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 (ℤ/pℤ)×) if the multiplicative order
of g modulo p is ϕ(p)=p-1. In other words, g is a generator
of the cyclic group
(ℤ/pℤ)×, i.e.
(ℤ/pℤ)×={1,2,3,…,p-1}={1,g,g2,…,gp-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>2 be a natural number. We say that n is the least universal exponent for Z/NZ if an≡1mod for all and is the least positive integer with this property.
It follows from Euler’s theorem that the least universal exponent of is less or equal to the value of Euler’s phi function , and in fact, the least universal exponent should divide .
Lemma.
Let be a prime and let be the least universal exponent of . Then there is a number whose order is precisely .
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 , 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 and have orders and then there is an element whose order is . This is clear: if is a prime and divides then, there is an element whose order is (namely has such order); and if and are relatively prime then . Finally, suppose that , for some distinct primes and positive integers . Then, each divides either or and there is an element of order exactly . Thus, the element has exact order .
∎
Theorem.
Every prime has a primitive root.
The following proof is due to Legendre.
Proof.
If then is a primitive root. Let us assume that is prime and let be the least universal exponent for , i.e. is the smallest positive integer such that , for all non-zero . Notice that, in particular by the Lemma, there is some element such that but for any , i.e. the multiplicative order of is precisely . Also, notice that by Fermat’s little theorem, .
Now, the polynomial has at most roots over the field (see http://planetmath.org/node/APolynomialOfDegreeNOverAFieldHasAtMostNRootsthis entry), and for all non-zero . Thus . Hence, and is of exact order , therefore 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 |