Math 127: Chinese Remainder Theorem PDF

Chinese Reminder Theorem

The Chinese Remainder Theorem enables one to solve simultaneous equations Step 1 Implement step (1). z1 = m/m1 = 60/4=3 · 5 = 15 z2 = 20

Math 127: Chinese Remainder Theorem

Example 2. Find x such that 3x ? 6 (mod 12). Solution. Uh oh. This time we don't have a multiplicative inverse to

The Chinese Remainder Theorem

The Chinese Remainder Theorem says that certain systems of simultaneous congruences with dif- Returning to the proof of the induction step I have.

On Solving Ambiguity Resolution with Robust Chinese Remainder

29 juin 2018 Theorem 1: ? can be divided into at most N disjoint subsets within which the index are consecutive. Moreover

The Chinese Remainder Theorem. Topics in Algebra 5900 Spring

Example. The multiplication table for mod 6 numbers is: Step 2. Given an ordered pair (r s)

Chinese Remainder Theorem Example. Find a solution to x ? 88

Chinese Remainder Theorem. Example. Find a solution to x ? 88 (mod 6) x ? 100 (mod 15). Solution 1: From the first equation we know we want x ? 88 = 6k

The Chinese Remainder Theorem Theorem. Let m and n be two

C and e. Then Alice and Bob do the Oblivious Transfer protocol Alice sending n to Bob in Step 1. If Bob learns the factorization

MODULAR EXPONENTIATION VIA THE EXPLICIT CHINESE

14 sept. 2006 The usual Chinese remainder theorem says that (for example) x1x4 mod P is ... During one time step a single memory location might be.

MODULAR EXPONENTIATION VIA THE EXPLICIT CHINESE

14 sept. 2006 The usual Chinese remainder theorem says that (for example) x1x4 mod P is ... During one time step a single memory location might be.

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

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)quotesdbs_dbs3.pdfusesText_6

[PDF] Math 127: Chinese Remainder Theorem

Math 127: Chinese Remainder Theorem

Mary Radclie

1 Chinese Remainder Theorem

3x7 (mod10)

Example 3.Findx, if possible, such that

2x5 (mod7);

3x4 (mod8)

3(6 + 7k)4 (mod8)

18 + 21k4 (mod8)

2 + 5k4 (mod8)

5k2 (mod8):

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

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

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

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

Proof.For eachiwith 1ik, putmi=Nn

Putx=y1b1m1+y2b2m2++ykbkmk:

Notice that for eachiwith 1ik, we obtain

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