# Solve using the Chinese Remainder Theorem

• Jun 15th 2013, 03:27 PM
Civy71
Solve using the Chinese Remainder Theorem
An old woman goes to market and a horse steps on her basket and crashes the eggs. The rider offers to pay for the damages and asks her how many eggs she had brought. She does not remember the exact number, but when she had taken them out two at a time, there was one egg left. The same happened when she picked them out three, four, five, and six at a time, but when she took them seven at a time they came out even. What is the smallest number of eggs she could have had?

• Jun 15th 2013, 07:19 PM
chiro
Re: Solve using the Chinese Remainder Theorem
Hey Civy71.

The first thing I suggest you do is write out the system of congruence equations first given your data. You will have one for each of the items including mod 2, mod 3, mod 4, mod 5, mod 6, and mod 7.
• Jun 15th 2013, 07:23 PM
HallsofIvy
Re: Solve using the Chinese Remainder Theorem
I am puzzled by this. Where did you get this problem? Obviously, whoever gave you this problem expects you to know what the "Chinese Remainder Theorem" is! If you do, why have you not at least tried to solve it yourself?
• Jun 22nd 2013, 12:40 PM
HallsofIvy
Re: Solve using the Chinese Remainder Theorem
Since this has been here a week now and we have not heard back from Civy71, if anyone is interested, the "Chinese Remainder Theorem" say, in modern language (I can't write Chinese!) "The solution to a system of equation x= a (mod n1), x= a (mod n2), ..., x= a (mod nk) (that is, x is congruent to the same thing, a, modulo k different numbers) satisfies x= a (mod m) where m is the least common multiple of n1, n2, ..., nk.

"she had taken them out two at a time, there was one egg left.[/quote]
That is, if you divide the number of eggs, n, by 2, the remainder is 1: n= 1 (mod 2)

"The same happened when she picked them out three, four, five, and six at a time'
If you divide n by 3, 4, 5, and 6, the remainder is 1: n= 1 (mod 3), n= 1 (mod 4), n= 1(mod 5), and n= 1 (mod 6).

The least common multiple of 2, 3, 4, 5, and 6 is 3(4)(5)= 60. n= 1 (mod 6) which means n is a multiple of 60 plus 1: n= 60i+ 1 for some integer i.

"but when she took them seven at a time they came out even."
n is a multiple of 7: n= 7j for some integer j. We now have n= 7j= 7j60i+ 1, or 7j- 60i= 1, a "Diophantine equation".

To solve that, note that 7 divides into 60 8 times with remainder 4: 60- 8(7)= 4.
4 divides into 7 once with remainder 3: 7- 4= 3.
3 divides into 4 once with remainder 1: 4- 3= 1.

Replace that "3" in 4- 3= 1 with 7- 4: 4- (7- 4)= 2(4)- 7= 1.
Replace the "4" in that with 60- 8(7): 2(60- 8(7))- 7= 2(60)- 17(7)= 1. But we wanted j(7)- i(60)= 1, with the subtraction reversed. Okay, us negative values: -(-2)(60)+ (-17)(7)= 1. That is, a solution to "j(7)- i(60)= 1" is j= -17, i= -2. But it is easy to see that j= -17+ 60k, i= -2+ 17k is also a solution, for any integer k: (-17+ 60k)(7)- (-2+ 17k)(60)= -121+ 420k+ 120- 420k= 1. Taking k= 1 gives j= p17+ 60= 43, i= -2+ 17= 15. n= 7j= 7(43)= 301.

And, it is easy to check: 2 divides into 301 150 times with remainder 1. 3 divides into 301 100 times with remainder 1. 4 divides into 301 75 times with remainder 1. 5 divides into 301 60 times with remainder 1, 6 divides into 301 5 times with remainder 1. And, finally, 7 divides into 301 exactly 43 times, with no remainder.