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 root is 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ⁱ ≡ g^j (mod 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^j-i ≡ 1 (mod 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 of p-1, i.e. i is a multiple of 2, so we write i = 2j. 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?”.