Chinese remainder theorem proof


We first prove the following lemma: if

ab(modp)
ab(modq)
gcd(p,q)=1

then

ab(modpq)

We know that for some k, a-b=kp; likewise, for some j, a-b=jq, so kp=jq. Therefore kp-jq=0.

It is a well-known theorem that, given a,b,c,x0,y0 such that x0a+y0b=c and d=gcd(a,b), any solutions to the diophantine equationMathworldPlanetmath ax+by=c are given by

x=x0+bdn
y=y0+adn

where n.

We apply this theorem to the diophantine equation kp-jq=0. Clearly one solution of this diophantine equation is k=0,j=0. Since gcd(q,p)=1, all solutions of this equation are given by k=nq and j=np for any n. So we have a-b=npq; therefore pq divides a-b, so ab(modpq), thus completing the lemma.

Now, to prove the Chinese remainder theoremMathworldPlanetmathPlanetmathPlanetmath, we first show that yi must exist for any natural i where 1in. If

yiPpi1(modpi)

then by definition there exists some k such that

yiPpi-1=kpi

which in turn implies that

yiPpi-kpi=1

This is a diophantine equation with yi and k being the unknown integers. It is a well-known theorem that a diophantine equation of the form

ax+by=c

has solutions for x and y if and only if gcd(a,b) divides c. Since Ppi is the productPlanetmathPlanetmath of each pj (j, 1jn) except pi, and every pj is relatively prime to pi, Ppi and pi are relatively prime. Therefore, by definition, gcd(Ppi,pi)=1; since 1 divides 1, there are integers k and yi that satisfy the above equation.

Consider some j, 1jn. For any i, 1in, either ij or i=j. If ij, then

aiyiPpi=(aiyiPpipj)pj

so pj divides aiyiPpi, and we know

aiyiPpi0(modpj)

Now consider the case that i=j. yj was selected so that

yjPpj1(modpj)

so we know

ajyjPpjai(modpj)

So we have a set of n congruencesMathworldPlanetmathPlanetmathPlanetmathPlanetmath modpj; summing them shows that

i=1naiyiPpiai(modpj)

Therefore x0 satisfies all the congruences.

Suppose we have some

xx0(modP)

This implies that for some k,

x-x0=kP

So, for any pi, we know that

x-x0=(kPpi)pi

so xx0(modpi). Since congruence is transitiveMathworldPlanetmathPlanetmathPlanetmathPlanetmathPlanetmath, x must in turn satisfy all the original congruences.

Likewise, suppose we have some x that satisfies all the original congruences. Then, for any pi, we know that

xai(modpi)

and since

x0ai(modpi)

the transitive and symmetric properties of congruence imply that

xx0(modpi)

for all pi. So, by our lemma, we know that

xx0(modp1p2pn)

or

xx0(modP)
Title Chinese remainder theorem proof
Canonical name ChineseRemainderTheoremProof
Date of creation 2013-03-22 11:59:11
Last modified on 2013-03-22 11:59:11
Owner vampyr (22)
Last modified by vampyr (22)
Numerical id 7
Author vampyr (22)
Entry type Proof
Classification msc 11D79