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

## No comments:

Post a Comment