Quadratic Residues – Part II

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 a^{(p-1)/2} \equiv -1 \pmod p. 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 = ordp(a), which is the smallest positive integer d for which a^d \equiv 1 \pmod p. We had proven earlier that d must divide p-1.

Definition : a primitive root is an element g mod p such that ord_p(g) = p-1 exactly.

In other words, among the elements 1, g, g^2, g^3, \dots, g^{p-2} (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 gi ≡ gj (mod p) for some 0 ≤ i < p-2, then since g is coprime to p, we can do cancellation on both sides to obtain gj-i ≡ 1 (mod p) where 0 < j-i ≤ p-2 which contradicts our assumption. So the p-1 elements 1, g, g^2, \dots, g^{p-2} 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 1, g, g^2, \dots, g^{p-2} forms a permutation of {1, 2, …, p-1}.

E.g.

  • p = 7 : pick g = 3, then the successive powers of 3 give : 1, 3, 3^2 \equiv 2, 3^3 \equiv 6, 4, 5.
  • 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 1^m + 2^m + \dots + (p-1)^m is a multiple of p.

Ok, now we’re ready to explain why a^{(p-1)/2} \equiv -1 \pmod p 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

g^i \equiv a \pmod p

for some i. We had already seen that a^{(p-1)/2} \equiv \pm 1 \pmod p must hold, so it suffices to show a^{(p-1)/2} \not\equiv +1 \pmod p. But if a^{(p-1)/2} \equiv +1 \pmod p, then:

g^{i(p-1)/2} \equiv +1 \pmod p.

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, a \equiv g^{2j}\equiv (g^j)^2 \pmod p 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?”.

This entry was posted in Notes and tagged , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s