Gauss's lemma (number theory) Created 2026-10-14 Updated 2026-11-05
Let be an odd prime and an integer with . Reduceto their least positive residue classes modulo . If exactly of these representatives exceed , Gauss's lemma statesThe 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 givesThe 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 sumsThe 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]
Quadratic Reciprocity by Ben Lynn. Ben Lynn, Quadratic Reciprocity, first theorem and proof of the Law of Quadratic Reciprocity: floor-sum parity and the separating-line count
Past exam of the mathematics course of the University of Cambridge 2001 ib Paper 2 17B Solution Created 2026-09-24 Updated 2026-10-14
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 statesWrite . 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 givesSince 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 . HenceThis is the quadratic character of two obtained from the lemma.
Let and . If a prime divides , then is odd and cannot divide . Moreoverso 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.
Gauss's lemma for quadratic residues states: if and is the number of least positive residue classes among that exceed , then .
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 isThus is a quadratic residue for and a quadratic nonresidue for .
