Gauss's lemma (number theory) Created 2026-10-14 Updated 2026-11-05
Let be an odd prime and an integer with . Reduce
to their least positive residue classes modulo . If exactly of these representatives exceed , Gauss's lemma states
The symbol on the left is the Legendre symbol. For example, and give representatives . Exactly one exceeds , so is a quadratic nonresidue modulo .
For a proof, replace every representative above by its negative modulo , obtaining numbers in . These numbers are distinct: equality would give , forcing because . They therefore form a permutation of . Multiplying the signed representatives gives
The factorial is invertible modulo . Cancelling it and applying the Euler criterion proves the lemma. Counting signs can thus replace a potentially large modular exponentiation.
A short proof outline connects Gauss's lemma to counting points with integer coordinates. For distinct odd primes , define the two floor function sums
The parity form of Gauss's lemma gives and . In the open rectangle , , the line separates points below it from points above it. None lies on the line, because and coprimality would force . The total is therefore . Combining that count with the parity identities gives quadratic reciprocity.[ref]
Figure 1.
A line partitions the integer coordinate points behind the quadratic reciprocity exponent
. For , the counts are ; for , they are . Dashed edges mark the excluded boundary of the rectangle. This illustrates the counting step; the separate parity step from Gauss's lemma is essential to relate the count to Legendre symbols. Details.
The Legendre symbol is when is a nonzero square modulo the odd prime , when it is not a square, and when . For the coprime case, Euler's criterion states
Write . For , the balanced residues are nonzero and their absolute values lie in . If , then . Cancel . The plus sign forces ; the minus sign would require , impossible because . Thus the absolute residues form a permutation of . If exactly are negative, multiplying gives
Since does not divide , cancellation and Euler's criterion prove Gauss's lemma:
The two signs are distinct modulo the odd prime, so this congruence identifies the integer symbol itself.
For , the balanced representative of is negative precisely when , giving . Checking the four odd residue classes modulo eight gives even for and odd for . Hence
This is the quadratic character of two obtained from the lemma.
Let and . If a prime divides , then is odd and cannot divide . Moreover
so has an explicit nonzero square root modulo . The criterion just proved forces every prime divisor of into the classes or modulo eight. But : if all its prime factors were modulo eight, their product, with multiplicities, would also be . Thus at least one prime divisor is modulo eight. No listed divides , because . This always produces another such prime, proving infinitely many primes are congruent to seven modulo eight, the Euclid proof for infinitely many primes congruent to seven modulo eight.
For the displayed multiples are , already least positive residue classes. Those greater than correspond to . Thus their number is . For , its parity is respectively even, odd, odd, even. Gauss's lemma therefore gives
Second supplementary law for quadratic reciprocity Created 2026-09-24 Updated 2026-11-05
For every odd prime , the Legendre symbol of is
Thus is a quadratic residue for and a quadratic nonresidue for .
Apply Gauss's lemma to the representatives . With , exactly
exceed . For the four possible odd residues of modulo , this count has the same parity as . The lemma gives the formula. For example, at the representatives have two entries above , giving ; indeed .