The Chinese Remainder Theorem - Loyola University Chicago

1 The Chinese Remainder TheoremWe now know how to solve a single linear congruence. In this lecture weconsider how to solve systems ofsimultaneouslinear solve the system 2x 5 (mod 7); 3x 4 (mod 8) of twolinear congruences (in one variablex). Multiply the first congruence by 2 1mod 7 = 4 to get 4 2x 4 5 (mod 7). This simplifies tox 6 (mod 7),sox= [6]7orx= 6 + 7t, wheret substitute forxin the second congruence: 3(6 + 7t) 4 (mod 8). Thissimplifies to 5t 2 (mod 8), which we solve by multiplying both sides by5 1mod 8 = 5 to obtaint 2 (mod 8). Sot= [2]8ort= 2 + 8s, wheres intoxgivesx= 6 + 7(2 + 8s) = 20 + 56s, which givesthe solutionx= [20]56orx 20 (mod 56). (Notice that 56 = 7 8.) 4x 2 (mod 6); 3x 5 (mod 8).

2 Start by reducing the first congruence to 2x 1 (mod 3). Multiply bothsides by 2 (an inverse of 2 mod 3) to solve it, which givesx 2 (mod 3), sox= 2 + substitutexinto the second given congruence: 3(2 + 3t) 5 (mod 8).This simplifies tot 1 (mod 8) ort 7 (mod 8). Sot= 7 + the formula forxwe obtainx= 2 + 3(7 + 8s) = 23 + 23 (mod 24). This is the complete solution. (Notice that 24 is theleast common multiple of 6,8.)The technique of the examples can always be used to solve simultaneouscongruences when there is a may be no solution, but the technique detects that as systemx 3 (mod 4);x 0 (mod 6) hasno the first congruence givesx= 3 + 4t, and substituting that into thesecond gives 3 + 4t 0 (mod 6) or 4t 3 (mod 6).

3 This congruence hasno solution, sinced= gcd(4,6) does not divide , in this case there is a simpler way to see there is no solution. Justnotice that the first congruence impliesxis odd, but the second implies thatxis even. That s a that have no solution are said to ( Chinese Remainder Theorem ).Letm1, m2, .. , mrbe a collec-tion of pairwise relatively prime integers. Then the system of simultaneouscongruencesx a1(modm1)x a2(modm2)..x ar(modmr)has a unique solution moduloM=m1m2, mr, for any given integersa1, a2, .. , of mrand for eachk= 1,2, .. , rletMk= gcd(Mk, mk) = 1 for allk. Letykbe an inverse ofMkmodulomk, foreachk. Then by definition of inverse we haveMkyk 1 (modmk). Letx=a1M1y1+a2M2y2+ + a simultaneous solution to all of the congruences.

4 Since the modulim1, .. , mrare pairwise relatively prime, any two simultaneous solutions tothe system must be congruent moduloM. Thus the solution is a uniquecongruence class moduloM, and the value ofxcomputed above is in that the proof is constructive! Not only does it tell us why thetheorem is true, it also gives an explicitformulafor the all integersxwhich leave a Remainder of 1, 2, 3, and 4when divided by 5, 7, 9, and 11 are asked to solve the system of congruences:x 1 (mod 5)x 2 (mod 7)x 3 (mod 9)x 4 (mod 11).Notice that the moduli are pairwise relatively prime, as required by thetheorem. We haveM= 5 7 9 11 = 3465 andM1=M/5 = 693,2M2=M/7 = 495,M3=M/9 = 385, andM4=M/11 = 315.

5 A smallcalculation givesy1= 2,y2= 3,y3= 4, andy4= 8. Hencex= 1 693 2 +2 495 3 + 3 385 4 + 4 315 8 = 19056. Sox= [19056]M= [1731]M. In fact,1731 is the smallest positive integer solution. The full solution isx 1731(modM).In the preceding example, in order to findykfork= 1,2,3,4 we needed toinvert [693]5= [3]5, [495]7= [5]7, [385]9= [7]9, and [315]11= [7]11. Theinverses can all (in this case) be guessed mentally. Notice carefully how wedo not actually need to work with the large numbersMkfork= 1,2,3,4 inorder to find the desired inverses!This is another example of the useful fact that when doing modular prob-lems, we can always replace any integer by any other integer in its can also solve other systems by the Chinese Remainder Theorem .

6 For ex-ample, verify that the system 2x 5 (mod 7); 3x 4 (mod 8) is equivalentto the simpler systemx 6 (mod 7)x 4 (mod 8).By solving this by the Chinese Remainder Theorem , we also solve the originalsystem. (The solution isx 20 (mod 56).)Of course, the formula in the proof of the Chinese Remainder Theorem isnot the only way to solve such problems; the technique presented at thebeginning of this lecture is actually more general, and it requires no mem-orization. Nevertheless, the formula in the proof of the Chinese remaindertheorem is sometimes