THE CHINESE REMAINDER THEOREM

1 THE CHINESE REMAINDER THEOREMKEITH CONRADWe should thank the CHINESE for their wonderful REMAINDER CHINESE REMAINDER THEOREM says we can uniquely solve every pair of congruenceshaving relatively prime relatively prime positive integers. For all integersaandb,the pair of congruencesx amodm, x bmodnhas a solution, and this solution is uniquely determined is important here is thatmandnare relatively prime. There arenoconstraintsat all congruencesx 6 mod 9 andx 4 mod 11 hold whenx= 15, andmore generally whenx 15 mod 99, and they do not hold for otherx. The modulus 99 is9 will prove the CHINESE REMAINDER THEOREM , including a version for more than twomoduli, and see some ways it is applied to study proof of the CHINESE REMAINDER we show there is always a solution. Then we will show it is unique of Solution. To show that the simultaneous congruencesx amodm, x bmodnhave a common solution inZ, we give two proof: Write the first congruence as an equation inZ, sayx=a+myfor somey Z.

2 Then the second congruence is the same asa+my both sides, we need to solve foryin( )my b (m, n) = 1, we knowmmodnis invertible. Letm be an inverse formmodn,somm 1 modn. Multiplying through ( ) bym , we havey m (b a) modn, soy m (b a) +nzwherez Z. Thenx=a+my=a+m(m (b a) +nz) =a+mm (b a) + CONRADS oifxsatisfies the original two congruences it must have this form. Let s now check thisexpression, for everyz Z, really satisfies the original two congruences:a+mm (b a) +mnz a+ 0 + 0 amodmanda+mm (b a) +mnz a+ 1(b a) + 0 proof: Write both congruences as equations inZ:x=a+myandx=b+nzfor integersyandzthat need to be determined. (Why would it be a bad idea to writex=a+myandx=b+ny?) The integers of the forma+myare the numbers thatare congruent toamodm, and the integers of the formb+nzare the numbers that arecongruent tobmodn. Finding a common solution to the two congruences amounts tofindingyandzinZsuch thata+my=b+nz,which is the same as( )my nz=b we find suchyandzfor alla,b,m, andnwhere (m, n) = 1?

3 Bezout s identity tells us 1is aZ-linear combination ofmandn, and therefore every integer is aZ-linear combinationofmandn(why?). Therefore integersyandzsatisfying ( ) of Solution. Ifx=candx=c both satisfyx amodm, x bmodn,then we havec c modmandc c modn. Thenm|(c c ) andn|(c c ). Since(m, n) = 1, the productmndividesc c , which meansc c modmn. This shows allsolutions to the initial pair of congruences are the same modulomn. to more than two congruencesThe CHINESE REMAINDER THEOREM can be extended from two congruences to an arbitraryfinite number of congruences, but we have to be careful about the way in which the moduliare relatively prime. Consider the three congruencesx 1 mod 6, x 4 mod 10, x 7 mod there is no common factor of 6, 10, and 15 greater than 1, these congruences donot admit a common solution: every solution to the first congruence is odd, while everysolution to the second congruence is even.

4 When we have more than two moduli, we have tobe sensitive to the difference between saying numbers are collectively relatively prime (nocommon factor greater than 1 divides them all) and pairwise relatively prime (no commonfactor greater than 1 can divide some pair of the numbers). For instance, 6, 10, and 15 arecollectively relatively prime but not pairwise relatively prime. Here is a more general formof the CHINESE REMAINDER 2, letm1, m2, .. , mrbe nonzero integers that are pairwise rela-tively prime:(mi, mj) = 1fori6=j. Then, for all integersa1, a2, .. , ar, the system ofcongruencesx a1modm1, x a2modm2, .. , x armodmr,has a solution, and this solution is uniquely determined modulom1m2 congruencesx 1 mod 3,x 2 mod 5,x 2 mod 7 are satisfied whenx= 37, more generally for allx 37 mod 105 and for no otherx. Note 105 = 3 5 CHINESE REMAINDER we show there is always a solution.

5 Then we will show it is unique modulom1m2 of Solution. We argue by induction onr. The base caser= 2 is , which has been proved we pass to the inductive step. Suppose all simultaneous congruences withrpairwiserelatively prime moduli can be solved. Consider a system of simultaneous congruences withr+ 1 pairwise relatively prime moduli:x a1modm1, .. , x armodmr, x ar+1modmr+1,where (mi, mj) = 1 for alli6=jand theai s are arbitrary. By the inductive hypothesis,there is a solutionbto the firstrcongruences, sayb a1modm1, b a2modm2, .. , b consider the system oftwocongruences( )x bmodm1m2 mr, x ar+1modmr+ (mi, mr+1) = 1 fori= 1,2, .. , r, we have (m1m2 mr, mr+1) = 1, so the two moduliin ( ) are relatively prime. Then by the case of two congruences, namely THEOREM ,there is a solution to ( ). Call itc. Sincec bmodm1m2 mr, we havec bmodmifori= 1,2, .. , r. From the choice ofbwe haveb aimodmifori= 1,2.

6 , r. Thereforec aimodmifori= 1,2, .. , r. Also,c ar+1modmr+1from the choice ofc, so we seecsatisfies ther+ 1 given concludes the inductive step, so a solution of Solution. Ifx=candx=c both satisfyx a1modm1, x a2modm2, .. , x armodmr,then we havec c modmifori= 1,2, .. , r, somi|(c c ) fori= 1,2, .. , r. Since themi s are pairwise relatively prime, their productm1m2 mrdividesc c , which meansc c modm1m2 mr. This shows all solutions to the given system of congruences arethe same when viewed modulom1m2 mr. significance of the CHINESE REMAINDER THEOREM is that it often reduces a questionabout modulusmn, where (m, n) = 1, to the same question for this way, questions about modular arithmetic can often be reduced to the special case ofprime power moduli. We will see how this works for several counting problems, often usingtwo features of modular arithmetic with two moduli: ifd|mit makes sense to reduce integers modmto integers modd: ifx ymodmthenx ymodd.

7 For example, ifx ymod 10 thenx ymod 5 since ifx yis divisible by 10 then it is also divisible by 5. (In contrast, it makes no sense toreducexmod 10 toxmod 3, since there are congruent numbers mod 10 that areincongruent mod 3, such as 1 and 11.) ifx ymodmandx ymodnand (m, n) = 1 thenx ymodmn. This wasused in the uniqueness part of the proof of the CHINESE REMAINDER first application is to counting units relatively prime positive integersmandn, (mn) = (m) (n).4 KEITH work with the setsUm={amodm,(a, m) = 1}, Un={bmodn,(b, n) = 1},Umn={cmodmn,(c, mn) = 1}.Then|Um|= (m),|Un|= (n), and|Umn|= (mn). To show (mn) = (m) (n), wewill write down a bijection betweenUmnandUm Un, which implies the two sets have thesame size, and that is what the THEOREM is saying (since|Um Un|= (m) (n)).Letf:Umn Um Unby the rulef(cmodmn) = (cmodm, cmodn).Forc Umn, we have (c, mn) = 1, so (c, m) and (c, n) equal 1, socmodmandcmodnare units.

8 Let s stop for a moment to take a look at an example of this 3 andn= 5:U3={1,2},U5={1,2,3,4}, andU15={1,2,4,7,8,11,13,14}.The following table shows the values of the functionfon each number inU15. Notice thatthe values fill up all ofU3 U5without 15f(cmod 15)1(1,1)2(2,2)4(4,4) = (1,4)7(7,7) = (1,2)8(8,8) = (2,3)11(11,11) = (2,1)13(13,13) = (1,3)14(14,14) = (2,4)There are 2 units modulo 3 and 4 units modulo 5, leading to 8 ordered pairs of units modulo3 and units modulo 5: (1,1), (1,2), (1,3), (1,4), (2,1), (2,2), (2,3), and (2,4). All these pairsshow up (and just once) in the second column of the return to the general situation and showf:Umn Um Unis a see thatfis one-to-one, supposef(kmodmn) =f(`modmn). Thenk `modmandk `modn, so since (m, n) = 1 (aha!), we havek `modmn. That meansk=`inUmn, sofis we showfis onto. Pick a pair (amodm, bmodn) Um Un. By the Chineseremainder THEOREM we can solvec amodmandc bmodnfor ac Z.

9 Is (c, mn) = 1?Sinceamodmis a unit andc amodm,cmodmis a unit so (c, m) = 1. Sincebmodnis a unit andc bmodn,cmodnis a unit so (c, n) = 1. From (c, m) = 1 and (c, n) = 1 weget (c, mn) = 1, soc Umn. From the congruence conditions onc, we havef(c) = (a, b). Corollary a positive integerm, (m) =m p|m(1 1p),where the product runs over the formula is clear form= 1 (interpreting an empty product as 1).Now supposem >1, and factorminto prime powers:m=pe11pe22 CHINESE REMAINDER THEOREM5 Thepeii s are pairwise relatively prime. By an extension of THEOREM from two relativelyprime terms to an arbitrary number of pairwise relatively prime terms (just induct on thenumber of terms), we have (m) = (pe11) (pe22) (perr).Now using the formula for on prime powers, (m) =pe1 11(p1 1)pe2 12(p2 1) per 1r(pr 1)=pe11(1 1p1)pe22(1 1p2) perr(1 1pr)=m p|m(1 1p). Example compute (540) = (22 33 5), we have (540) = 540(1 12)(1 13)(1 15)= 540 12 23 45= 18 8= alternate calculation is (540) = (4) (27) (5)= (4 2)(27 9)(5 1)= 2 18 4= table of values of (m), as shown below, suggests that (m) is even whenm >2, which is true.

10 But not every positive even number is a value of the 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 (m)1 1 2 2 4 2 6 4 641041268816We will use the general formula for (m) to show for all odd primesq >3 that there isno solution to (m) = 2q2. (For example, takingq= 5,7, and 11, (m) is never 50, 98,or 242. But 2 32= (33).) For each odd prime factorpofm, (m) is divisible byp 1,which is even, so ifmhas more than 2 odd prime factors then (m) would be divisible by4. Thus when (m) = 2q2,mhas at most one odd prime factor, som= 2e, 2epf, orpf(allexponents are positive). Ifm= 2ethen (m) = 2e 1is a power of 2, which is not true. Ifm=pfthen (m) =pf 1(p 1), so if this is 2q2thenpf 1(p 1)/2 =q2. Iff 2 thenp|q2, sop=qandqf 1(q 1)/2 =q2. Every prime factor of (q 1)/2has to beq, which is impossible, so (q 1)/2 = 1 and thusq= 3, so whenq >3 wecan t havem= CONRAD Ifm= 2epfthen (m) = (2e) (pf) = 2e 1(p 1)pf 1.