Wednesday, August 27, 2008

Wednesday Math, Vol. 36: The Chinese Remainder Theorem

'Splained with coconuts and a monkey.

You have a pile of coconuts. If you decide to split up the pile evenly into three smaller piles, there will be one coconut left over, which you will throw to the monkey. (Be careful, the monkey is a baby, and only slightly larger than the coconut.)

If you decide to split the pile into four equal piles, there will be three left over, which you will throw to the monkey. That's a lot of coconuts for a little monkey. I hope he has friends he can share with.

If you want to make five equal piles, there will be one left over, and I think by now you now what we do with the leftover coconuts.

What is the minimum number of coconuts that can be in the pile?

This problem is an example of the Chinese Remainder Theorem, a problem in number theory whose best known solution came from an ancient Chinese text, not surprisingly. The number of different ways we want to split up the original bunch is not a limiting factor. We could split the pile up into any number of equal piles, but the numbers have to be relatively prime, which means that if I pick any two of the numbers, the biggest number that divides them both is one. For example, since I said that there are three left over if I split the bunch into four piles, I know what would happen if I split it into two piles. I would lump two of the 1/4 piles together into the left pile, the other two 1/4 piles into the right pile, and throw one of the three leftovers into the left and one into the right and one to the monkey. Because the biggest number that divides into 2 and 4 is 2, they are not relatively prime, and that puts a damper on what we can do with the method we are going to use.

So let's solve this problem, starting with the piles of three and piles of four. since 3x4 = 12, we only have to check a few possible solutions.

Numbers that I can divide by 3 with 1 left over are 1, 4, 7, 10, ... etc.
Numbers I can divide by 4 with 3 left over are 3, 7, 11, ... etc.

The first number on both lists is 7. This means that if I divided the piles into twelve equal parts, there will be 7 left over. The numbers on that list are 7, 19, 31, 43, 55, ... etc.

Now we need to look at numbers divisible by 5 that will have 1 left over, but we only have to check up to 60, which is 5x12. That list is 1, 6, 11, 16, 21, 26, 31, 36, 41, 46, 51, 56, ... etc. The number that is on both the five list and the twelve list is 31. That means that there were 31 coconuts in the original pile, because I asked for the minimum number. Any number you can divide by 60 with 31 left over would also work, so that list is 31, 91, 151, 211, ... etc.

(Note: This concept is tied into the idea of modulo arithmetic, which I 'splained way back in November in Volume 5 of Wednesday math.)

2 comments:

Karlacita! said...

Oh this math is very inters ... look at the monkey!!!!

Wait, back to the math - why do you multiply 3x4 first, but not 5 when ... oh look at dis mmmmminkey.

Oh leetle monkey monkey! He can has all coconutz!

dguzman said...

You had me at the cute little monkey. Sadly, I never made it to the maths. But I feel 'splained to anyway, which is all that counts!