Chinese Remainder Theorem

From Notes
(Redirected from Chinese remainder theorem)
Jump to navigation Jump to search

Let p and q be positive integers such that gcd(p,q)=1.

For two integers x and y, there exists an integer a such that

a≡xmodpa≡ymodq

if b satisfies the same equivalences as a above, then

a≡bmodpq

Namely,

a≡xq(1q(modp))+yp(1p(modq))(modpq)


Proof

Since gcd(p,q)=1, there exist integers p′ and q′ such that

gcd(p,q)=1=pp′+qq′

In particular, we have

qq′≡1modppp′≡1modq

Multiply both sides of the equivalence by x and y respectively…

xqq′≡xmodpypp′≡ymodq

The integer a represents the sum of these two equivalences.

a=ypp′+xqq′

This is true because

ypp′+xqq′≡0+xmodpypp′+xqq′≡y+0modq∴a≡xmodpa≡ymodq

Suppose another integer a′ also satisfies the equivalences above:

a′≡xmodpa′≡ymodq

Therefore for some k

a≡a′modp⟶a−a′=kp

However, a−a′ is divisible by both p and q, which means that kp must also be divisible by q.

kp≡0modpobviouslykp≡0modq

p and q are coprime (gcd(p,q)=1; they do not divide each other), so the second equivalence implies that k must be divisible by q.

Therefore, a−a′ must be divisible by pq, so as claimed,

a≡a′modpq
Q.E.D.