The Chinese Remainder Theorem
Posted: Mon Dec 04, 2017 1:09 pm
Consider the following simultaneous congruence. x=3 (mod II), x = 5 (mod 6). It is easy to find a solution, x = 47, by inspection. Here's another method. Since 61-II, we can find a linear combination of 6 and II that equals one, for example, ( -I) . II + 2·6 = I.
Now compute 5·(-1)·11 +3·2·6= -19.
This number is a solution, modulo 66 = 6· II. Indeed, 47=-19 (mod 66).
(a) Why does this work?
(b) Note that the two moduli (which were II and 6 in the example) must be reby example that there may not always be a solution to a simultaneous congruence if the two moduli share a factor.
(c) Let m 1-n, let a and b be arbitrary, and let x simultaneously satisfy the congruences x = a (mod m) and x = b (mod n). The algorithm described above will produce a solution for x. Show that this solution is unique modulo mn.
(d) Show that this algorithm can be extended to any finite number of simultaneous congruences, as long as the moduli are pairwise relatively prime.
(e) Show that there exist three consecutive numbers, each of which is divisible by the 1999th power of an integer.
(f) Show that there exist 1999 consecutive numbers, each of which is divisible by the cube of an integer.
Please help me in solving it.
Now compute 5·(-1)·11 +3·2·6= -19.
This number is a solution, modulo 66 = 6· II. Indeed, 47=-19 (mod 66).
(a) Why does this work?
(b) Note that the two moduli (which were II and 6 in the example) must be reby example that there may not always be a solution to a simultaneous congruence if the two moduli share a factor.
(c) Let m 1-n, let a and b be arbitrary, and let x simultaneously satisfy the congruences x = a (mod m) and x = b (mod n). The algorithm described above will produce a solution for x. Show that this solution is unique modulo mn.
(d) Show that this algorithm can be extended to any finite number of simultaneous congruences, as long as the moduli are pairwise relatively prime.
(e) Show that there exist three consecutive numbers, each of which is divisible by the 1999th power of an integer.
(f) Show that there exist 1999 consecutive numbers, each of which is divisible by the cube of an integer.
Please help me in solving it.