Gauss's Lemma (number Theory) - Proof

Proof

A fairly simple proof of the lemma, reminiscent of one of the simplest proofs of Fermat's little theorem, can be obtained by evaluating the product

modulo p in two different ways. On one hand it is equal to

The second evaluation takes more work. If x is a nonzero residue modulo p, let us define the "absolute value" of x to be

Since n counts those multiples ka which are in the latter range, and since for those multiples, −ka is in the first range, we have

Now observe that the values |ra| are distinct for r = 1, 2, ..., (p−1)/2. Indeed, if |ra| = |sa|, then ra = ±sa, and therefore r = ±s (because a is invertible modulo p), so r = s because they are both in the range 1 ≤ r ≤ (p−1)/2. But there are exactly (p−1)/2 of them, so they must just be some rearrangement of the integers 1, 2, ..., (p−1)/2. Therefore

Comparing with our first evaluation, we may cancel out the nonzero factor

and we are left with

This is the desired result, because by Euler's criterion the left hand side is just an alternative expression for the Legendre symbol (a/p).