Discrete Mathematics Questions A Find solution to the congru

Discrete Mathematics Questions

A) Find solution to the congruence 7x 12 (mod 19)

B) Find all integers x such that 2x 1 (mod 5), x 2 (mod 6), and -x 3 (mod 7).

Note that

7*11=77=76+1=19*4+1=1 mod 19

So we multiply the given congruence by 11. We can do this because 11 and 19 are coprime

SO we get

11*7x=11*12 (mod 19)

77x=132 (mod 19)

x=133-1=19*7-1=-1 (mod 19)

So solution is

x=-1 (mod 19)

2x=1 (mod 5)

Multiplying by 3 gives

6x=3 (mod 5)

x=3 (mod 5)

-x=3 (mod 7)

x=-3 (mod 7)

x=4 (mod 7)

x=7n+4

Case 1. n=1 mod 5

x=7*1+4=11=1 mod 5

Case 2: n=2 mod 5

x=7*2+4=18=3 mod 5

Case 3. n=3 mod 5

x=7*3+4=25=0 mod 5

Case 4. n=4 mod 5

x=7*4+4=32=2 mod 5

Hence, n=2 mod 5, n=5m+2

x=7(5m+2)+4=35m+18

x=2 mod 6

35m+18=2 mod 6

35m=2 mod 6

-m=2 mod 6

m=-2 mod 6

m=4 mod 6

Hence, m=6p+4

So, x=35(6p+4)+18=210p+158