13,087,797 members (83,179 online)
alternative version

#### Stats

44.5K views
14 bookmarked
Posted 23 Sep 2008

# Chinese Remainder Problem

, 17 Oct 2008
 Rate this:
Solve the Chinese remainder problem cleverly

## Introduction

Around A.D. 100, the Chinese mathematician Sun-Tsu solved the problem of finding those integers x that leave remainders 2, 3, and 2 when divided by 3, 5, and 7 respectively. One such solution is x = 23; all solutions are of the form 23 + 105k for arbitrary integers k.

The Chinese remainder problem says that integers a,b,c are pairwise coprime, N leaves remainders r1, r2, r3 when divided by a, b, c respectively, finding N. The problem can be described by the following equation:

N = a * x + r<sub>1</sub> = b * y + r<sub>2</sub> = c * z + r<sub>3</sub>

How can we solve this problem and how to compute it by a computer?

## Background

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 n2 mod ac = 0
n3 mod c = 1 and n3 mod ab = 0
Then N1 = n1*r1 + n2*r2 + n3*r3, N0 = N1 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
N1 = 70*2 + 21*3 + 15*2 = 233
N0 = 233 mod (3*5*7) = 23

## A New Solution

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 we solve a * x + r1 = b * y + r2, it can be rewritten as ax = by + r.
Notice that if x<sub>0</sub>,y<sub>0</sub> is a solution of ax = by + 1, then x = bn + rx<sub>0</sub>,y = an + ry<sub>0</sub> is a solution of ax = by + r for any integer n.
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.
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 if 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 + rx<sub>0</sub>,y = an + ry<sub>0</sub> we can let x<sub>1</sub> = rx<sub>0</sub> mod b and y<sub>1</sub> = ry<sub>0</sub> mod a.
x1,y1 will be the smallest numbers fulfil a * x + r1 = b * y + r2.
Let r<sub>4</sub> = ax<sub>1</sub> + r<sub>1</sub> = by<sub>1</sub> + r<sub>2</sub>, we can see that solutions are of the form abu + r<sub>4</sub>.
Then we solve abu + r<sub>4</sub> = cz + r<sub>3</sub> and get u<sub>1</sub>,z<sub>1</sub>.
Finally N<sub>0</sub> = abu<sub>1</sub> + r<sub>4</sub> = cz<sub>1</sub> + r<sub>3</sub>.

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 we 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.

## Using the Code

Here is a C# program that implements the above algorithm:

/// <summary>
/// Solve Chinese Remainder Problem
/// </summary>
public class RemainderProblem
{
/// <summary>
/// Get Greatest Common Divisor
/// </summary>
public static int GCD(int a, int b)
{
if (a > b)
{
int t = b;
b = a;
a = t;
}
int r = b % a;
while (r != 0)
{
b = a;
a = r;
r = b % a;
}
return a;
}

/// <summary>
/// Get Least Common Multiple
/// </summary>
public static int LCM(int a, int b)
{
int gcd = GCD(a, b);
return a * b / gcd;
}

/// <summary>
/// Solve ax=by+1
/// </summary>
public static void Solve(int a, int b, out int x, out int y)
{
if (b == 1)
{
x = 1;
y = a - 1;
}
else if (a == 1)
{
y = 1;
x = b + 1;
}
else if (b > a)
{
int subx;
Solve(a, b - a, out subx, out y);
x = y + subx;
}
else if (a > b)
{
int suby;
Solve(a - b, b, out x, out suby);
y = x + suby;
}
else
{
throw new Exception(String.Format
("The equation {0}x={1}y+1 has no integer solution.", a, b));
}
}

/// <summary>
/// Solve ax = by + c
/// </summary>
public static void Solve(int a, int b, int c, out int x1, out int y1)
{
/* if
a * x0 = b * y0 + 1
then
x = b * t + c * x0
y = a * t + c * y0
satisfies
a * x  = b * y  + c
so
x1 = (c * x0) mod b
y1 = (c * y0) mod a
*/
int d = GCD(a, b);
if (d > 1)
{
if (c % d != 0)
{
throw new Exception(String.Format
("The equation {0}x={1}y+{2} has no integer solution.", a, b, c));
}
a = a / d;
b = b / d;
c = c / d;
}
int x0, y0;
Solve(a, b, out x0, out y0);
x1 = (c * x0) % b;
y1 = (c * y0) % a;
}

/// <summary>
/// Solve a * x + r1 = b * y + r2
/// </summary>
public static void Solve(int a, int b, int r1, int r2, out int x1, out int y1)
{
if (r2 > r1)
{
Solve(a, b, r2 - r1, out x1, out y1);
}
else if (r1 > r2)
{
Solve(b, a, r1 - r2, out y1, out x1);
}
else
{
x1 = b;
y1 = a;
}
}

/// <summary>
/// Solve a * x + r1 = b * y + r2 = c * z + r3 = n
/// n0 = n mod t
/// </summary>
public static void Solve(int a, int b, int c, int r1,
int r2, int r3, out int n0, out int t)
{
int x1, y1;
Solve(a, b, r1, r2, out x1, out y1);
// let r4 = a * x1 + r1 = b * y1 + r2
// to satisfy n = a * x + r1 = b * y + r2
// we can see n = a * b * u + r4
int r4 = a * x1 + r1;
int x2, y2;
Solve(a * b, c, r4, r3, out x2, out y2);
n0 = c * y2 + r3;
t = LCM(LCM(a, b), c);
//n0 = n % t;
}
}

In the form, we implement the button call as:

private void buttonSolve_Click(object sender, EventArgs e)
{
try
{
int a = int.Parse(textBoxA.Text);
int b = int.Parse(textBoxB.Text);
int c = int.Parse(textBoxC.Text);
int r1 = int.Parse(textBox1.Text);
int r2 = int.Parse(textBox2.Text);
int r3 = int.Parse(textBox3.Text);
int n0, t;
RemainderProblem.Solve(a, b, c, r1, r2, r3, out n0, out t);
textBoxN.Text = n0.ToString();
textBoxT.Text = t.ToString();
listBoxN.Items.Clear();
for (int i = 0; i < 20; i++)
{
}
}
catch (Exception error)
{
MessageBox.Show(error.Message, "No solution");
}
}

## Points of Interest

The algorithm can be easily extended to solve the generalized Chinese remainder problem:

N = a<sub>1</sub> * x<sub>1</sub> + r<sub>1</sub> = a<sub>2</sub> * x<sub>2</sub> + r<sub>2</sub> = ... = a<sub>n</sub> * x<sub>n</sub> + r<sub>n </sub>

## History

• 2008-09-24 Initial submission
• 2008-10-18 Updated so that the condition a,b,c are pairwise coprime is no longer required
• 2008-10-19 Fixed the error that if a,b,c are not coprime then the period t should be the least common multiple of a,b,c

## Share

 Architect YunCheDa Hangzhou China
No Biography provided

## You may also be interested in...

 Pro

 View All Threads First Prev Next
 Buggy? Lono17524-Jan-12 9:38 Lono175 24-Jan-12 9:38
 Re: Buggy? Liu Junfeng22-Mar-12 19:46 Liu Junfeng 22-Mar-12 19:46
 Re: Buggy? Lono17522-Mar-12 19:59 Lono175 22-Mar-12 19:59
 Last Visit: 31-Dec-99 18:00     Last Update: 17-Aug-17 12:11 Refresh 1
{"found_math": false, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0}