Associated Topics || Dr. Math Home || Search Dr. Math

### 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?

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/
```
Associated Topics:
High School Number Theory

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search