Recall what we’re trying to do here: to show that if *p* > 2 is prime and *a* is not a square modulo *p*, then . As mentioned at the end of the previous part, we will need…

**Primitive Roots**

Again, let *p* > 2 be prime. For any *a* which is not divisible by *p*, recall that we have *d* = ord_{p}(*a*), which is the smallest positive integer *d* for which . We had proven earlier that *d* must divide *p*-1.

Definition : a

primitive rootis an element g mod p such that exactly.

In other words, among the elements (modulo *p*), only the first is equal to 1. In fact, we can say more: all these *p*-1 elements are distinct mod *p*! Indeed, if *g ^{i}* ≡

*g*(mod

^{j}*p*) for some 0 ≤

*i*<

*j*≤

*p*-2, then since

*g*is coprime to

*p*, we can do cancellation on both sides to obtain

*g*≡ 1 (mod

^{j-i}*p*) where 0 <

*j-i*≤

*p*-2 which contradicts our assumption. So the

*p*-1 elements are distinct and each is congruent to one of {1, 2, …,

*p*-1}. In short:

If g is a primitive root, then the successive powers forms a permutation of {1, 2, …, p-1}.

E.g.

*p*= 7 : pick*g*= 3, then the successive powers of 3 give : .*p*= 13 : pick*g*= 2, then powers of 2 give 1, 2, 4, 8, 3, 6, 12, 11, 9, 5, 10, 7.

Now, we shall state a theorem without proof (with apology in advance … but it’s a very classical result and the reader should have no difficulty finding a book with proof).

Theorem. Every prime p has at least one primitive root.

**Exercise 1**: exactly how many primitive roots are there modulo *p* ?

**Exercise 2**: prove that if *m* is a positive integer not divisible by *p*-1, then is a multiple of *p*.

–

Ok, now we’re ready to explain why for non-square *a* modulo *p*. Pick a primitive root *g* mod *p*. Since the powers of *g* (mod *p*) run through the entire set {1, 2, …, *p*-1} in some order, we have

for some *i*. We had already seen that must hold, so it suffices to show . But if , then:

.

Since the multiplicative order of *g* modulo *p* is exactly *p*-1, it just means that *i*(*p*-1)/2 is a multiple o*f p*-1, i.e. *i* is a multiple of 2, so we write *i* = 2*j*. Thus, is a square modulo *p*, which is a contradiction. ♦

**Exercise 3** : prove that if *p* > 2 is prime, then (-1) is a square modulo *p* if and only if *p* is 1 modulo 4. [ Thanks to our theory of quadratic residues, this result is utterly trivial. ]

**Exercise 4** : prove that if *p* > 2 is prime, then 2 is a square modulo *p* if and only if *p* ≡ ±1 (mod 8).

The last result is extremely important and not too easy, so we’ll guide you along with it. To read the hint, highlight the text starting from here … [ Hint : consider the elements 1, 2, … , (*p*-1)/2 modulo *p*. Upon multiplying them by 2, we obtain 2, 4, …, (*p*-1). Note that 2 × 4 × … × (*p*-3) × (*p*-1) ≡ (-1) × 2 × (-3) × 4 … . Now, multiply these (*p*-1)/2 numbers together, consider various cases modulo 8 and you’re done. ] … to here.

In the next chapter, we’ll introduce the Legendre symbol notation, an extremely handy notation for checking which numbers are squares mod *p*. Also, you’ll answer questions like “for what primes *p* is 3 a square mod *p*?”.