Chinese Remainder Theorem

Date: 06/27/98 at 02:07:15
From: Jerome Burns
Subject: Number Theory

The teacher has some apples to distribute to her students. If she 
gives all of the apples to the 13 students in her first class she will 
have 4 left. If she gives all of the apples to the 29 students in her 
second class she will have 9 left. If she gives all of the apples to 
the 37 students in her third class she will have 16 left. Whichever 
class she gives the apples to, she will give each student the same 
number of apples. What is the smallest number of apples the teacher 
can have? 

That is the problem, but it seems too easy. The answer is 17, right? 
But how does it fit into the Chinese Remainder Theorem?

Thank you for your help.

Jerome

Date: 06/27/98 at 14:01:18
From: Doctor Joe
Subject: Re: Number Theory

Dear Jerome,

Since you know what the Chinese Remainder Theorem is (applied to the 
set of integers; note that there is a Chinese Remainder Theorem for 
General Rings), I shall deal with the setting up of the system of 
equations so that you might use the Chinese Remainder Theorem.

Let the number of apples the teacher has be n.  Note that n is a 
positive integer.

For the first class, supposing each student gets k1 apples. Then, we 
may write:   n = 13(k1) + 4.

Since k1 is an integer, in the language of integers modulo, I shall 
write reduce n to 4 modulo 13, i.e.

             n = 4 (mod 13)

Note that 13 is a prime.  That's useful later.

Now for the second class, we can similarly set up:

             n = 9 (mod 29)

For the third class, we can set up:

             n = 16 (mod 37)

Note that 13, 29, 37 are all coprime to one another; i.e. they have no 
common divisors other than 1.

This is the criterion for using the Chinese Remainder Theorem.

Hope this helps.  Please feel free to email me again.

- Doctor Joe, The Math Forum
  http://mathforum.org/dr.math/