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

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

2010-10-20T16:25:23Z

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!

Answer by Todd Trimble for Best way to introduce the Chinese Remainder Theorem (to a high school student)

2010-10-20T17:19:14Z

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))$.

Answer by Pietro Majer for Best way to introduce the Chinese Remainder Theorem (to a high school student)

2010-10-20T18:04:43Z

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

Answer by Nick S for Best way to introduce the Chinese Remainder Theorem (to a high school student)

2010-10-20T23:11:14Z

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:

Start with the water-container problem.

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).

Answer by Timothy Chow for Best way to introduce the Chinese Remainder Theorem (to a high school student)

2010-10-21T00:44:12Z

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?