Why do we need primitive roots? 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?
 A: 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$.
