Proof of Theorem 5

This proof unfortunately requires many lemmas. It is probably a good idea to skip over the lemmas as much as possible on a first reading.

We begin with three preliminary results about greatest common divisors, which may be intuitive.

Lemma 11   If $(a,b)=1$ and $(a,c)=1$, then $(a,bc)=1$.

Proof: By Theorem 1, there are integers $x,y,w,z$ with $ax+by=aw+cz=1$. Together these imply

$$ax+b(awy+czy)=1= a(x+bwy)+bc(zy)$$

which is impossible if $(a,bc)>1$. height 8pt width 4pt

Lemma 12   If $a$ divides $b$ and $(b,c)=1$, then $(ab,c)=1$.  

Proof: Let $bx+cy=1$ and $b=az$. Then

$$1=bx+cy= b^2x^2+bxcy+cy=ab(x^2z)+c(bxy+y)\quad\hbox{\vrule height 8pt width 4pt}$$

Lemma 13   If $(a,b)=1$, $cb$ is divisible by $a$, and $ca$ is divisible by $b$, then $c$ is divisible by $ab$.

Proof: Let $ax+by=1$, $cb=aw$, and $ca=bz$. Then

$$c=c(ax+by)^2=ca^2x^2+cb^2y^2+2abcxy=ab(x^2z+y^2w+2cxy)\quad\hbox{\vrule height 8pt width 4pt}$$

The key step of the proof begins with any $x\not\equiv0$. Let $d$ be the smallest positive number for which $x^d \equiv1$ (there must be such a $d\le p-1$ since $x^K\equiv x^L$ implies $x^{K-L}\equiv1$). By Lemma 10, if $d=p-1$, $x$ is a primitive root. If $d<p-1$, we will find $t$ with $t^i\not\equiv1$ for all $0<i\le d$. If $t$ is not a primitive root, we repeat the process, this time with $x=t$. Since the exponent $d$ increases each time, we eventually obtain a primitive root.

Lemma 14   There are at most $d$solutions to a congruence involving a polynomial of degree $d$:

$$x^d+\alpha_1x^{d-1}+\dots\alpha_d\equiv0\hbox{ (mod }p)$$

In particular, there are at most $d$ $x$ with $x^d \equiv1$. 

Proof: This can be proved in the same way as the corresponding theorem in ordinary algebra: if $x=\beta$is a solution, the polynomial can be written as $(x-\beta)$ times a poly nomial of degree $d-1$, which by induction has $\le d-1$ solutions. height 8pt width 4pt

We return to the proof of Theorem 5.² The sequence

$$x\quad x^2\quad x^3\dots x^d\equiv1\hbox{ (mod }p)$$

consists of $d$ different solutions of $x^d \equiv1$. If $d<p-1$, let $y\not\equiv0$ be any non-member of the sequence, with $e$ the smallest positive number with $y^e\equiv1$. If $e>d$, we may take $t=y$, so we will assume $e\le d$ from now on. By Lemma 14, $y^d\not\equiv1$, which implies $e$ does not divide $d$ and $e/(d,e)>1$. We will use $x$ and $y$ to construct a number $t$ such that $t^i\not\equiv1$ for all $0<i<de/(d,e)$. The construction is based on two lemmas:

Lemma 15   Suppose that $(a,b)=1$ and that $a,b$ are the smallest positive numbers for which $u^a\equiv v^b\equiv1$. If $k>0$ and $(uv)^k\equiv1$, then $k$ is divisible by $ab$. 

Proof: Since $(uv)^{ka}\equiv1\equiv v^{ka}$, Lemma 9 implies $ka$ is divisible by $b$. Similarly $kb$ is divisible by $a$, and Lemma 13 gives the desired result. height 8pt width 4pt

Lemma 16   Let $c=(d,e)$, $d'=d/c$, $e'=e/c$. There are $m,m'$ such that (i) $mm'=c$ and (ii)  $(d'm,e'm')=1$.

Proof: Let $m$ be the largest divisor of $c$ for which $(m,e')=1$, $m'=c/m$. The maximality of $c$ implies $(d',e')=1$. By Lemma 11, $(md',e')=1$.

The maximality of $m$ and Lemma 12 implies $(m,m')=1$. Since $(d',e')=1$ implies $((d',m'),e')=1$, Lemma 11 implies $(m(d',m'),e')=1$. Thus the maximality of $m$ implies $(d',m')=1$. Lemma 11 now implies $(md',m')=1$.

Applying Lemma 11 to the conclusions of the preceding paragraphs yields $(d'm,em')=1$. height 8pt width 4pt

We can finally complete the proof of Theorem 5. With the notation of Lemma 16, let $t=x^{m'}y^m$. For $u=x^{m'}$, $u^a\not\equiv1$ for $0<a<md'$. A similar assertion holds for $v=y^m$. The other conditions of Lemma 15 are satisfied, and we can conclude that $t^k\equiv1$ if and only if $k$ is a multiple of $md'm'e'=de/c$. height 8pt width 4pt

This proof does not give us an efficient procedure for finding a primitive root for large primes $p$, but the reason may not be obvious. The steps implicit in the lemmas can all be carried out efficiently. The one problem is the choice of $y$, which was required to be a non-member of the set of powers of $x$. It is too inefficient to list all the powers of $x$ if $d$ is large, and no significantly better way of finding a non-member is known.

Footnotes

....²

This proof uses ideas of Michael Fischer, who pointed out an error in an earlier version.