chineseremaindertheorem

Chinese Remainder Theorem

Let hcf (n1,n2,n3,…,nr)=1. Then the system of linear congruences:

x==a1 [mod n1]

x==a2 [mod n2]

x==a3 [mod n3] …

x==ar [mod nr]

has a simultaneous solution, unique modulo n1n2n3…nr

Proof:

Let n=n1n2n3…nr

Let Nk = n/nk, and Nkxk == 1 [mod nk]

Let X=a1N1x1 + a2N2x2 + … + arNrxr

Then, Ni==0 [mod nk][i<>k]

so X == akNkxk == ak.1 == ak [mod nk]

Suppose Y is another solution:

X==Y [mod nk]

=> nk|(X-Y) for each k

But, hcf (ni,nj)=1 => n1n2n3…nr|(X-Y)

=> X==Y [mod n]