Proof.
Let
![$ a\in (\mathbb{Z}/p\mathbb{Z}{})^*$](img884.png)
.
The order of
![$ a$](img37.png)
is a divisor
![$ d$](img16.png)
of
the order
![$ p-1$](img531.png)
of the group
![$ (\mathbb{Z}/p\mathbb{Z}{})^*$](img779.png)
.
Write
![$ d =(p-1)/n$](img885.png)
, for some divisor
![$ n$](img7.png)
of
![$ p-1$](img531.png)
.
If
![$ a$](img37.png)
is not a generator of
![$ (\mathbb{Z}/p\mathbb{Z}{})^*$](img779.png)
, then
since
![$ n\mid (p-1)$](img886.png)
, there is a prime divisor
![$ p_i$](img270.png)
of
![$ p-1$](img531.png)
such that
![$ p_i\mid n$](img887.png)
.
Then
Conversely, if
![$ a$](img37.png)
is a generator, then
![$ a^{(p-1)/p_i} \not\equiv 1\pmod{p}$](img882.png)
for any
![$ p_i$](img270.png)
. Thus the algorithm terminates with step
3
if and only if the
![$ a$](img37.png)
under consideration is a primitive root.
By Theorem
2.5.8 there is at least one primitive
root, so the algorithm terminates.