Quadratic Residues – Part I

[ Background required : modular arithmetic. Seriously. ]

Warning: many of the proofs for theorems will be omitted in this set of notes, due to the length of the proofs.

The basic question we’re trying to answer in this series of notes is:

Let a be an integer mod m, so 0 ≤ a ≤ m-1. For which a, are there solutions to the congruence x^2 \equiv a \pmod m?

For some concrete examples:

  • m = 11 : then (±1)2 ≡ 1, (±2)2 ≡ 4, (±3)2 ≡ 9, (±4)2 ≡ 5, (±5)2 ≡ 3, so the only squares modulo 11 are 0, 1, 3, 4, 5, 9;
  • m = 15 : then (±1)2 ≡ 1, (±2)2 ≡ 4, (±3)2 ≡ 9, (±4)2 ≡ 1, (±5)2 ≡ 10, (±6)2 ≡ 6, (±7)2 ≡ 4, so the squares modulo 15 are 0, 1, 4, 6, 9, 10.

By Chinese Remainder Theorem, we know that solving a congruence modulo m is equivalent to solving it modulo prime powers, e. g. to solve something mod 135, it suffices to solve it mod 27 and mod 5, then piece the results together. In our above example of m = 15, notice that m = 10 is a square but m = 5 isn’t: because 5 modulo 3 = 2 is not a square mod 3.

In other words, we might as well assume m = pr is a prime power. In fact, we will even assume m = p is an odd prime for now. The case of prime power is not significantly harder.

Let a be an integer which is not divisible by prime p > 2.

First, suppose a is a square mod p, i.e. we can find an x for which x^2 \equiv a \pmod p. Since a is not divisible by p, neither is x. By Fermat’s little theorem, we get:

1 \equiv x^{p-1} \equiv a^{\frac{p-1} 2} \pmod p.

In short, if a is a square, then a^{(p-1)/2} \equiv 1 \pmod p.

On the other hand, what happens if a is not a square?

Let x \equiv a^{(p-1)/2} \pmod p. Thanks to Fermat’s little theorem again, we have:

x^2 \equiv a^{p-1} \equiv 1 \pmod p.

Thus, x2-1 is a multiple of p and so either x-1 or x+1 is a multiple of p, i.e. x \equiv \pm 1 \pmod p. In conclusion, we have proven the following:

Let m = p be an odd prime. For any a which is not divisible by p, let x = a^{(p-1)/2}. Then

  • we always have x ≡ ±1 (mod p);
  • if a is a square mod p, then x ≡ 1 (mod p).

The big question is: what happens if a is not a square mod p??

It turns out, as the reader suspected, that if a is not a square mod p, then a^{(p-1)/2} \equiv -1 \pmod p. E.g. take the case of p = 13 and a = 2, then we have a^{(p-1)/2} = 2^6 = 64 \equiv -1 \pmod {13}.

To prove this in greater generality, we will need to introduce the concept of primitive roots in the next installation…

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