[PDF] Math 127: Chinese Remainder Theorem

View - Download Math 127: Chinese Remainder Theorem

Previous PDF

Next PDF

Math 127: Chinese Remainder Theorem

Mary Radclie

1 Chinese Remainder Theorem

Using the techniques of the previous section, we have the necessary tools to solve congruences of the form

axb(modn). The Chinese Remainder Theorem gives us a tool to consider multiple such congruences simultaneously.

First, let's just ensure that we understand how to solveaxb(modn).Example 1.Findxsuch that 3x7 (mod10)

Solution.Based 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 33277 (mod10). Hence, multiplying both sides of the above equation by 7, we obtain

3x7 (mod10)

,73x77 (mod10) ,x499 (mod10) Hence, the solution isx9 (mod10).Example 2.Findxsuch that 3x6 (mod12). Solution.Uh 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 3x6 (mod12), that means 3x6 is divisible by 12, so there is somek2Zsuch that 3x6 = 12k. Now that we're working in the integers, we can happily divide by 3, and we thus obtain thatx2 = 4k. Hence, we have thatx2 (mod4)

solves the desired congruence.Of course, the strategy outlined here will not always work. Imagine, if instead of 3x6 (mod12), we

wanted 3x7 (mod12). Obviously that wouldn't be possible, as writing out the corresponding integer equation yields 3x7 = 12k, and there are no integersx;ksuch that 3x12k= 7, by Bezout's Lemma. In general, we have thataxb=nyfor somey2Z, and henceaxny=b. This implies that we can nd a solution to this congruence if and only if gcd(a;n)jb, again by Bezout's Lemma. Proposition 1.Letn2N, and leta;b2Z. The congruenceaxb(modn) has a solution forxif and only if gcd(a;n)jb. Moreover, 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 thatbis divisible byd. In particular, there exist integersa0;b0;n0such thata=a0d;b=b0d;n=n0d. We can then work as we did in Example 2 to rewrite this equation asa0xb0(modn0). 1

Example 3.Findx, if possible, such that

2x5 (mod7);

and 3x4 (mod8) Solution.First note that 2 has an inverse modulo 7, namely 4. So we can write the rst equiva- lence asx456 (mod7). Hence, we have thatx= 6 + 7kfor somek2Z. Now we can substitute this in for the second equivalence:

3x4 (mod8)

3(6 + 7k)4 (mod8)

18 + 21k4 (mod8)

2 + 5k4 (mod8)

5k2 (mod8):

Recalling that 5 has an inverse modulo 8, namely 5, we thus obtain k102 (mod8):

Hence, we have thatk= 2 + 8jfor somej2Z.

Plugging this back in forx, we have thatx= 6 + 7k= 6 + 7(2 + 8j) = 20 + 56jfor somej2Z. In fact, any choice ofjwill work here. Hence, we have thatxis a solution to the system of congruences if and only ifx20 (mod56).Example 4.Findx, if possible, such that x3 (mod4); andx0 (mod6): Solution.Let's work as we did above. From the rst equivalence, we have thatx= 3 + 4k for somek2Z. Then, the second equivalence implies that 3 + 4k0 (mod6), and hence

4k 33 (mod6). However, this is impossible, since we know that gcd(4;6) = 2 and 26 j3.Ok, so not every system of congruences will have a solution, but our strategy of trying to solve them

will reveal when there is no solution also. Notice the problem that occurred here: when we considered the rst equivalence, we ended up with

a coecient of 4 in front of thek. Since 4 is not relatively prime to 6, there was a chance that the next

equivalence 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 form xb1(modn1) xb2(modn2); then the method we developed above will take the following approach: rst, writex=b1+kn1. Plug that in to the second equation to obtainkn1b2b1(modn2). Ifn1andn2share factors, then we may not be able to solve this equivalence, per Proposition 1. Hence, we can demand thatn1andn2are relatively prime, and this should solve that problem. Continuing, then, if we assume thatn1andn2are relatively prime, we have reduced this system to kn

1b2b1(modn2). Then we obtainkn1b2+b1=jn2for somej2Z. Rearranging, we have

kn

1jn2=b2b1. Sincen1andn2are relatively prime, we know from Bezout's Lemma that we will be

2 able to solve this equation forkandj. Once we knowkandj, we can then backsolve to give us a solution forx.

This strategy of considering relatively prime moduli, in general, will yield a solution to this problem.

The general form is given by the following theorem. Theorem 1.Letn1;n2;:::;nkbe a set of pairwise relatively prime natural numbers, and letb1;b2;:::;bk2 Z. PutN=n1n2:::nk, the product of the moduli. Then there is a uniquex(modN)such thatx b i(modni)for all1ik. Note that working modNshould be unsurprising; this is how we ended up in the rst example as well. You can see that the method of backsolving forxwill end up multiplying the moduli together.

Proof.For eachiwith 1ik, putmi=Nn

i. Notice that since the moduli are relatively prime, and m iis the product of all the moduli other thanni, we have thatni?mi, and hencemihas a multiplicative inverse moduloni, sayyi. Moreover, note thatmiis a multiple ofnjfor allj6=i.

Putx=y1b1m1+y2b2m2++ykbkmk:

Notice that for eachiwith 1ik, we obtain

xy1b1m1+y2b2m2++ykbkmk(modni) yibimi(modni) (since eachmjwithj6=iis a multiple ofni) bi(modni) (sinceyiis an inverse tomimoduloni):

Therefore, we have thatxbi(modni) for all 1ik.

Finally, we wish to show uniqueness of the solution (modN). Suppose thatxandyboth solve the congruences. Then we have that for eachi,niis a divisor ofxy. Since theniare relatively prime, this

means thatNis a divisor ofxy, and hencexyare congruent moduloN.Example 5.Use the Chinese Remainder Theorem to nd anxsuch that

x2 (mod5) x3 (mod7) x10 (mod11) Solution.SetN= 5711 = 385. Following the notation of the theorem, we havem1=

N=5 = 77,m2=N=7 = 55, andm3=N=11 = 35.

We now seek a multiplicative inverse for eachmimoduloni. First:m1772 (mod5), and hence an inverse tom1modn1isy1= 3. Second:m2556 (mod7), and hence an inverse tom2modn2isy2= 6. Third:m3352 (mod11), and hence an inverse tom3modn3isy3= 6. Therefore, the theorem states that a solution takes the form: x=y1b1m1+y2b2m2+y3b3m3= 3277 + 6355 + 61035 = 3552: Since we may take the solution moduloN= 385, we can reduce this to 87, since 2852

87 (mod385).3

Example 6.Find all solutionsx, if they exist, to the system of equivalences:

2x6 (mod14)

3x9 (mod15)

5x20 (mod60)

Solution.As in Example 2, we rst wish to reduce this, where possible, using the strategy outlined following the statement of Proposition 1. Since gcd2;14 = 2, we can cancel a 2 from all terms in the rst equivalence to writex3 (mod7). Likewise, we simplify the other two equivalences to reduce the entire system to x3 (mod7) x3 (mod5) x4 (mod12): We can now follow the strategy of the Chinese Remainder Theorem. Following the notation in the theorem, we have m

1= 512 = 604 (mod7);y14510242 (mod7)

m

2= 712 = 844 (mod5);y243644 (mod5)

m

3= 75 = 3511 (mod12);y3113(1)3 111 (mod12):

Hence, we havex=y1m1b1+y2m2b2+y3m3b3= 2603 + 4843 + 11354 = 2908.

Hence, we have any solutionx2908388 (mod420).4

quotesdbs_dbs11.pdfusesText_17

[PDF] calcul modulo 97

[PDF] personnage du livre moi boy

[PDF] escadrille 80 questionnaire de lecture

[PDF] controle de lecture moi boy

[PDF] moi boy roald dahl pdf entier

[PDF] moi boy roald dahl résumé

[PDF] moi boy roald dahl pdf gratuit

[PDF] séquence pluriel des noms ce2

[PDF] no et moi telecharger pdf

[PDF] leçon pluriel des noms ce2 lutin bazar

[PDF] no et moi avis argumenté

[PDF] séquence pluriel des noms ce1

[PDF] effet doppler formules

[PDF] télécharger no et moi pdf

[PDF] effet doppler formule longueur d'onde