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