What is the most motivating way to introduce the order of a modulo n? Apart from simplifying powers of residues is there any other use of the order? Are there any examples which have a real impact on motivation.
Also why do we teach primitive roots? What is the need for this topic? Is there a really good hook that can used to introduce primitive roots?
[Math] Why do we need primitive roots
educationelementary-number-theory
Related Solutions
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$?
RSA, or public-key cryptography is one of them.
Best Answer
Primitive roots are the equivalent of logarithms, in the sense that they allow us to translate problems about multiplication into problems about addition. In fact, if we fix a primitive root $r$ modulo $p$, then we can define $\log_r(x)$ for $x\in\mathbb Z$ as the unique $0\leq n\leq p-1$ satisfying $r^n\equiv x$. This function then satisfies:
$$\log_r(xy)\equiv\log_r(x) + \log_r(y)\mod p-1$$
Of course, we don't often need to really use such notation, it just illustrates the close connection to logarithms of real numbers. The more important thing to understand is that this establishes that problems involving modular multiplication always have an equivalent problem involving modular addition. The most obvious application of this is the problem of $n$-th roots modulo a prime $p$. Indeed, $x^n=a$ means $n\log(x)\equiv\log(a)$ modulo $p-1$, so the problem of roots reduces to the problem of division.
This may seem simple but allows many theorems to be proven easily:
There are equally many quadratic residues and non-residues modulo a prime (not counting $0$). Proof: half the multiplicative group has even index, half has odd index, and being a quadratic residue is equivalent to having even index.
The product of a residue with a residue is a residue, the product of two non residues is a residue, and the product of a residue and a non residue is a non residue. This can be proven by elementary means, but if we know about primitive roots then the striking resemblance of these rules to those for adding even and odd numbers is explained clearly (because we are adding even and odd numbers - namely, the logarithms).
When is $-1$ a quadratic residue modulo $p$? We just need to know when the index of $-1$ is even. If $r$ is a primitive root then $r^{p-1}\equiv 1$, so $\frac {p-1} 2$ (which is an integer) is the index of $-1$. It is easy to determine for which primes $p$ this is even and for which it is not - it is even precisely when $p$ is one more than a multiple of $4$.