Click here to Skip to main content
Click here to Skip to main content
Add your own
alternative version

Tagged as

Chinese Remainder Problem

, 17 Oct 2008 CPOL
Solve the Chinese remainder problem cleverly
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.

By viewing downloads associated with this article you agree to the Terms of Service and the article's licence.

If a file you wish to view isn't highlighted, and is a text file (not binary), please let us know and we'll add colourisation support for it.

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

Liu Junfeng
Software Developer (Senior) Beyondsoft SH
China China
No Biography provided

| Advertise | Privacy | Terms of Use | Mobile
Web01 | 2.8.141223.1 | Last Updated 17 Oct 2008
Article Copyright 2008 by Liu Junfeng
Everything else Copyright © CodeProject, 1999-2014
Layout: fixed | fluid