# 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?

• primitive roots generate the multiplicative group $\mathbf{Z}_n^{*}$ Commented Nov 10, 2013 at 13:53
• Primitive roots are generators of cyclic groups. This is very important and there are a lot of open problems concerning them, in particular the Artin's conjecture for primitive roots, which has an important analogue for elliptic curves. Besides theoretical reasons, founding an efficient method for generating primitive roots mod $p$ for large primes, could also be dramatically relevant for cryptography. Commented Nov 10, 2013 at 17:38
• They are also the only roots of cyclotomic polynomials which are also very useful. Commented Nov 11, 2013 at 11:20
• Being cyclic is an incredibly strong statement about the structure of a group. It says that multiplying modulo $n$ is basically walking around a circle with $\phi(n)$ points on it. It's a general principle in mathematics that if you can describe or visualize a structure in a very simple way, you should do it, because it's bound to simplify calculations somewhere along the line. Commented Jan 20, 2015 at 22:03

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:

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

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

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