Saturday, May 09, 2009

The Chinese Remainder Theorem - Modular arithmetic

I don't pretend to know much about mathematics, but that should make it really easy to follow this article, because if I understood it, then so should you. I was watching this four episode show called Story of Maths. Its first episode was pretty nice and I started watching the second. The guy presented what he called the Chinese Remainder Theorem, something that was created and solved centuries before Europeans even knew what math was. It's a modular arithmetic problem. Anyway, here is the problem:

A woman selling eggs at the market has a number of eggs, but doesn't know exactly how many. All she knows is that if she arranges the eggs in rows of 3 eggs, she is left with one egg on the last row, if she uses rows of 5, she is left with 2 eggs, while if she uses rows of 7, 3 eggs are left on the last row. What is the (minimum) number of eggs that she can have?
You might want to try to solve it yourself before readind the following.

Here is how you solve it:

Let's call the number of eggs X. We know that X 1(mod 3) 2(mod 5) 3(mod 7). That means that there are three integer numbers a, b and c so that X = 3a+1 = 5b+2 = 7c+3.

3a = 5b+1 from the first two equalitites.
We switch to modular notation again: 3a 1(mod 5). Now we need to know what a is modulo 5 and we do this by looking at a division table or by finding the lowest number that satisfies the equation 3a = 5b+1 and that is 2. 3*2 = 5*1+1.

So 3a 1(mod 5) => a 2(mod 5).

Therefore there is an integer number m so that a = 5m+2 and 3a+1 = 7c+3. We do a substitution and we get 15m+7 = 7c+3.

In modular that means 15m+7 3(mod 7) or (7*2)m+7+m 3(mod 7). So m 3(mod 7) so there is an integer n that satisfies this equation: m = 7n+3. Therefore X = 15m+7 = 15(7n+3)+7 = 105n+52

And that gives us the solution: X 52(mod 105). The smallest number of eggs the woman had was 52. I have to wonder how the Chinese actually performed this calculation.

Let me summarize:
X 1(mod 3) 2(mod 5) 3(mod 7) =>
X = 3a+1 = 5b+2 = 7c+3 =>
3a 1(mod 5) =>
a 2(mod 5)=>
a = 5m+2 =>
X = 15m+7 = 7c+3 =>
15m+7 3(mod 7) =>
m 3(mod 7) =>
m = 7n+3 =>
X = 15(7n+3)+7 = 105n+52 =>
X 52(mod 105)

For me, what seemed the most hard to understand issue was how does 3a 1(mod 5) turn into a 2(mod 5). But we are in modulo 5 country here, so if 3a equals 1(mod 5), then it also equals 6(mod 5) and 11 and 16 and 21 and so on. And if 3a equals 6(mod 5), then a is 2(mod 5). If 3a equals 21(mod 5), then a equals 7(mod 5) which is 2(mod 5) all over again.