What is most motivating way of introducing this function? Does it in itself have any real life applications that have an impact. I can only think of a^phi(n)=1 (mod n) which is powerful result but is this function used elsewhere.
[Math] the use of Euler Totient or Phi Function
educationelementary-number-theorynumber theory
Related Solutions
I'm surprised everyone seems to be in general agreement that the domino analogy is good. It seems poor to me: what have dominos got to do with proving things? It's a nice metaphor, but it has simply nothing to do with the issue at hand. I don't remember it having been helpful when I came across it before understanding induction, either. Maybe I'm a special case in that regard.
Which brings me to my answer: I would look for theorems that admit a particularly simple inductive proof. I would also relate those proofs to the students in a more conversational language. Ie, rather than:
First, prove it for 0. Then, prove that if it is true for n, it is true for n + 1. So it must be true for all n.
There are two points here that may be confusing:
- The notion of proving an "if then" statement. I suspect many students initially find it hard to see that an "if then" can even be considered a "statement" at all, people are more used to thinking of them as combinations of statements. The idea of proving "A if B", without even considering whether A is true, seems bizarre. Supposing I proved that if there were a unicorn, it would like tea.
- The use of a variable $n$ may be an unnecessary distraction for some students with low mathematical ability, many students remain uncomfortable with variables all the way through high school. This is admittedly a less important point.
To beat issue (1), work by example. State a simple theorem and propose to prove that it's true for all numbers (don't say "for all n"! Just point to the number in the statement, written on the board, and say "we'll prove it's true no matter what this is"). Prove it for zero. Then, without proving or stating the inductive step as a separate statement, go right ahead show "well because it's true for 0, it must be true for 1, because...". Then, "but because it's true for 1, we can use the same argument to show it must be true for 2, after all...". Repeat maybe once more. Finish up by pointing out that as the same argument works for any number, you can keep going as far as you need to and the statement is true for all numbers.
Imagine you had never been taught induction, that you were living in an age before abstract mathematics, and remember the principle meaning of the word proof. A proof is what you use to convince your fellow human that something must be true. If you were simply trying to do that, you wouldn't be fussing around with separating out the inductive step as a proposition in its own right, you'd use the much more easily grasped (and much more convincing!) sort of proof by example above. The illustration of why that means it's true for all $n$ is in the language of the proof itself: it's true because we can keep doing the thing we just did two or three times.
I call the CRT the "modular coordinates theorem".
If you have a bunch of numbers $m_1...m_n$, then any number $k$ can be given a "coordinate" by giving the $n$-tuple of its remainders modulo each $m_i$: $(k \mod m_1,\ ...\ k \mod m_n)$. The question is: can we uniquely determine a number from its coordinate tuple?
Well, of course not, not if our number $k$ is any arbitrary integer. There's only $\prod m_i$ possible tuples and an infinite number of values of $k$. In fact, we can show that the coordinate tuples are $\prod m_i$-periodic as follows. First note that the coordinate tuple of $k$ uniquely determines the coordinate of $k+1$, since you can obtain the latter by adding $1$ and taking a remainder to each value in the coordinate tuple of $k$. Next, obviously the coordinate tuple of $\prod m_i$ is $0$ - it's congruent to $0$ modulo any of the $m_i$. Any sequence that both deterministic (every value depends only on the previous value) and eventually goes back to its initial value is obviously periodic after that point.
So if our coordinate system resets and starts repeating after $\prod m_i$, then we can certainly only hope to determine a number $k$ from its coordinates if we know that $k$ is between $0$ and $\prod m_i$. But can we always do that? Maybe some numbers in that range will have the same coordinate.
First of all, we'll obviously run into problems if the $m_i$ aren't pairwise distinct. Imagine if we had $m_1=m_2=2$. Then the coordinate "tuple" of $k$ is really just a single value - the remainder of $k$ modulo $2$. You certainly can't uniquely identify any number between $0$ and $m_1m_2=4$ with that information. If the coordinate is $0$ then $k$ could be either $0$ or $2$, and if it's $1$ it could be either $1$ or $3$.
We're also in trouble if $m_1=2$ and $m_2=4$, as the following table shows:
As you can see, there are multiple numbers that share coordinate tuples. The trouble here is that, although the coordinate tuples are indeed $m_1m_2=8$-periodic, that's not their smallest period. They're also $4$-periodic, and $4$ is the smallest period of the coordinate tuples. Furthermore, you can see that for $k<4$, we can uniquely determine $k$ from its coordinates. $4$, incidentally, happens to be the LCM of $m_1$ and $m_2$.
We can show in general that the coordinate tuples modulo $m_1...m_n$ are injective between $0$ and $\mathrm{LCM}(m_1,...m_n)$, i.e. numbers in that range are uniquely determined by their coordinate tuple. Furthermore, this is also the maximum range on which coordinates are injective. This in particular implies the standard statement of the Chinese Remainder Theorem, since the LCM of a set of coprime integers is their product.
Proof:
My favorite proof is similar to the argument I gave above, showing that the coordinates are $\prod m_i$-periodic. Let's say we're working with the modulos $m_1...m_n$. I'll abbreviate $\mathrm{LCM}(m_1,...m_n)$ by $M$. Obviously, the coordinate tuples are $M$-periodic, since the coordinate tuple of $M$ is all zeros. By the above argument, the coordinate tuples must repeat after that point. Also, is the coordinate tuple of $k$ is all zeros, then $k$ must be a common multiple of $m_1, ... m_n$. Therefore, there is no number less than $M$ whose tuple is all zeros.
Now, suppose we had $k < k' < M$, such that the coordinate tuples of $k$ and $k'$ were identical. Again, since the coordinate tuple of a number determines the coordinate tuple of the next number, we know that the coordinate tuples must repeat after $k'$. In particular, the coordinates of the numbers $k...k'$ are going to repeat infinitely. Since $M>k'$, this means that the coordinate of $M$ must be the same as the coordinate of some number between $k$ and $k'$. But this is impossible, since the coordinate tuple of $M$ is all zeros, and no smaller number has all zero coordinates, as was shown previously. Therefore the coordinates of $k$ and $k'$ are not identical. $\blacksquare$
This "coordinate system" point of view leads to the interesting question as to, if we had an infinite set $m_1, m_2, ...$ of coprime modulos (say, the set of prime numbers), would the resulting coordinate system be injective over $\Bbb N$?
Best Answer
RSA, or public-key cryptography is one of them.