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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.