Question

The solution for the system of congruences x 2 mod 3, x 3 mod 5, x 2 mod 7 is

Answer 1

Answer:

M2 = M/7 = 495, M3 = M/9 = 385, and M4 = M/11 = 315. A small

calculation gives y1 = 2, y2 = 3, y3 = 4, and y4 = 8. Hence x = 1 · 693 · 2 +

2·495·3+ 3·385·4+ 4·315·8 = 19056. So x = [19056]M = [1731]M. In fact,

1731 is the smallest positive integer solution. The full solution is x ≡ 1731

(mod M).

In the preceding example, in order to find yk for k = 1, 2, 3, 4 we needed to

invert [693]5 = [3]5, [495]7 = [5]7, [385]9 = [7]9, and [315]11 = [7]11. The

inverses can all (in this case) be guessed mentally. Notice carefully how we

do not actually need to work with the large numbers Mk for k = 1, 2, 3, 4 in

order to find the desired inverses!

This is another example of the useful fact that when doing modular problems, we can always replace any integer by any other integer in its congruence

class.

We can also solve other systems by the Chinese remainder theorem. For example, verify that the system 2x ≡ 5 (mod 7); 3x ≡ 4 (mod 8) is equivalent

to the simpler system

x ≡ 6 (mod 7)

x ≡ 4 (mod 8).

By solving this by the Chinese remainder theorem, we also solve the original

system. (The solution is x ≡ 20 (mod 56).)

Of course, the formula in the proof of the Chinese remainder theorem is

not the only way to solve such problems; the technique presented at the

beginning of this lecture is actually more general, and it requires no memorization. Nevertheless, the formula in the proof of the Chinese remainder

theorem is sometimes convenient

Step-by-step explanation: