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!
-
1$\begingroup$ Motivate and explain first linear equations «modulo $n$», and the consider systems thereof. $\endgroup$– Mariano Suárez-ÁlvarezCommented Oct 20, 2010 at 16:34
-
$\begingroup$ 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. $\endgroup$– Harry GindiCommented Oct 20, 2010 at 17:06
-
7$\begingroup$ 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. $\endgroup$– KConradCommented Oct 20, 2010 at 17:44
-
$\begingroup$ 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. $\endgroup$– Yemon ChoiCommented Oct 20, 2010 at 19:05
4 Answers
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))$.
-
1$\begingroup$ Once you have explained that, a natural next step is showing the relation with polynomial interpolation. You can think to polynomial interpolation as solving a system of "congruences modulo polynomials" of the form $p(x) \equiv y_i \mod x-x_i$, and then the similarity is apparent. Now notice that the constructive algorithm for finding a solution to the CRT is formally equivalent to Lagrange interpolation. $\endgroup$ Commented Oct 21, 2013 at 18:20
-
1$\begingroup$ @FedericoPoloni Oh, most definitely. Lagrange interpolation being all about the structure of the ring $k[x]/(g(x))$ and its idempotents, where $g(x)$ splits into linear factors with roots $x_i$. It is also interesting to consider more general $g(x)$, and how the dual of $k[x]/(g(x))$ sits in the dual of $k[x]$ (formal power series). If $g(x) = b_0 + \ldots + b_nx^n$ has $b_0 \neq 0$, and $g^\text{rev}(x) := b_n x^n + \ldots + b_n$, then $\frac1{g^\text{rev}(x)}, \frac{x}{g^\text{rev}(x)}, \ldots, \frac{x^{n-1}}{g^\text{rev}(x)}$ form a basis of this dual in the space of $k[[x]]$. (cont.) $\endgroup$ Commented Oct 21, 2013 at 20:58
-
$\begingroup$ And more generally, the Hermite interpolation (prescribing jets, not only values, at given points) $\endgroup$ Commented Oct 21, 2013 at 21:07
-
$\begingroup$ (cont.) In this way, there is a kind of duality between "Lagrange interpolation" (or more generally the structure of $k[x]/(g(x))$) and the structure of rational functions $\frac{x^i}{g^\text{rev}(x)}$ as power series calculated by partial fraction decompositions (which yield appropriate geometric series). (Typing a bit hurriedly as I have to go.) $\endgroup$ Commented Oct 21, 2013 at 21:10
One simple approach would be to build up to it. The Chinese Reminder 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 water-containers problem (the students usually like them): Given two containers, one of 3l and one of 5l, a water 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 water tap and a sink, we can 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 extended 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?
