Gauss's Lemma is needed to prove the Quadratic Reciprocity Theorem, that for odd primes p and q, (p/q) = (q/p) unless p ≡ q ≡ 3 (mod 4), in which case (p/q) = -(q/p), but it also has other uses.

Theorem (Gauss's Lemma) Suppose that p is an odd prime, p ∤ a, and that among the least residues (mod p) of a, 2a, …, ((p-1)/2)a exactly g are greater than (p - 1)/2. Then (a/p) = (-1)g.

Proof Divide the least residues (mod p) of a, 2a, …, ((p - 1)/2)a into two classes: r1, r2, …, rk that are less than or equal to (p - 1)/2 and s1, s2, …, sg that are greater than (p - 1)/2. Then k + g = (p - 1)/2. By Euler's Criterion, to prove the theorem it is enough to show that a(p-1)/2 ≡ (-1)g (mod p).

No two of r1, r2, …, rk are congruent (mod p). If they were we would have k1a ≡ k2a (mod p) and, because (a, p) = 1, k1 ≡ k2 (mod p). Because k1 and k1 are both in the interval [1, (p -1)/2] we have k1 = k1.