## 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 r_{1}, r_{2}, r_{3} 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 n_{1}, n_{2}, n_{3 }such that:

n_{1 }mod a = 1 and n_{1 }mod bc = 0

n_{2} mod b = 1 and n_{2} mod ac = 0

n_{3} mod c = 1 and n_{3} mod ab = 0

Then N_{1} = n_{1}*r_{1} + n_{2}*r_{2} + n_{3}*r_{3}, N_{0} = N_{1} mod abc, N = N_{0} + abc*n where n=0,1,2...

For example, we have N = 3x+2 = 5y+3 = 7z+2

n_{1} = 35u = 3v+1 = 70 when u=2, v=23

n_{2} = 21u = 5v+1 = 21 when u=1, v=4

n_{3} = 15u = 7v+1 = 15 when u=1, v=2

N_{1} = 70*2 + 21*3 + 15*2 = 233

N_{0} = 233 mod (3*5*7) = 23

## A New Solution

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

Firstly we solve a * x + r_{1} = b * y + r_{2}, it can be rewritten as ax = by + r.

Notice that if `x`_{0},y_{0}

is a solution of `ax = by + 1`

, then `x = bn + rx`_{0},y = an + ry_{0}

is a solution of `ax = by + r `

for any integer `n`

.

Because a(bn+rx_{0}) = b(an+ry_{0})+r

=> abn + arx_{0} = ban + bry_{0} + r

=> ax_{0} = by_{0} + 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`_{0},y = an + ry_{0}

we can let `x`_{1} = rx_{0} mod b

and `y`_{1} = ry_{0} mod a

.

x_{1},y_{1} will be the smallest numbers fulfil a * x + r_{1} = b * y + r_{2}.

Let `r`_{4} = ax_{1} + r_{1} = by_{1} + r_{2}

, we can see that solutions are of the form` abu + r`_{4}

.

Then we solve `abu + r`_{4} = cz + r_{3}

and get `u`_{1},z_{1}

.

Finally `N`_{0} = abu_{1} + r_{4} = cz_{1} + r_{3}

.

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

=> x_{0}-y_{0}=3,2y_{0}-x_{0}=1

=> x_{0}=7,y_{0}=4

=> r_{4} =3*7+2=23

Then we solve 15u+23=7z+2 => 7z=15u+21 (here r=21, we are ready to know ru_{0} mod 7 = 0),

7z=15u+1 => 7(z-u)=8u+1 => 7(z-2u)=u+1 => u_{0}=6,z_{0}=13 => u_{1} = 21*6 mod 7 = 0 => N_{0}=15*0+23=23.

## Using the Code

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

public class RemainderProblem
{
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;
}
public static int LCM(int a, int b)
{
int gcd = GCD(a, b);
return a * b / gcd;
}
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));
}
}
public static void Solve(int a, int b, int c, out int x1, out int y1)
{
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;
}
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;
}
}
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);
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);
}
}

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++)
{
listBoxN.Items.Add(n0 + t * i);
}
listBoxN.Items.Add("...");
}
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