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

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

We switch to modular notation again:

So

Therefore there is an integer number

In modular that means

And that gives us the solution:

Let me summarize:

For me, what seemed the most hard to understand issue was how does

*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).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.
## 0 comments:

Post a Comment