Thread: chinese remainder

1) Make a list of the units in Z16, and with each unit give its multiplicative inverse.

2) Solve the following system of congruences

X=2 (mod 3)
X=3 (mod 5)
X=6 (mod 7)

3) Solve the following system of congruences

X=2 (mod 3)
X=3 (mod 5)
X=4 (mod 7)
X=5 (mod 11)

Any help would be great.

Originally Posted by noles2188

1) Make a list of the units in Z16, and with each unit give its multiplicative inverse.

This is just "arithmetic" If, for example, 3 and x are multiplicative inverses, then 3x= 1 (mod 16) so 3x= 16n+ 1. 16+ 1= 17 is not a multiple of 16 but 2(16)+ 1= 33 is. It is 3(11) so the multiplicative inverse of 3 is 11. Similarly 16n+ 1 is a multiple of 5 for n= 4: 16(4)+ 1= 65= 5(13) so the multiplicative inverse of 5 is 13. 16(3)+1= 49= 7(7) so 7 is its own multiplicative inverse. 5(16)+ 1= 81= 9*9 so 9 is also its own multiplicative inverse. 15*15= 225= 14(16)+ 1 so 15 is also its own multiplicative inverse.

If p is even, then px- 16n is divisible by 2 no matter what x and n are so we can never have px- 16n= 1 or px= 16n+ 1. What does that tell you?

[2) Solve the following system of congruences

X=2 (mod 3)
X=3 (mod 5)
X=6 (mod 7)

Those tell you that X= 3a+ 2= 5b+ 3= 7c+ 6 for integers a, b, c. Just looking at possible values for c, I find that 7(11)+ 6= 5(13)+ 3= 3(27)+ 2.

3) Solve the following system of congruences

X=2 (mod 3)
X=3 (mod 5)
X=4 (mod 7)
X=5 (mod 11)

Any help would be great.

Again, these equations tell you that X= 3a+ 2= 5b+ 3= 7c+ 4= 11d+ 5 for integer. Trying succesive values for d I find that 11(33)+5= 7(52)+ 4= 5(13)+ 3= 3(122)+ 2= 368.

For a more systematic way of doing these look up the "Chinese Remainder Theorem".