Chinese Remainder Problem

Chinese remainder problem

The Chinese remainder problem is that integers a,b,c are pairwise coprime, 
N leave remainders r1, r2, r3 when divided by a, b, c respectively, find out N.

The problem can be described by the equation: N = a * x + r1 = b * y + r2 = c * z + r3


Traditionally this problem is solved by Chinese remainder theorem, using the following approach:
Find numbers n1, n2, n3 such that:
 n1 mod a = 1 and n1 mod bc = 0
 n2 mod b = 1 and n1 mod ac = 0
 n3 mod c = 1 and n1 mod ab = 0
Then N = n1*r1 + n2*r2 + n3*r3, N0 = N mod abc, N = N0 + abc*n where n=0,1,2...

For example, we have N = 3x+2 = 5y+3 = 7z+2
n1 = 35u = 3v+1 = 70 when u=2, v=23
n2 = 21u = 5v+1 = 21 when u=1, v=4
n3 = 15u = 7v+1 = 15 when u=1, v=2
N = 70*2 + 21*3 + 15*2 = 233
N0 = 233 mod (3*5*7) = 23

Now I present a method that can compute the smallest solution N0 directly, it is easy to carry out 
both by human and by computer.

Firstly when solve a * x + r1 = b * y + r2, it can be rewrite as ax = by + r.
And we notice that if x0,y0 is a solution for ax = by + 1 then x=bn+cx0,y=an+cy0 is a solution for ax = by + r.
Because a(bn+rx0) = b(an+ry0) +r => abn + arx0 = ban + bry0 + r => ax0 = by0 + 1.

So the problem come down to solve ax = by + 1.
a and b should be coprime, othewise solve (a/d)x = (b/d)y + 1 first.
If a > b we can solve (a-b)x = by' + 1, y' = y - x first, say the solution is x,y', then y = y'+x.
Similarly this can be done when a < b. Repeat the procedure, a and b become smaller and smaller,
When a = 1 we can let y = 1 and x = b + 1, else if b = 1 we can let x = 1 and y = a - 1.

Since x=bn+rx0,y=an+ry0 we can let x1 = rx0 mod b and y2 = ry0 mod a.
x1,y1 will be the smallest number fulfil a * x + r1 = b * y + r2.
Let r4 = ax1 + r1 = by1 + r2, we can see that N = abu + r4.
Then we solve abu + r4 = cz + r3 and get u1,z1.
Finally N0 = abu1 + r4 = cz1 + r3.

For example, we solve N = 3x+2 = 5y+3 = 7z+2 again.
Firstly solve 3x=5y+1 => 3(x-y)=2y+1 => x-y=2(y-(x-y))+1 => x0-y0=3,2y0-x0=1 => x0=7,y0=4 => r4 =3*7+2=23
Then solve 15u+23=7z+2 => 7z=15u+21, (here r=21, we are ready to know ru0 mod 7 = 0)
7z=15u+1 => 7(z-u)=8u+1 => 7(z-2u)=u+1 => u0=6,z0=13 => u1 = 21*6 mod 7 = 0 => N0=15*0+23=23.