Problem 27

Problem 27 : The Chinese Remainder Theorem

I have been meaning to write this out for a long time now. This is a powerful theorem that to me allows one to effectively deduce the subspace of solutions to a series of congruence relations. As far as history goes, the earliest known statement of the theorem is present in the 3rd-century book Sun-tzu Suan-ching by Sun-tzu. Here is an embedded calculator for playing around with 2 congruences.

Theorem Statement

Suppose that we have a sequence of k natural numbers n1,n2,nk that are relatively prime i.e. their greatest common divisor, gcd (ni,nj)=1ij.

Then the following system of equations,

xa1(modn1)xak(modnk)

has a unique solution modulo n1.n2.n3nk.

The Modulo Inverse

Before beginning the proof, I would like to define the modulo inverse. The modulo inverse say, x of a w.rt. m may be uniquely defined under certain conditions that will be clear soon.

a.x1(modm)

Using the definition of modulo, ax1 should be a multiple of m.

(ax1)=myaxmy=1

for some integer y. A careful look at the expression reveals that if a,m are not relatively prime or equivalently, gcd(a,m)1, we can find a divisor d>1 such that,

adxmdy=1d

Now we have an issue, because LHS is an integer but the RHS is a fraction. So, there is no solution for integers x and y.

So, the condition for modulo inteverse of a w.r.t. m to exist, the condition that naturally arises from the definition is gcd(m,a)=1.

Proof

Let N=Πi=1kni be the product of the relatively prime sequence ni. To make this problem tractable, we need to uniquely consider the influence of each congruence relation in the system of congruences provided in the Theorem’s statement. To this end, we can define Ni=Nni such that Ni is a product of all the nj’s for ji.

This allows us to claim that xiNixi1(modni). Where we simply used the fact that gcd(Ni,ni)=1 along with the definition of the modulo inverse.

biNixibi(modni)

Also, by design, biNixi0(modnj) for ji.

So, the sum X=i=1kbiNixi will satisfy all the congruences. This proves the existence of the solution.

For uniqueness, we assume that distinct X,Y such that Xbj(modnj) and Ybj(modnj) for j=1k.

Then, the difference of the two XY0(modnj). Since, the sequence ni is relatively prime, the only way in which XY can be divisible by all ni is if they are also divisible by their product. So, N divides XY. Equivalently,

XY(modN)

Therefore, X and Y are the same solution modulo N.

This completes the proof.