Corollary 2.5.1

Corollary 2.5.1 Suppose p and q are prime, and p =2q + 1. Suppose g Є Z*_p and

g ≠±1(mod p). Then g is a primitive element if and only if g^(p-1)/2 ≠ 1(mod p).

Proof. Observe that g^[(p-1)/q] ≠ g^2 (mod p), and g^2≡ 1(mod p)

if and only if g ≡≠1(mod p). Hence the result follows from the last Lemma.

In fact, If g ≠±1 (mod p) and g is not primitive, then g^(p-1)/2 ≡ 1(mod p). But then

we have Thus, by this Corollary (-g) must be primitive.