## Best way to introduce the Chinese Remainder Theorem (to a high school student)

What do you think to be the most effective way to teach the Chinese remainder theorem to a smart high school student, which is supposed to only have a soft idea about how modular arithmetic works, and where by effective i mean "putting someone in the best position to use a mathematical result as a tool for solving problems"? Please note that the answer "it should come with a better understanding of modular arithmetic" is not a valid answer (even if i support this point of view actually), because that is something that is going come with undergraduate studies (or a really smart high school student). I'm not asking about a magic wand, just some suggestion about what you consider the most insightful examples or effective ideas. Please note that while being an obvious result for those that are used to it, this theorem requires some examples and exercises to be grasped by a beginner. Thanks!

-
community wiki? – Pietro Majer Oct 20 2010 at 16:32
Motivate and explain first linear equations «modulo $n$», and the consider systems thereof. – Mariano Suárez-Alvarez Oct 20 2010 at 16:34
The only version I can ever remember is the version for (modules over) commutative rings (along with the easy proof). I always have to rederive the classical statement. – Harry Gindi Oct 20 2010 at 17:06
I don't see how Harry's comment is helpful for the topic being asked. Maurizio, as far as examples go, look at answers to the question mathoverflow.net/questions/10014/… for many ways CRT can be used. Some of these might be interesting to the students you have in mind. – KConrad Oct 20 2010 at 17:44
I would also add that one's approach might vary, depending on whether the student is taking math(s) as honours or as part of another degree. In the former case there might be a bit more room to go abstract as per Todd Trimble's remarks. – Yemon Choi Oct 20 2010 at 19:05

What things like partial fractions decompositions (in resolving rational functions) are really all about is the algebra surrounding the Chinese remainder theorem. Often when I've taught this sort of thing to calculus students, I get them to try to write, say, 5/21 as a sum of integral multiples of 1/3 and 1/7, or something like that, and algebraically we are doing something similar with partial fractions. It's sort of fun thinking about all this methodically, from algebraic first principles: how to do it in a principled way will eventually get one into idempotents of rings $\mathbb{Z}/n$ or $\mathbb{R}[x]/(q(x))$.

-

A healthy approach is maybe starting form applications. Here and here you can find a list of very interesting topics.

-

One simple approach would be to build up to it. The chineze reminding theorem can be basically reduced first to

$$x \equiv a \mod n$$ $$x \equiv b \mod m$$

has solutions for all $(a,b)$ whenever gcd $(m,n)=1$.

But this is equivalent to the fact that $b-a$ can be written in the form: $b-a=km+ln \,.$ (The solution then is $x= b-ln=a+km$).

Now to motivate this problem, one could use a standard watter-containers problem (the students usually like them): Given two containers, one of 3l and one of 5l, a watter tap and a sink, get exactly 4l in one container.

The following is a a possible motivational approach:

Cover the euclidian and the extended euclidian algorithm.

Cover the following generalisation of the water-containers problem: Given two containers, one of m liters and one of n liters, with gcd$(m,n)=1$; a watter tap and a sink, wecan get any desired integer amount of liters in one container.

Prove that $$x \equiv a \mod n$$ $$x \equiv b \mod m$$ always has solution. Also note that using the extende euclidian algorithm we can find a solution to $b-a=km+ln \,.$ and thus we can find one $x= b-ln=a+km$ (depending by the strength of the student you migth want to find or not ALL the solutions).

Observe that the system

$$x \equiv a \mod n$$ $$x \equiv b \mod m$$ $$x \equiv c \mod p$$

can be reduced to the following two systems $$x_0 \equiv a \mod n$$ $$x_0 \equiv b \mod m$$

and $$x \equiv x_0 \mod mn$$ $$x \equiv c \mod p$$

Since this way you can always reduce effectively the sytem by one equation at a time, you don't need to prove the Chinese Reminder Theorem in the general case, but you'll probably need to cover a case with 3 and a case with 4 equations( many students would probably understand the reduction from 3 to 2, but struggle on their own with the reduction from 4 to 3).

-

There are some classic puzzles that are most easily solved using the CRT. For example, there's the one about the monkey and the coconuts (you know—three sailors have some coconuts, and each one in turn gets up in the middle of the night, divides the coconuts into three piles, tosses the odd coconut to the monkey, etc.) Or there's Brahmagupta's puzzle:

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?

-