every prime has a primitive root

Let p be a prime. Recall that an integer g is said to be a primitive rootMathworldPlanetmath for p (or more concretely for (/p)×) if the multiplicative orderMathworldPlanetmath of g modulo p is ϕ(p)=p-1. In other words, g is a generatorPlanetmathPlanetmathPlanetmath of the cyclic groupMathworldPlanetmath (/p)×, i.e.


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


Let N>2 be a natural numberMathworldPlanetmath. We say that n is the least universal exponent for Z/NZ if an1modN for all a(Z/NZ)× and n is the least positive integer with this property.

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


Let p be a prime and let n be the least universal exponent of Z/pZ. Then there is a number a(Z/pZ)× whose order is precisely n.


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 multipleMathworldPlanetmathPlanetmath of all the orders of all the elements of (/N)×, 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 ord(a)=h and ord(b)=k then there is an element c whose order is ord(c)=lcm(h,k). This is clear: if q is a prime and qi divides h=ord(a) then, there is an element whose order is pi (namely ah/qi has such order); and if h=ord(c) and k=ord(d) are relatively prime then ord(cd)=hk. Finally, suppose that lcm(h,k)=q1i1qtit, for some distinct primes q1,,qt and positive integers i1,,it. Then, each qjij divides either h or k and there is an element cj of order exactly qjij. Thus, the element c=c1ct has exact order lcm(h,k). ∎


Every prime p has a primitive root.

The following proof is due to Legendre.


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 xn1modp, for all non-zero x/p. Notice that, in particular by the Lemma, there is some element g/p such that gn1 but gm1modp for any m<n, i.e. the multiplicative order of g is precisely n. Also, notice that by Fermat’s little theorem, np-1.

Now, the polynomialPlanetmathPlanetmath f(x)=xn-1 has at most n roots over the field /p (see http://planetmath.org/node/APolynomialOfDegreeNOverAFieldHasAtMostNRootsthis entry), and f(x)0modp for all non-zero xmodp. Thus np-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