12,881,671 members (32,459 online)

#### Stats

42.2K views
14 bookmarked
Posted 23 Sep 2008

# 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.```

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.