# every prime has a primitive root

Let $p$ be a prime. Recall that an integer $g$ is said to be a primitive root^{} for $p$ (or more concretely for ${(\mathbb{Z}/p\mathbb{Z})}^{\times}$) if the multiplicative order^{} of $g$ modulo $p$ is $\varphi (p)=p-1$. In other words, $g$ is a generator^{} of the cyclic group^{} ${(\mathbb{Z}/p\mathbb{Z})}^{\times}$, i.e.

$${(\mathbb{Z}/p\mathbb{Z})}^{\times}=\{1,2,3,\mathrm{\dots},p-1\}=\{1,g,{g}^{2},\mathrm{\dots},{g}^{p-2}\}.$$ |

Before we go into the proof of the main theorem, we define the term “least universal^{} exponent” and prove a lemma.

###### Definition.

Let $N\mathrm{>}\mathrm{2}$ be a natural number^{}. We say that $n$ is the least universal exponent for $\mathrm{Z}\mathrm{/}N\mathit{}\mathrm{Z}$ if ${a}^{n}\mathrm{\equiv}\mathrm{1}\mathrm{mod}N$ for all $a\mathrm{\in}{\mathrm{(}\mathrm{Z}\mathrm{/}N\mathit{}\mathrm{Z}\mathrm{)}}^{\mathrm{\times}}$ and $n$ is the least positive integer with this property.

It follows from Euler’s theorem that the least universal exponent $n$ of $\mathbb{Z}/N\mathbb{Z}$ is less or equal to the value of Euler’s phi function $\varphi (n)$, and in fact, the least universal exponent should divide $\varphi (n)$.

###### Lemma.

Let $p$ be a prime and let $n$ be the least universal exponent of $\mathrm{Z}\mathrm{/}p\mathit{}\mathrm{Z}$. Then there is a number $a\mathrm{\in}{\mathrm{(}\mathrm{Z}\mathrm{/}p\mathit{}\mathrm{Z}\mathrm{)}}^{\mathrm{\times}}$ whose order is precisely $n$.

###### Proof.

In this proof we will use the properties of the multiplicative order of an integer. We shall prove that (a) the least universal exponent is the least common multiple^{} of all the orders of all the elements of ${(\mathbb{Z}/N\mathbb{Z})}^{\times}$, and (b) there is an element whose order is exactly the least common multiple. In order to show (a) and (b), it suffices to show that if $a$ and $b$ have orders $\mathrm{ord}(a)=h$ and $\mathrm{ord}(b)=k$ then there is an element $c$ whose order is $\mathrm{ord}(c)=\mathrm{lcm}(h,k)$. This is clear: if $q$ is a prime and ${q}^{i}$ divides $h=\mathrm{ord}(a)$ then, there is an element whose order is ${p}^{i}$ (namely ${a}^{h/{q}^{i}}$ has such order); and if ${h}^{\prime}=\mathrm{ord}(c)$ and ${k}^{\prime}=\mathrm{ord}(d)$ are relatively prime then $\mathrm{ord}(cd)={h}^{\prime}{k}^{\prime}$. Finally, suppose that $\mathrm{lcm}(h,k)={q}_{1}^{{i}_{1}}\mathrm{\cdots}{q}_{t}^{{i}_{t}}$, for some distinct primes ${q}_{1},\mathrm{\dots},{q}_{t}$ and positive integers ${i}_{1},\mathrm{\dots},{i}_{t}$. Then, each ${q}_{j}^{{i}_{j}}$ divides either $h$ or $k$ and there is an element ${c}_{j}$ of order exactly ${q}_{j}^{{i}_{j}}$. Thus, the element $c={c}_{1}\mathrm{\cdots}{c}_{t}$ has exact order $\mathrm{lcm}(h,k)$.
∎

###### Theorem.

Every prime $p$ has a primitive root.

The following proof is due to Legendre.

###### Proof.

If $p=2$ then $g=1$ is a primitive root. Let us assume that $p>2$ is prime and let $n$ be the least universal exponent for $p$, i.e. $n$ is the smallest positive integer such that ${x}^{n}\equiv 1modp$, for all non-zero $x\in \mathbb{Z}/p\mathbb{Z}$. Notice that, in particular by the Lemma, there is some element $g\in \mathbb{Z}/p\mathbb{Z}$ such that ${g}^{n}\equiv 1$ but ${g}^{m}\ne 1modp$ for any $$, i.e. the multiplicative order of $g$ is precisely $n$. Also, notice that by Fermat’s little theorem, $n\le p-1$.

Now, the polynomial^{} $f(x)={x}^{n}-1$ has at most $n$ roots over the field $\mathbb{Z}/p\mathbb{Z}$ (see http://planetmath.org/node/APolynomialOfDegreeNOverAFieldHasAtMostNRootsthis entry), and $f(x)\equiv 0modp$ for all non-zero $xmodp$. Thus $n\ge p-1$. Hence, $n=p-1$ and $g$ is of exact order $p-1$, therefore $g$ is a primitive root.
∎

Title | every prime has a primitive root |
---|---|

Canonical name | EveryPrimeHasAPrimitiveRoot |

Date of creation | 2013-03-22 16:20:41 |

Last modified on | 2013-03-22 16:20:41 |

Owner | alozano (2414) |

Last modified by | alozano (2414) |

Numerical id | 6 |

Author | alozano (2414) |

Entry type | Theorem |

Classification | msc 11-00 |

Related topic | APolynomialOfDegreeNOverAFieldHasAtMostNRoots |

Related topic | ExistenceOfPrimitiveRootsForPowersOfAnOddPrime |