Introduction
When doing modular arithmetic modulo $n$, whose prime factorization is $p_1^{\alpha_1}...p_k^{\alpha_k},$ it is sensible to consider each of the moduli $p_i^{\alpha_i}$ separately. Indeed, the Chinese remainder theorem guarantees that if we solve a congruence equation modulo each of these prime powers, we can recover the original solution $\pmod n$. This is not only numerically a lot more effective, but also shows that any polynomial congruence problem in $\mathbb{Z}_n$ (the integers $\pmod n$) is reduced to understanding the structure of $\mathbb{Z}_{p^{\alpha}}$ for prime powers (we will encounter this fact many times).
The basic operations are easy to perform in $\mathbb{Z}_{p^{\alpha}}$. Three of them are no harder than in the ordinary integers, and division is also quite easy in $\mathbb{Z}_{p^{\alpha}}$ since the congruence $ax\equiv b \pmod{p^{\alpha}}$ has a unique solution, denoted by $x\equiv \frac{b}{a} \pmod{p^{\alpha}}$, if and only if $a$ and $p$ are coprime. This solution is given by Euclid's algorithm in an effective way. Therefore, it is natural to ask what is an effective way to take roots modulo a prime power or to solve exponential congruences.
The answer lies in exploiting the existence of a primitive root $g$ modulo $p^{\alpha}$, which is an integer such that its powers $g^k$ are noncongruent for $0\leq k<\varphi(p^{\alpha})$ ($\varphi(\cdot)$ is Euler's totient function). By Euler's theorem, $g^{\varphi(q)}\equiv 1 \pmod q$, so a primitive root is an integer whose powers repeat themselves as rarely as possible. Clearly every residue class coprime to $p$ is given by a power of $g$, so if $x\equiv g^{y}\pmod{p^{\alpha}},$ the equation $x^k\equiv a \pmod{p^{\alpha}}$ becomes $g^{ky}\equiv a \pmod{p^{\alpha}}$. In order to solve this new equation, we just need to determine which power of $g$ is congruent to $a$ (the answer is unique modulo $\varphi(p^{\alpha})$), and then perform a division, which is easy. Similarly, if we write $a\equiv g^m \pmod{p^{\alpha}}$, the equation $a^x \equiv b \pmod{p^{\alpha}}$ reduces to $g^{mx}\equiv b \pmod{p^{\alpha}}$, which can be solved in the same way as the former congruence. Hence, primitive roots work much in the same way as logarithms do in $\mathbb{R}$, but they are much more interesting, since they are by no means trivial despite their usefulness.
To appreciate primitive roots, it is good to know that before calculators people computed using logarithm tables. This is because all the basic operations are reduced to easier ones by taking logarithms, so one only needs a table of the values of the logarithm. However, in modular arithmetic, calculators have not replaced discrete logarithms, which are based on primitive roots, since the numbers that one computes with can be enormous (for example, one may want to compute $2^n\pmod m$, where $n$ is some number greater than one million, say), while the results are of reasonable size, namely smaller than the modulus. The fact that computing discrete logarithms, or equivalently finding primitive roots, is hard is the basis of many cryptosystems that are used for secure data transfer.
Primitive roots modulo primes
We will prove the existence of primitive roots, first modulo primes and later modulo odd prime powers (also the cases $2p^{\alpha}$ will be dealt with, and modulo $2^{\alpha}$ we ''almost'' have a primitive root). As usual, if one controls prime moduli, it is not very hard to control prime power moduli. Before giving the proof, let us consider one application of primitive roots to see their usefulness in some problems in elementary number theory. We show:
Proposition 1. The sum $1^k+2^k+...+(p-1)^k$ is $\equiv 0 \pmod p$ if $p-1\nmid k$ and $-1\pmod p$ otherwise.
Proof. The case $p-1\mid k$ follows directly from Fermat's little theorem, but in the case $p-1\nmid k$, it is convenient to use the existence of a primitive root $\pmod p$. By definition, the sets $\{1,g,g^2,...,g^{p-2}\}$ and $\{1,2,..,p-1\}$ are the same modulo $p$, so
\[1^k+2^k+...+(p-1)^k \equiv 1+g^{k}+g^{2k}+...+g^{(p-2) k}=\frac{g^{(p-1)k}-1}{g^k-1}.\]
\[1^k+2^k+...+(p-1)^k \equiv 1+g^{k}+g^{2k}+...+g^{(p-2) k}=\frac{g^{(p-1)k}-1}{g^k-1}.\]
The numerator is divisible by $p$ while the denominator is not, so the result is divisible by $p$, proving the claim.
■
In the case of a prime modulus, there is even a simple formula for the number of primitive roots.
Theorem 2. There is a primitive root $\pmod p$, when $p$ is a prime. Moreover, there are exactly $\varphi(p-1)$ of them.
The idea for proving this is the following. Let $\text{ord}_p(a)$ (the multiplicative order of $a$ modulo $p$) be the least positive integer $k$ such that $a^k \equiv 1 \pmod p$. We first show that $\text{ord}_p(a) $ is a divisor of $p-1$. Let $\text{ord}_p(a)=d$ be satisfied for $\psi(d)$ integers $a\in [1,p-1]$. We will see that $\psi(d)=0$ or $\varphi(d)$ for all $d$ and that $\sum_{d\mid p-1}\psi(d)=p-1$. On the other hand, we are going to see that $\sum_{d\mid p-1}\varphi(d)=p-1$, so $\psi(d)=\varphi(d)$ for $d\mid p-1$. In particular, there are $\psi(p-1)=\varphi(p-1)$ primitive roots $\pmod p$.
Lemma 3. We have $\text{ord}_p(a)\mid p-1$ and $\text{ord}_p(a^k)=\frac{\text{ord}_p(a)}{(\text{ord}_p(a),k)}$ (here $(\cdot,\cdot)$ is the greatest common divisor).
Proof. The relation $\text{ord}_p(a)\mid p-1$ is easy to prove although very useful. Indeed, if we had $p-1=k\cdot \text{ord}_p(a)+r$ with $0<r<\text{ord}_p(a)$, Fermat's little theorem would imply $a^{r}\equiv 1 \pmod p$, which is a contradiction to the minimality of the order.
Now we prove the second assertion. Let us denote $d=\text{ord}_p(a)$. Then $a^{kx}\equiv 1 \pmod p$ if and only if $d\mid kx$ (this follows similarly to the first part) if and only if $\frac{d}{(d,k)}\mid x,$ so the smallest nonnegative $x$ for which $a^{kx}\equiv 1 \pmod p$ is $x=\frac{d}{(d,k)}$.In other words, $\text{ord}_p(a^k)=\frac{d}{(d,k)}.$
■
The next step is to prove
Lemma 4. We have $\psi(d)=0$ or $\psi(d)=\varphi(d)$.
Proof. Suppose that $\psi(d)>0$ (in particular, $d\mid p-1$ by the previous lemma), and let $a$ be such that $\text{ord}_p(a)=d$. Then the integers $a,a^2,...,a^{d}$ are noncongruent $\pmod p$ and satisfy $\text{ord}_p(a^k)=d$ if and only if $(k,d)=1$, so we obtain $\psi(d)\geq \varphi(d)$. If we show that the congruence $x^d\equiv 1 \pmod p$ has precisely $d$ solutions, we are done, since the numbers $a,a^2,...,a^d$ are a set of $d$ solutions containing exactly $\varphi(d)$ elements with $\text{ord}_p(a)=d$. The congruence $x^{p-1}-1\equiv 0 \pmod p$ of course has $p-1$ solutions, and
\[x^{p-1}-1=(x^d-1)(x^{(n-1)d}+x^{(n-2)d}+...+1),\]
where $n=\frac{p-1}{d}.$ Therefore, Euclid's lemma tells that if the congruence $x^d\equiv 1 \pmod p$ had less than $d$ roots, there would exist a polynomial of degree $(n-1)d$ with more than $(n-1)d$ roots, which is impossible because $\mathbb{Z}_p$ is a field (the proof that the congruence $P(x)\equiv 0\pmod p$ has at most $\deg P$ solutions is essentially the same as the proof of the corresponding claim in the field $\mathbb{R}$). Similarly, $x^d-1$ cannot have more than $d$ roots $\pmod p$, so there are exactly $\varphi(d)$ of them, if any. This proves the lemma.
■
Finally, it is clear that every integer $1,2,...,p-1$ has a unique order, so $\sum_{d\mid p-1}\psi(d)=p-1$. Hence to finish the proof it is enough to show that $\varphi(d)$ has the same sum formula since we know that if $\psi(d)\neq \varphi(d)$, then $\psi(d)=0$.
Lemma 5. We have $\sum_{d\mid n}\varphi(d)=n$.
Proof. There are many ways to show this; one way would be to start with the case of $n$ equal to a prime power and use multiplicativity. We use a perhaps more elegant method. Consider the fractions $\frac{1}{n},\frac{2}{n},...,\frac{n}{n}$. The number of these fractions is $n$, and each of them can be written uniquely in a reduced form $\frac{k}{d}$, where $d\mid n$ and $(k,d)=1, 0<k\leq d$. For any $d$, there are $\varphi(d)$ such fractions, so in total we have $\sum_{d\mid n}\varphi(d)$ fractions. But, on the other hand, we had $n$ of them.
■
As already mentioned, combining the two previous lemmas proves the theorem.
■Prime power moduli
We now proceed to the case of prime power moduli, which follows easily from the case of primes.
Theorem 6. There exists a primitive root $\pmod{p^{\alpha}}$, where $p$ is an odd prime.
Proof. Take a primitive root $g\pmod p$. Then one of $g$ and $g+p$ is a primitive root also modulo $p^2$. Indeed, if $g^k \equiv 1 \pmod p$ for some $k\in [0,\varphi(p^2)-1]$, then
\[(g+p)^k =\sum_{r=0}^k \binom{k}{r}g^rp^{k-r}\equiv g^k+kpg^{k-1}\equiv 1+kpg^{k-1}\pmod p.\]
Therefore, $(g+p)^k$ cannot be $1$ modulo $p^2$ unless $p\mid k$, but since $p-1\mid k$ by definition, we get $\varphi(p^2)\mid k$, so $g+p$ is a primitive root.
In the case of higher powers of $p$, one again has a nice result: If $g$ is a primitive root modulo $p$ and $p^2$, it is a primitive root with respect to all the powers. Suppose $g^k \equiv 1 \pmod{p^{\alpha}}$. Then by assumption $p(p-1)\mid k$. We show by induction on $\alpha$ that $p^{\alpha-1}(p-1)\mid k.$ The case $\alpha=2$ has already been considered. If the case $\alpha$ has been proved, $g^{k}\equiv 1 \pmod{p^{\alpha+1}}$ implies $g^{\frac{k}{p}}\equiv 1 \pmod{p^{\alpha}}$ since $g^k-1=(g^{\frac{k}{p}}-1)(g^{\frac{k(p-1)}{p}}+...+g^{\frac{k}{p}}+1)$ and the latter factor is congruent to $p \pmod{p^2}$ because $g^{\frac{k}{p}}\equiv 1 \pmod p$. Thus the induction hypothesis gives $p^{\alpha}\mid k$, and $p-1 \mid k$ was already known. The claim is now proved (by the way, the method we used to deal with congruences $\pmod{p^{\alpha}}$ could be generalized to prove the so called lifting the exponent lemma).
■
The case $2p^{\alpha}$ is a direct corollary.
Theorem 7. If $p$ is an odd prime, there exists a primitive root $\pmod{2p^{\alpha}}$. In addition, there exists a primitive root $\pmod 4$.
Proof. The number $3$ is clearly a primitive root $\pmod 4$. Let $g$ be a primitive root $\pmod{p^{\alpha}}$. If $g^k\equiv 1 \pmod{2p^{\alpha}}, $ we have $p^{\alpha-1}(p-1)\mid k$ and $\varphi(2p^{\alpha})=p^{\alpha-1}(p-1)$, so $g$ is actually a primitive root for the new modulus unless it is even. Since $g$ is a primitive root if and only if $g+p^{\alpha}$ is, we may assume that it is odd.
■
Summarizing, we have proved that there exists a primitive root modulo $2,4,^{\alpha}$ and $2p^{\alpha}$, where $p$ is an odd prime. These turn out to be the only cases when we have a primitive root (in fact, for other moduli $n$ one can show that $a^{\frac{\varphi(n)}{2}}\equiv 1 \pmod n$ for $(a,n)=1$), but for powers of two we almost have a primitive root; namely
Theorem 8. We have $5^k \equiv 1 \pmod{2^{\alpha}}, \alpha\geq 3,$ if and only if $2^{\alpha-2}\mid k$.
Proof. We induct on $\alpha.$ The base case is trivial. Assume $5^k \equiv 1 \pmod{p^{\alpha}}.$ Obviously $k$ is even, so $5^k-1=(5^{\frac{k}{2}}-1)(5^{\frac{k}{2}}+1),$ and the latter factor is divisible by $2$ but not by $4$, so we arrive at $5^{\frac{k}{2}}\equiv 1 \pmod{2^{\alpha-1}},$ so we may apply the induction hypothesis to see that $2^{\alpha-3}\mid\frac{k}{2}$, which proves the statement.
■
Since $\varphi(2^{\alpha})=2^{\alpha-1},$ the number $5$ is very close to being a primitive root, and this is enough for many applications.
Problems solvable with primitive roots
Now that we have enough theory about primitive roots, let us consider some problems that can be solved with them.
Proposition 9 (Wilson's theorem). For a prime $p$, it holds that $(p-1)! \equiv -1 \pmod p.$
Proof. Let $g$ be a primitive root $\pmod p$. Again, the sets $\{1,2,...,p-1\}$ and $\{1,g,...,g^{p-2}\}$ are identical $\pmod p$, so $(p-1)!\equiv g^{0+1+...+(p-2)}=g^{\frac{(p-1)(p-2)}{2}}\pmod p$. We have $g^{\frac{p-1}{2}}\equiv -1\pmod p$ since $g^{\frac{p-1}{2}}$ is equal to $\pm 1$ as a square root of $1$ $\pmod p$, and it cannot be $1\pmod p$ as $g$ is a primitive root. The number $g^{\frac{(p-1)(p-2)}{2}}$ is an odd power of this (unless $p=2$, which is a trivial case), so it is also $-1\pmod p.$
■
Problem 10. (IMO shortlist 1997) If an infinite arithmetic progression of positive integers contains a perfect square and a perfect cube, then it also contains the sixth power of an integer.
Proof. Let the arithmetic progression be $qn+a,n=1,2,...$. Our assumption is that the congruences $x^2 \equiv a \pmod q$ and $x^3 \equiv a \pmod q$ are solvable, and we want to show that the equation $x^6 \equiv a \pmod q$ has a solution. From the Chinese remainder theorem it follows that a polynomial congruence $\pmod q$ has a solution if and only if it has a solution modulo all the prime power divisors of $q$. therefore, it is enough to consider the case $q=p^{\alpha}$. The cases $q=1,2,4$ are trivial. Assume first that $q=p^{\alpha}$ is odd, and let $g$ be a primitive root $\pmod{p^{\alpha}}$. The number $a$ above can be assumed to be coprime with $q$ since if $p^k$ is their greatest common divisor, $k$ must be divisible by $6$, but in that case, we can just divide $a$ and $q$ by $p^6$, reducing the greatest common divisor without altering the claim.
Hence we can write $a\equiv g^n\pmod{p^{\alpha}}.$ We obtain $g^{2m}\equiv g^n \pmod{p^{\alpha}}$ for some $m$, and equivalently, $2m\equiv n \pmod{p^{\alpha-1}(p-1)}.$ This means that $n$ is even. Similarly, $3\ell\equiv n \pmod{p^{\alpha-1}(p-1)}$ for some $\ell$. Then the solubility of the congruence $x^6\equiv a \pmod q$ means that $6k \equiv n \pmod{p^{\alpha-1}(p-1)}$ for some $k$. It is clear that the conditions $2\mid n$ and $3\ell\equiv n \pmod{p^{\alpha-1}(p-1)}$ allow us to choose $k=\frac{\ell}{2}$, which finishes the case of an odd prime power.
Then let $q=2^{\alpha},\alpha\geq 3$. Again $a$ can be assumed odd without loss of generality. Then $a$ is either a power of $5\pmod{2^{\alpha}}$ or the negative of a power of $5$. Indeed, if two of the numbers $1,5,...,5^{2^{\alpha-2}},-1,-5,...,-5^{2^{\alpha-2}}$ were congruent, it would follow that $5^i\equiv -5^j\pmod{2^{\alpha}}$ for some $0< i<j\leq 2^{\alpha-2}$. but then $5^{i+j}\equiv -1 \pmod{2^{\alpha}}$, which is impossible. So let us write any odd $x$ as $x\equiv \pm 5^k \pmod{2^{\alpha}}$. Then $x^3 \equiv \pm 5^{3k}\pmod{2^{\alpha}}$, so we see that the map $x\mapsto x^3$ only permutes the odd residues. Thus $x^6=(x^2)^3 \equiv a \pmod{2^{\alpha}}$ is solvable if and only if $x^2 \equiv a \pmod{2^{\alpha}}$ is.
■
There are plenty of other examples as well. I formulate a few without proofs. Notice that all of the following problems can be formulated without mentioning primitive roots, but in solving them, primitive roots are beneficial.
Problem 11. Let $p$ be a prime and $a$ an integer not divisible by $p$. Then the congruence $x^n \equiv a \pmod p$ has either no solutions or exactly $(n,p-1)$ of them.
Problem 12. (Vojtech Jarnik competition 2014) Let $p\equiv 1 \pmod 6$ be a prime. Let $A$ be a subset of $\mathbb{Z}_p$ that forms a multiplicative group. Then there exist $x,y\in A$ such that $x+y\equiv 1\pmod p$.
Problem 13. Let $n$ be a positive integer. Then we have the following generalization of Wilson's theorem
\[\prod_{1\leq k\leq n\atop (k,n)=1} k=\begin{cases}-1 \quad \text{if}\quad n=4,p^{\alpha},2p^{\alpha}\\ 1\quad \text{otherwise},\end{cases}\]
where $p$ denotes an odd prime.
Problem 14. Let $n$ be a positive integer, and let $n'$ be its odd part. Then the number of solutions to $x^2\equiv 1 \pmod n$ is $2^{a+\omega(n')}$,where $\omega(m)$ is the number of prime factors of $m$, and $a=0$ if $n$ is odd, $a=1$ if $2\mid n$ but $4$ does not divide $n$, and $a=2$ if $4\mid n$.
Problem 15. Let $p$ be a prime. Then the length of the period of the decimal representation of $\frac{1}{p}$ is $p-1$, if $10$ is a primitive root $\pmod p$, and otherwise the period is shorter (it is $\text{ord}_{p}(10)$).
Problem 16. Let $p$ be a prime. Then the longest possible period of the sequence $a^{2^n} \pmod p ,n=0,1,2,...$ is $\text{ord}_{(p-1)'}(2)$, where $(p-1)'$ is the odd part of $(p-1)'$ (the sequence is not necessarily periodic, but it becomes periodic at some point).
Problem 17. There are only two real-valued Dirichlet characters $\pmod q$; in other words, if a function $\chi:\mathbb{Z}\to \mathbb{R}$ has the properties
(i) $\chi(mn)=\chi(m)\chi(n)$ for all $m,n$
(ii) $\chi(n)=0$ unless $(n,q)=1$
(iii) $\chi(n+q)=\chi(n)$ for all $n$,
then either $\chi(n)=1$ whenever $(n,q)=1$ and $\chi(n)=0$ otherwise, or
\[\chi(n)=\left(\frac{n}{p_1}\right)^{\alpha_1}...\left(\frac{n}{p_k}\right)^{\alpha_k},\]
where $q=p_1^{\alpha_1}...p_k^{\alpha_k}$ and $\left(\frac{n}{p}\right)$ is the Legendre symbol ($\left(\frac{n}{p}\right)$ is equal to $0$ if $p\mid n$, and otherwise it gives the value $1$ if $n\equiv a^2\pmod p$ for some $a$, and it gives the value $-1$ otherwise). The expression above is called the Jacobi symbol $\pmod q$.
Problem 18. Let $n=p_1^{\alpha_1}...p_k^{\alpha_k}$. Define the Carmichael function $\lambda(n)$ by
\[\lambda(n)= [\varphi(p_1^{\alpha_1}),...,\varphi(p_k^{\alpha_k})],\]
where $[a_1,...,a_k]$ is the least common multiple of $a_1,...,a_k$. Then $\lambda(n)$ is the smallest integer $m$ with the property $a^{m}\equiv 1 \pmod n$ for all $a$ coprime to $n$. Moreover, if $\alpha=\max \alpha_i$ is the maximal exponent in the prime factorization, then $a^{\lambda(n)+\alpha}\equiv a^{\alpha} \pmod n$ for any $a$. We also see that there is no primitive root $\pmod n$ unless $n$ is of the form $2,4,p^{\alpha}$ or $2p^{\alpha}$.
