[ 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 ?

For some concrete examples:

• m = 11 : then (±1)² ≡ 1, (±2)² ≡ 4, (±3)² ≡ 9, (±4)² ≡ 5, (±5)² ≡ 3, so the only squares modulo 11 are 0, 1, 3, 4, 5, 9;
• m = 15 : then (±1)² ≡ 1, (±2)² ≡ 4, (±3)² ≡ 9, (±4)² ≡ 1, (±5)² ≡ 10, (±6)² ≡ 6, (±7)² ≡ 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 = p^r 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 . Since a is not divisible by p, neither is x. By Fermat’s little theorem, we get:

.

In short, if a is a square, then .

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

Let . Thanks to Fermat’s little theorem again, we have:

.

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

Let be an odd prime. For any a which is not divisible by p, let . 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 . E.g. take the case of p = 13 and a = 2, then we have .

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