CHINESE REMAINDER THEOREM AND
MODULAR MULTIPLICATIVE INVERSE[EXPLAINED].
Solve the following system of congruences:
x mod 5 = 1
x mod 7 = 2
x mod 9 = 3
x mod 11=4
Notice that the moduli are, pairwise, relatively prime, as required by the theorem. We have: M = 5 · 7 · 9 · 11 = 3465........................................................(1). M/5 = 693, M/7 = 495, M/9 = 385, and M/11 = 315...............(2)
A small calculation gives 2, 3, 4, and 8 as the "Modular Multiplicative Inverses" of the values in (2) above. Then these "mmi's" are multiplied by the remainders of the congruences and by the values in (2) above and then added all up as follows: x = [1 · 693 · 2] +[ 2·495·3] + [3·385·4] + [4·315·8] = 19056. So x = [19056] mod [3465] in (1) above==1,731. 1731 is the smallest positive integer solution. The full solution is x ≡ 3465c + 1731, where c=0, 1, 2, 3......etc.
In order to find inverses 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. These inverses are calculated as follows:[5*7*9*11] / 5 =693 mod 5 =3^(-1) mod 5 =2....and so on for each of the four moduli above. The inverses can all (in this case) be guessed at mentally, instead of using more formal methods such as "Extended Euclidean Algorithm." 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!
Notice that when doing modular problems, we can always replace any integer by any other integer in its congruence class.
!
