+0  
 
0
1243
2
avatar

Solve the following system of congruences:
x ≡ 1 (mod 5)
x ≡ 2 (mod 7)
x ≡ 3 (mod 9)
x ≡ 4 (mod 11).

 Use the "Chinese Remainder Theorem" if possible. I would appreciate any help. Thank you.

 May 29, 2019
 #1
avatar
+1

I wrote a relatively short computer code to solve them for you. The code uses the Chinese Remainder Theorem + Modular Multiplicative Inverse. One of the mathematicians here is much better suited in explaining it to you than I am.

 

i=1;a1=5;a2=7;a3=9;a4=11;a5=1;a=((a1*a2*a3*a4*a5)/a1);m=a1;a=a%m; if(a*i % m==1,goto loop, goto loop1);loop:print"The mmi = ",i;loop1:i++;if(i<=(m-1), goto3, discard=0;
r1=1;r2=2;r3=3;r4=4;r5=0;listforeach(x, m=product(a1, a2, a3, a4, a5),(( n=m/a1*r1*2+ m/a2*r2*3+ m/a3*r3*4 + m/a4*r4*8 + m/a5*r5*0));printm,"m + ",n%m;return


OUTPUT:   3465m + 1731, m=0, 1, 2, 3........etc.

 May 30, 2019
 #2
avatar
+1

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.

 May 30, 2019
edited by Guest  May 30, 2019
edited by Guest  May 30, 2019

2 Online Users

avatar
avatar