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:
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
