Math 127: Chinese Remainder Theorem

1 math 127: Chinese Remainder TheoremMary Radcliffe1 Chinese Remainder TheoremUsing the techniques of the previous section, we have the necessary tools to solve congruences of the formax b(modn). The Chinese Remainder Theorem gives us a tool to consider multiple such , let s just ensure that we understand how to solveax b(modn).Example that 3x 7 (mod 10) on our previous work, we know that 3 has a multiplicative inverse modulo 10,namely 3 (10) 1. Moreover, (10) = 4, so the inverse of 3 modulo 10 is 33 27 7 (mod 10).Hence, multiplying both sides of the above equation by 7, we obtain3x 7 (mod 10) 7 3x 7 7 (mod 10) x 49 9 (mod 10)Hence, the solution isx 9 (mod 10).Example that 3x 6 (mod 12). oh. This time we don t have a multiplicative inverse to work with. So what to do?Well, let s take a look at what this would mean. If 3x 6 (mod 12), that means 3x 6 is divisibleby 12, so there is somek Zsuch that 3x 6 = 12k. Now that we re working in the integers, wecan happily divide by 3, and we thus obtain thatx 2 = 4k.

2 Hence, we have thatx 2 (mod 4)solves the desired course, the strategy outlined here will not always work. Imagine, if instead of 3x 6 (mod 12), wewanted 3x 7 (mod 12). Obviously that wouldn t be possible, as writing out the corresponding integerequation yields 3x 7 = 12k, and there are no integersx, ksuch that 3x 12k= 7, by Bezout s general, we have thatax b=nyfor somey Z, and henceax ny=b. This implies that we canfind a solution to this congruence if and only if gcd(a, n)|b, again by Bezout s N, and leta, b Z. The congruenceax b(modn) has a solution forxif andonly if gcd(a, n)| , the strategy we employed in Example 2 will in general work. Suppose that we haveax b(modn), and we have that gcd(a, n) =d. Then in order that this has a solution, we know thatbisdivisible byd. In particular, there exist integersa , b , n such thata=a d, b=b d, n=n d. We can thenwork as we did in Example 2 to rewrite this equation asa x b (modn ).

3 1 Example , if possible, such that2x 5 (mod 7),and 3x 4 (mod 8) note that 2 has an inverse modulo 7, namely 4. So we can write the first equiva-lence asx 4 5 6 (mod 7). Hence, we have thatx= 6 + 7kfor somek we can substitute this in for the second equivalence:3x 4 (mod 8)3(6 + 7k) 4 (mod 8)18 + 21k 4 (mod 8)2 + 5k 4 (mod 8)5k 2 (mod 8).Recalling that 5 has an inverse modulo 8, namely 5, we thus obtaink 10 2 (mod 8).Hence, we have thatk= 2 + 8jfor somej this back in forx, we have thatx= 6 + 7k= 6 + 7(2 + 8j) = 20 + 56jfor somej fact, any choice ofjwill work here. Hence, we have thatxis a solution to the system ofcongruences if and only ifx 20 (mod 56).Example , if possible, such thatx 3 (mod 4),andx 0 (mod 6). s work as we did above. From the first equivalence, we have thatx= 3 + 4kfor somek Z. Then, the second equivalence implies that 3 + 4k 0 (mod 6), and hence4k 3 3 (mod 6).

4 However, this is impossible, since we know that gcd(4,6) = 2 and 26| , so not every system of congruences will have a solution, but our strategy of trying to solve themwill reveal when there is no solution the problem that occurred here: when we considered the first equivalence, we ended up witha coefficient of 4 in front of thek. Since 4 is not relatively prime to 6, there was a chance that the nextequivalence would not have a solution, and indeed that is what happened. In general this will be the case:if we consider two equivalences of the formx b1(modn1)x b2(modn2),then the method we developed above will take the following approach: first, writex=b1+kn1. Plugthat in to the second equation to obtainkn1 b2 b1(modn2). Ifn1andn2share factors, then wemay not be able to solve this equivalence, per Proposition 1. Hence, we can demand thatn1andn2arerelatively prime, and this should solve that , then, if we assume thatn1andn2are relatively prime, we have reduced this system tokn1 b2 b1(modn2).

5 Then we obtainkn1 b2+b1=jn2for somej Z. Rearranging, we havekn1 jn2=b2 b1. Sincen1andn2are relatively prime, we know from Bezout s Lemma that we will be2able to solve this equation forkandj. Once we knowkandj, we can then backsolve to give us a strategy of considering relatively prime moduli, in general, will yield a solution to this general form is given by the following , n2, .. , nkbe a set of pairwise relatively prime natural numbers, and letb1, b2, .. , bk Z. PutN=n1n2.. nk, the product of the moduli. Then there is a uniquex(modN)such thatx bi(modni)for all1 i that working modNshould be unsurprising; this is how we ended up in the first example as can see that the method of backsolving forxwill end up multiplying the moduli eachiwith 1 i k, putmi=Nni. Notice that since the moduli are relatively prime, andmiis the product of all the moduli other thanni, we have thatni mi, and hencemihas a multiplicativeinverse moduloni, sayyi.

6 Moreover, note thatmiis a multiple ofnjfor allj6= +y2b2m2+ + that for eachiwith 1 i k, we obtainx y1b1m1+y2b2m2+ +ykbkmk(modni) yibimi(modni)(since eachmjwithj6=iis a multiple ofni) bi(modni)(sinceyiis an inverse tomimoduloni).Therefore, we have thatx bi(modni) for all 1 i , we wish to show uniqueness of the solution (modN). Suppose thatxandyboth solve thecongruences. Then we have that for eachi,niis a divisor ofx y. Since theniare relatively prime, thismeans thatNis a divisor ofx y, and hencex yare congruent moduloN. Example the Chinese Remainder Theorem to find anxsuch thatx 2 (mod 5)x 3 (mod 7)x 10 (mod 11) 5 7 11 = 385. Following the notation of the Theorem , we havem1=N/5 = 77,m2=N/7 = 55, andm3=N/11 = now seek a multiplicative inverse for eachmimoduloni. First:m1 77 2 (mod 5), andhence an inverse tom1modn1isy1= :m2 55 6 (mod 7), and hence an inverse tom2modn2isy2= :m3 35 2 (mod 11), and hence an inverse tom3modn3isy3= , the Theorem states that a solution takes the form:x=y1b1m1+y2b2m2+y3b3m3= 3 2 77 + 6 3 55 + 6 10 35 = we may take the solution moduloN= 385, we can reduce this to 87, since 2852 87 (mod 385).

7 3 Example all solutionsx, if they exist, to the system of equivalences:2x 6 (mod 14)3x 9 (mod 15)5x 20 (mod 60) in Example 2, we first wish to reduce this, where possible, using the strategy outlinedfollowing the statement of Proposition 1. Since gcd 2,14 = 2, we can cancel a 2 from all terms inthe first equivalence to writex 3 (mod 7). Likewise, we simplify the other two equivalences toreduce the entire system tox 3 (mod 7)x 3 (mod 5)x 4 (mod 12).We can now follow the strategy of the Chinese Remainder Theorem . Following the notation in thetheorem, we havem1= 5 12 = 60 4 (mod 7);y1 45 1024 2 (mod 7)m2= 7 12 = 84 4 (mod 5);y2 43 64 4 (mod 5)m3= 7 5 = 35 11 (mod 12);y3 113 ( 1)3 1 11 (mod 12).Hence, we havex=y1m1b1+y2m2b2+y3m3b3= 2 60 3 + 4 84 3 + 11 35 4 = , we have any solutionx 2908 388 (mod 420).4