[PDF] The Chinese Remainder Theorem The Chinese Remainder Theorem says

View - Download The Chinese Remainder Theorem

Previous PDF

Next PDF

12-14-2022

The Chinese Remainder Theorem

TheChinese Remainder Theoremsays that certain systems of simultaneous congruenceswith dif- ferent modulihave solutions. The idea embodied in the theorem was known to the Chinese mathematician

Sunzi in the 3

rdcentury A.D. - hence the name.

I"ll begin by collecting some useful lemmas.

Lemma 1.Letmanda1,...,anbe positive integers. Ifmis relatively prime to each ofa1,...,an, then it is relatively prime to their producta1···an.

Proof.If (m,a1···an)?= 1, then there is a primepwhich divides bothmanda1···an. Nowp|a1···an,

sopmust divideaifor somei. Butpdivides bothmandai, so (m,ai)?= 1. This contradiction implies that (m,a1···an) = 1.

For example, 6 is relatively prime to 25, to 7, and to 11. Now 25·7·11 = 1925, and (6,1925) = 1.

I showed earlier that the greatest common divisor (a,b) ofaandbisgreatestin the sense that it is divisible by any common divisor ofaandb. The next result is the analogous statement for least common multiples. Lemma 2.Letmanda1,...,anbe positive integers. Ifmis a multiple of each ofa1,...,an, thenmis a multiple of [a1,...,an]. Proof.By the Division Algorithm, there are unique numbersqandrsuch that Nowaidivides bothmand [a1,...,an], soaidividesr. Since this is true for alli,ris a common

multiple of theaismaller than theleastcommon multiple [a1,...,an]. This is only possible ifr= 0. Then

m=q·[a1,...,an], i.e.mis a multiple of [a1,...,an].

For instance, 88 is a multiple of 4 and 22. The least common multiple of 4 and 22 is 44, and 88 is also

a multiple of 44. Lemma 3.Leta1,...,anbe positive integers. Ifa1,...,anare pairwise relatively prime (that is, (ai,aj) = 1 fori?=j), then [a1,...,an] =a1···an. Proof.Induct onn. The statement is trivially true forn= 1, so I"ll start withn= 2. The statement for n= 2 follows from the equationxy= [x,y](x,y): [a1,a2] =a1a2 (a1,a2)=a1a21=a1a2. Now assumen >2, and assume the result is true forn. I will prove that it holds forn+ 1.

Claim:[[a1,...,an],an+1] = [a1,...,an,an+1].

(Some people take this as an iterativedefinitionof [a1,...,an,an+1].) [a1,...,an,an+1] is a multiple of

each ofa1,...,an, so by Lemma 2 it"s a multiple of [a1,...,an]. It"s also a multiple ofan+1, so [[a1,...,an],an+1]??[a1,...,an,an+1].

On the other hand, fori= 1,...,n,

a i??[a1,...,an] and [a1,...,an]??[[a1,...,an],an+1]. 1

Therefore,

a i??[[a1,...,an],an+1].

Obviously,

a n+1??[[a1,...,an],an+1].

Thus, [[a1,...,an],an+1] is a common multiple of all theai"s. Since [a1,...,an,an+1] is the least common

multiple, Lemma 2 implies that [a1,...,an,an+1]??[[a1,...,an],an+1]. Since I have twopositivenumbers which divide one another, they"re equal: [[a1,...,an],an+1] = [a1,...,an,an+1].

This proves the claim.

Returning to the proof of the induction step, I have [a1,...,an,an+1] = [[a1,...,an],an+1] = [a1···an,an+1] =a1···anan+1.

The second equality follows by the induction hypothesis (the statement forn). The third equality follows

from Lemma 1 and the result forn= 2. As an example, 6, 25, and 7 are relatively prime (in pairs). The least common multiple is [6,25,7] =

1050 = 6·25·7.

Theorem.(The Chinese Remainder Theorem) Supposem1,...,mnare pairwise relatively prime (that is, (mi,mj) = 1 fori?=j). Then the following system of congruences has a unique solution mod m

1m2···mn:

x=a1(modm1) x=a2(modm2) x=an(modmn)

Notation.

x

For example,

x

This is a convenient (and standard) notation for omitting a single variable term in a product of things.

Proof.Define

p k=m1···?mk···mn. That is,pkis the product of them"s withmkomitted. By Lemma 1, (pk,mk) = 1. Hence, there are numberssk,tksuch that s kpk+tkmk= 1.

In terms of congruences,

s kpk= 1 (modmk).

Now let

x=a1p1s1+a2s2p2+···+anpnsn. 2 Ifj?=k, thenmk|pj, so modmkall the terms but thek-th term are 0 modmk: x=akpksk=ak·1 =ak(modmk).

This proves thatxis a solution to the system of congruences (and incidentally, gives a formula forx).

Now suppose thatxandyare two solutions to the system of congruences. x=a1(modm1) andy=a1(modm1) x=a2(modm2) andy=a2(modm2) x=an(modmn) andy=an(modmn) Then x=ak=y(modmk) sox-y= 0 (modmk) ormk|x-y.

Thus,x-yis a multiple of all them"s, so

[m1,...,mn]|x-y. But them"s are pairwise relatively prime, so by Lemma 3, m That is, the solution to the congruences is unique modm1···mn.

Example.Solve

x= 2 (mod 4) x= 7 (mod 9). (4,9) = 1, so there is a unique solution mod 36. Following the constructionofxin the proof, p

1= 9,9·1 = 1 (mod 4),sos1= 1

p

2= 4,4·7 = 1 (mod 9),sos2= 7

Solution:

x=a1p1s1+a2p2s2= 18 + 196 = 214 = 34 (mod 36).

Example.Solve

x= 3 (mod 4) x= 1 (mod 5) x= 2 (mod 3).

The moduli are pairwise relatively prime, so there is a unique solution mod 60. This time, I"ll solve the

system using an iterative method. x= 3 (mod 4),sox= 3 + 4s.

Butx= 1 (mod 5), so

3 + 4s= 1 (mod 5)

4s= 3 (mod 5)

4·4s= 4·3 (mod 5)

s= 2 (mod 5) s= 2 + 5t 3

Hence,

x= 3 + 4s= 3 + 4(2 + 5t) = 11 + 20t.

Finally,x= 2 (mod 3), so

11 + 20t= 2 (mod 3)

20t=-9 = 0 (mod 3)

2t= 0 (mod 3)

2·2t= 2·2 (mod 3)

t= 0 (mod 3)

Hence,t= 3u.

Now put everything back:

x= 11 + 20t= 11 + 20(3u) = 11 + 60u,orx= 11 (mod 60).

Example.Calvin Butterball keeps pet meerkats in his backyard. If he divides them into 5 equal groups, 4

are left over. If he divides them into 8 equal groups, 6 are left over. If he divides them into 9 equal groups,

8 are left over. What is the smallest number of meerkats that Calvin could have?

Letxbe the number of meerkats. Then

x= 4 (mod 5) x= 6 (mod 8) x= 8 (mod 9) Fromx= 4 (mod 5), I getx= 4 + 5a. Plugging this into the second congruence, I get

4 + 5a= 6 (mod 8)

5a= 2 (mod 8)

5·5a= 5·2 (mod 8)

25a= 10 (mod 8)

a= 2 (mod 8)

Hence,a= 2 + 8b. Plugging this intox= 4 + 5agives

x= 4 + 5(2 + 8b) = 14 + 40b.

Plugging this into the third congruence, I get

14 + 40b= 8 (mod 9)

40b=-6 (mod 9)

4b= 3 (mod 9)

7·4b= 7·3 (mod 9)

28b= 21 (mod 9)

b= 3 (mod 9) Hence,b= 3 + 9c. Plugging this intox= 14 + 40bgives x= 14 + 40(3 + 9c) = 134 + 360c. The smallest positive value ofxis obtained by settingc= 0, which givesx= 134. 4

You can sometimes solve a system even if the moduli aren"t relatively prime; the criteria are similar to

those for solving system of linear Diophantine equations.

Theorem.Consider the system

x=a1(modm1) x=a2(modm2). (a) If (m1,m2)? |a1-a2, there are no solutions. (b) If (m1,m2)|a1-a2, there is a unique solution mod [m1,m2]. Note that if (m1,m2) = 1, case (b) automatically holds, and [m1,m2] =m1m2- i.e. I get the Chinese

Remainder Theorem forn= 2.

Proof.(a) I"ll prove the contrapositive. Supposexis a solution to the system of congruences, so x=a1(modm1) andx=a2(modm2). The first congruence givesx-a1= 0 (modm1), som1|x-a1. Similarly,m2|x-a2. But (m1,m2)|m1 and (m1,m2)|m2, so (m1,m2)|x-a1and (m1,m2)|x-a2.

Therefore,

(m1,m2)|(x-a2)-(x-a1) =a1-a2. This proves the contrapositive of the assertion, so (a) is true. (b) First, suppose that ifxandyare solutions to the system. x=a1(modm1) andy=a1(modm1) givex-y= 0 (modm1). Thus,m1|x-y. Similarly,m2|x-y. Sincex-yis a multiple ofm1andm2, it is a multiple of [m1,m2]. Thus, x-y= 0 (mod [m1,m2]),sox=y(mod [m1,m2]). Thus, any two solutions are congruent mod [m1,m2]. Now suppose (m1,m2)|a1-a2, soa1-a2=k(m1.m2) for somek?Z. Note that ?m1 (m1,m2),m2(m1,m2)? = 1.

It follows that

m1 (m1,m2)is invertible modm2(m1,m2), so there is an integerpsuch that p m1 (m1,m2)= 1?quotesdbs_dbs3.pdfusesText_6

[PDF] chinese remainder theorem examples

[PDF] chinese remainder theorem for polynomials

[PDF] chinese remainder theorem notes

[PDF] chinese remainder theorem online solver

[PDF] chinese remainder theorem pdf

[PDF] chinese remainder theorem practice

[PDF] chinese remainder theorem proof

[PDF] chinese remainder theorem proof in ring theory

[PDF] chinese remainder theorem proof math

[PDF] chinese remainder theorem proof pdf

[PDF] chinese remainder theorem proof rings

[PDF] chinese remainder theorem questions

[PDF] chinese remainder theorem solution

[PDF] chinese remainder theorem solve

[PDF] chinese remainder theorem to solve congruences