Chinese remainder theorem proof
We first prove the following lemma: if
a≡b(modp) |
a≡b(modq) |
gcd(p,q)=1 |
then
a≡b(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 equation 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 a≡b(modpq), thus completing the lemma.
Now, to prove the Chinese remainder theorem, we first show that yi must exist for any natural i where 1≤i≤n. If
yiPpi≡1(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 product of each pj (j∈ℕ, 1≤j≤n) 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∈ℕ, 1≤j≤n. For any i∈ℕ, 1≤i≤n, either i≠j or i=j. If i≠j, then
aiyiPpi=(aiyiPpipj)pj |
so divides , and we know
Now consider the case that . was selected so that
so we know
Suppose we have some
This implies that for some ,
So, for any , we know that
so . Since congruence is transitive, must in turn satisfy all the original congruences.
Likewise, suppose we have some that satisfies all the original congruences. Then, for any , we know that
and since
the transitive and symmetric properties of congruence imply that
for all . So, by our lemma, we know that
or
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 |