Gauss's Lemma

Fix an odd prime pp and an integer aa not divisible by pp. Multiply the numbers 1,2,…,p−121, 2, \dots, \tfrac{p-1}{2} by aa. Reduce each product to the residue in the range (−p/2,p/2)(-p/2, p/2). Count how many of these residues come out negative. Gauss's Lemma asserts that the parity of this count determines the answer. It tells us exactly whether aa is a quadratic residue or nonresidue mod pp. This is a strange and beautiful fact. A purely arithmetic sign-counting exercise reproduces deep multiplicative structure. That structure is encoded in the Legendre Symbol. The result matters for two reasons. First, it converts an abstract question into a mechanical computation. The question "is aa a square mod pp?" becomes: count sign changes. Second, it is the load-bearing lemma underneath the Law of Quadratic Reciprocity. Gauss himself used a version of this counting argument. It appears in several of his eight proofs of reciprocity. It bridges two ideas. One is Euler's Criterion, an existence-flavored characterization via a(p−1)/2a^{(p-1)/2}. The other is geometric lattice-point counting, which eventually yields reciprocity. The big picture is this. Quadratic residues mod pp form an index-2 subgroup of (Z/pZ)×(\mathbb{Z}/p\mathbb{Z})^\times. Legendre's symbol (ap)\left(\frac{a}{p}\right) is the corresponding sign character. Euler's criterion identifies this character with a(p−1)/2  pa^{(p-1)/2} \bmod p. Gauss's Lemma gives a second, independent identification. This one works via parity of sign flips among least residues. The fact that these two characterizations agree is itself a small miracle. It is worth proving carefully. Once proved, the lemma becomes a computational engine. It will let us evaluate (2p)\left(\frac{2}{p}\right) outright. It will also supply the geometric heart of the proof of reciprocity itself. This article gives the precise statement. It includes a complete proof from first principles, using only elementary facts about residues. It offers two fully computed numerical examples with asymmetric inputs. It discusses exactly which hypotheses are load-bearing. Finally, it looks at where the lemma sits historically and in modern applications.

Key takeaways
  • Gauss's Lemma expresses (ap)\left(\frac{a}{p}\right) as (−1)μ(-1)^\mu, where μ\mu counts negative least residues among a⋅1,a⋅2,…,a⋅p−12(modp)a\cdot 1, a\cdot 2, \dots, a\cdot\tfrac{p-1}{2} \pmod p.
  • It requires pp an odd prime and gcd⁡(a,p)=1\gcd(a,p)=1; both hypotheses are essential.
  • The proof multiplies the least-residues together and compares the result to 1⋅2⋯p−121\cdot 2\cdots \tfrac{p-1}{2}, using unique reduction mod pp.
  • It gives an independent, purely combinatorial route to Euler's criterion's conclusion, without invoking Fermat's Little Theorem directly on aa.
  • It is the direct ancestor of the geometric lattice-point argument (Eisenstein's proof) for the Law of Quadratic Reciprocity.
  • It immediately computes (2p)\left(\frac{2}{p}\right) and other small supplementary symbols.
  • Key idea: counting sign flips of least residues under multiplication by aa exactly detects whether aa is a square mod pp.

Where this lives today

Gauss's Lemma is the direct technical predecessor of the supplementary laws of quadratic reciprocity: applying it with a=−1a = -1 recovers (−1p)=(−1)(p−1)/2\left(\frac{-1}{p}\right) = (-1)^{(p-1)/2} by counting that every element of the half-system flips sign, and applying it with a=2a = 2 (via a short lattice-point count of how many multiples 2i2i exceed p/2p/2) gives (2p)=(−1)(p2−1)/8\left(\frac{2}{p}\right) = (-1)^{(p^2-1)/8}. Both supplementary laws are usually proved as corollaries of exactly this counting method before the full Law of Quadratic Reciprocity is attempted. In modern terms, Gauss's Lemma is one of the earliest instances of a sign character computation via a group action: (Z/pZ)×(\mathbb{Z}/p\mathbb{Z})^\times acting on itself by multiplication, tracked through a fundamental domain (−p/2,p/2)(-p/2, p/2), produces a cocycle whose value is exactly the Legendre symbol. This viewpoint generalizes to more elaborate reciprocity laws (cubic and biquadratic reciprocity, and Hilbert reciprocity for local fields), where analogous "sign" or "residue symbol" counting arguments recur. Computationally, algorithms for quadratic residuosity testing — relevant to primality tests and to cryptographic protocols relying on the quadratic residuosity assumption (e.g. Goldwasser–Micali encryption) — ultimately rest on the equivalence between Euler's criterion and this sign-counting description, since both give independently checkable routes to the same bit of information. In computational number theory courses, the lemma is frequently used as a hand-computable cross-check against modular exponentiation when verifying quadratic residue tables by two different methods.

Ask the tutor: How does Gauss's Lemma with a=2a=2 get refined into the full geometric lattice-point proof of quadratic reciprocity?

DefinitionLeast residue and Gauss's sign count

Let pp be an odd prime and let nn be any integer with p∤np \nmid n. The least residue of nn modulo pp, denoted n∗n^*, is the unique integer in the range

−p2<n∗<p2,n∗≡n(modp).-\frac{p}{2} < n^* < \frac{p}{2}, \qquad n^* \equiv n \pmod p .

(Since pp is odd, n∗n^* is never equal to ±p/2\pm p/2, so this range is unambiguous and n∗≠0n^*\neq 0 whenever p∤np\nmid n.) Now fix an integer aa with gcd⁡(a,p)=1\gcd(a,p) = 1, and consider the half-system

1, 2, 3, …, p−12.1, \ 2, \ 3, \ \dots, \ \frac{p-1}{2}.

Form the products a⋅1,a⋅2,…,a⋅p−12a\cdot 1, a\cdot 2, \dots, a\cdot \tfrac{p-1}{2} and let r1,r2,…,r(p−1)/2r_1, r_2, \dots, r_{(p-1)/2} be their least residues mod pp. Define

μ(a,p)  =  #{ i:ri<0 },\mu(a,p) \;=\; \#\{\, i : r_i < 0 \,\},

the number of these least residues that are negative. Gauss's Lemma computes the Legendre symbol (ap)\left(\frac{a}{p}\right) in terms of the parity of μ(a,p)\mu(a,p).

Intuition

Think of the integers mod pp arranged symmetrically around 00, from −p−12-\tfrac{p-1}{2} up to p−12\tfrac{p-1}{2}, instead of the usual 00 to p−1p-1. Multiplying by aa permutes the nonzero residues; the question is how many of the "positive half" {1,…,p−12}\{1,\dots,\tfrac{p-1}{2}\} get thrown, after reduction, into the "negative half" {−p−12,…,−1}\{-\tfrac{p-1}{2},\dots,-1\}. If a=1a=1, nothing moves: μ=0\mu = 0, even, and indeed 11 is always a square. If a=−1a = -1, every single element of the positive half maps to its negative, so μ=p−12\mu = \tfrac{p-1}{2}; this count is even exactly when p≡1(mod4)p \equiv 1 \pmod 4, matching the classical fact (−1p)=(−1)(p−1)/2\left(\frac{-1}{p}\right) = (-1)^{(p-1)/2}. The lemma says this parity phenomenon is completely general: whenever aa is a nonresidue, multiplication by aa must push an odd number of elements across the sign line, and whenever aa is a residue, an even number cross. The picture below shows p=13p = 13, a=2a = 2. We track where each of 1,2,3,4,5,61,2,3,4,5,6 lands after multiplying by 22 and reducing to (−6.5,6.5)(-6.5, 6.5).

Figure
Sign changes for a=2a=2, p=13p=13: multiplying the half-system 1,…,61,\dots,6 by 22 and reducing mod 1313 to (−6.5,6.5)(-6.5,6.5)
n 2n mod 13 1 2 3 4 5 6 -6 0 6 negative least residues positive least residues 2 4 6 -5 -3 -1

In this picture, n=4,5,6n = 4,5,6 land in the negative zone: that is μ=3\mu = 3, an odd count, so the lemma predicts (213)=(−1)3=−1\left(\frac{2}{13}\right) = (-1)^3 = -1. Indeed 22 is not a square mod 1313 (the squares mod 1313 are 1,4,9,3,12,101,4,9,3,12,10), confirming the prediction.

TheoremGauss's Lemma

Let pp be an odd prime, and let a∈Za \in \mathbb{Z} with gcd⁡(a,p)=1\gcd(a,p) = 1. Let μ=μ(a,p)\mu = \mu(a,p) be the number of negative least residues among

a⋅1, a⋅2, …, a⋅p−12(modp),a\cdot 1,\ a \cdot 2,\ \dots,\ a\cdot \frac{p-1}{2} \pmod p,

as in the Definition above. Then

(ap)=(−1)μ.\left(\frac{a}{p}\right) = (-1)^{\mu}.
Proof

Setup. Write m=p−12m = \tfrac{p-1}{2}. For i=1,…,mi = 1, \dots, m, let rir_i be the least residue of aiai mod pp, so ri∈(−p2,p2)r_i \in \left(-\tfrac{p}{2}, \tfrac{p}{2}\right) and ri≡ai(modp)r_i \equiv ai \pmod p. Since p∤ap \nmid a and p∤ip \nmid i (as 1≤i≤m<p1 \le i \le m < p), we have p∤aip \nmid ai, so ri≠0r_i \neq 0 for every ii. Write εi=sign⁡(ri)∈{+1,−1}\varepsilon_i = \operatorname{sign}(r_i) \in \{+1,-1\} and si=∣ri∣∈{1,2,…,m}s_i = |r_i| \in \{1, 2, \dots, m\}, so that

ai≡ri=εisi(modp),i=1,…,m.ai \equiv r_i = \varepsilon_i s_i \pmod p, \qquad i = 1,\dots,m.

By definition, μ\mu is exactly the number of indices ii with εi=−1\varepsilon_i = -1, so

∏i=1mεi=(−1)μ.(1)\prod_{i=1}^m \varepsilon_i = (-1)^{\mu}. \tag{1}

Step 1: the values s1,…,sms_1, \dots, s_m are a permutation of 1,…,m1, \dots, m. Each sis_i lies in {1,…,m}\{1,\dots,m\} by construction, and there are mm of them, so it suffices to show the map i↦sii \mapsto s_i is injective on {1,…,m}\{1,\dots,m\}. Suppose si=sjs_i = s_j for some 1≤i,j≤m1 \le i, j \le m. Then ri=±rjr_i = \pm r_j, i.e. ai≡±aj(modp)ai \equiv \pm aj \pmod p. Since gcd⁡(a,p)=1\gcd(a,p)=1, aa is invertible mod pp, so this gives i≡±j(modp)i \equiv \pm j \pmod p.

  • If i≡j(modp)i \equiv j \pmod p: since 1≤i,j≤m<p1 \le i, j \le m < p, we get ∣i−j∣<p|i - j| < p, so i≡j(modp)i \equiv j \pmod p forces i=ji = j.
  • If i≡−j(modp)i \equiv -j \pmod p: then p∣(i+j)p \mid (i+j). But 1≤i,j≤m=p−121 \le i, j \le m = \tfrac{p-1}{2}, so 2≤i+j≤p−1<p2 \le i+j \le p - 1 < p, and the only multiple of pp in this range would have to be 00, impossible since i+j≥2i + j \ge 2. So this case cannot occur (unless we also already have i=ji=j from the first case forcing i+ji+j even, but we've shown outright p∣(i+j)p\mid(i+j) is impossible here).

Hence i≡j(modp)i \equiv j \pmod p is the only possibility, forcing i=ji = j. So i↦sii \mapsto s_i is injective, and since it maps the mm-element set {1,…,m}\{1,\dots,m\} into itself injectively, it is a bijection. That is,

{s1,…,sm}={1,2,…,m}as sets (with multiplicity one each).(2)\{s_1, \dots, s_m\} = \{1, 2, \dots, m\} \quad \text{as sets (with multiplicity one each).} \tag{2}

Step 2: multiply everything together. From ai≡εisi(modp)ai \equiv \varepsilon_i s_i \pmod p for each ii, take the product over i=1,…,mi = 1, \dots, m:

am⋅(1⋅2⋯m)=am∏i=1mi  ≡  ∏i=1mεisi  =  (∏i=1mεi)(∏i=1msi)(modp).a^m \cdot (1 \cdot 2 \cdots m) = a^m \prod_{i=1}^m i \;\equiv\; \prod_{i=1}^m \varepsilon_i s_i \;=\; \left(\prod_{i=1}^m \varepsilon_i\right)\left(\prod_{i=1}^m s_i\right) \pmod p.

By (2), ∏i=1msi=∏i=1mi=m!\prod_{i=1}^m s_i = \prod_{i=1}^m i = m! (the same product, just reordered — multiplication is commutative). So

am⋅m!  ≡  (∏i=1mεi)⋅m!(modp).a^m \cdot m! \;\equiv\; \left(\prod_{i=1}^m \varepsilon_i\right) \cdot m! \pmod p.

Since pp is prime and m!=1⋅2⋯mm! = 1 \cdot 2 \cdots m is a product of integers each strictly between 00 and pp, we have p∤m!p \nmid m!; hence m!m! is invertible mod pp and we may cancel it:

am≡∏i=1mεi(modp).(3)a^m \equiv \prod_{i=1}^m \varepsilon_i \pmod p. \tag{3}

Step 3: identify am  pa^m \bmod p via Euler's Criterion. By Euler's Criterion, since gcd⁡(a,p)=1\gcd(a,p) = 1,

a(p−1)/2=am≡(ap)(modp).a^{(p-1)/2} = a^m \equiv \left(\frac{a}{p}\right) \pmod p.

Combining with (3):

(ap)≡∏i=1mεi(modp).\left(\frac{a}{p}\right) \equiv \prod_{i=1}^m \varepsilon_i \pmod p.

Both sides lie in {1,−1}\{1,-1\}, and since pp is odd, p≥3p \ge 3, so 1≢−1(modp)1 \not\equiv -1 \pmod p; congruence mod pp between two elements of {1,−1}\{1,-1\} forces actual equality. Hence

(ap)=∏i=1mεi.\left(\frac{a}{p}\right) = \prod_{i=1}^m \varepsilon_i.

By (1), the right side equals (−1)μ(-1)^\mu. Therefore

(ap)=(−1)μ,\left(\frac{a}{p}\right) = (-1)^\mu,

which is the assertion of the theorem. ■\blacksquare

∎

Worked examples

Example 1: a=5a = 5, p=17p = 17 (asymmetric, no shortcut). Here p=17p = 17 is odd prime, gcd⁡(5,17)=1\gcd(5,17) = 1, and m=p−12=8m = \tfrac{p-1}{2} = 8. We compute 5i5i for i=1,…,8i = 1,\dots,8, reduce mod 1717, and take least residues in (−8.5,8.5)(-8.5, 8.5).

ii5i5i5i  175i \bmod 17 (in [0,16][0,16])least residue rir_isign
1555+
2101010−17=−710 - 17 = -7−-
3151515−17=−215-17=-2−-
42033+
52588+
6301313−17=−413-17=-4−-
73511+
84066+

Check Step 1's claim: the absolute values of the least residues are 5,7,2,3,8,4,1,65,7,2,3,8,4,1,6 — indeed a permutation of {1,…,8}\{1,\dots,8\}, confirming (2). Count negative entries: i=2,3,6i = 2,3,6 give negative least residues, so μ=3\mu = 3, odd. Gauss's Lemma predicts

(517)=(−1)3=−1.\left(\frac{5}{17}\right) = (-1)^3 = -1.

Independent check via Euler's criterion. We need 58  175^8 \bmod 17. Compute stepwise: 52=25≡85^2 = 25 \equiv 8; 54≡82=64≡64−51=13≡−45^4 \equiv 8^2 = 64 \equiv 64 - 51 = 13 \equiv -4; 58≡(−4)2=16≡−1(mod17)5^8 \equiv (-4)^2 = 16 \equiv -1 \pmod{17}. So 58≡−1(mod17)5^{8} \equiv -1 \pmod{17}, confirming (517)=−1\left(\frac{5}{17}\right) = -1 directly, matching the lemma's prediction. (Indeed the squares mod 17 are 1,4,9,16,8,2,15,131,4,9,16,8,2,15,13 — the list {1,2,4,8,9,13,15,16}\{1,2,4,8,9,13,15,16\} — and 55 is not among them.)

Example 2: a=7a = 7, p=19p = 19 (a second independent check, larger and asymmetric). Here p=19p = 19, m=9m = 9, gcd⁡(7,19)=1\gcd(7,19)=1. Compute 7i  197i \bmod 19 for i=1,…,9i=1,\dots,9 and take least residues in (−9.5,9.5)(-9.5,9.5).

ii7i7imod 19 (in [0,18][0,18])least residue rir_isign
1777+
2141414−19=−514-19=-5−-
32122+
42899+
5351616−19=−316-19=-3−-
64244+
7491111−19=−811-19=-8−-
8561818−19=−118-19=-1−-
96366+

Absolute values: 7,5,2,9,3,4,8,1,67,5,2,9,3,4,8,1,6 — a permutation of {1,…,9}\{1,\dots,9\} as required. Negative entries occur at i=2,5,7,8i=2,5,7,8: that's μ=4\mu = 4, even. Gauss's Lemma predicts

(719)=(−1)4=1,\left(\frac{7}{19}\right) = (-1)^4 = 1,

i.e. 77 should be a quadratic residue mod 1919.

Verification: indeed 92=81=4⋅19+59^2 = 81 = 4\cdot 19 + 5... let's directly search: squares mod 19 are 1,4,9,16,6,17,11,7,51,4,9,16,6,17,11,7,5 (from 12,…,921^2,\dots,9^2). Since 82=64=3⋅19+7≡78^2 = 64 = 3\cdot19+7 \equiv 7, we confirm 7≡82(mod19)7 \equiv 8^2 \pmod {19} is indeed a square, matching μ\mu even. Also by Euler: 79  197^9 \bmod 19. Compute 72=49≡117^2=49\equiv 11; 74≡112=121≡121−114=77^4 \equiv 11^2=121\equiv 121-114=7; 78≡72=49≡117^8\equiv 7^2=49\equiv 11; 79≡11⋅7=77≡77−76=1(mod19)7^9 \equiv 11\cdot 7 = 77 \equiv 77-76=1\pmod{19}. So 79≡17^9\equiv1, confirming (719)=1\left(\frac{7}{19}\right)=1.

Counterexampledropping "pp odd prime"

Gauss's Lemma is stated for odd primes pp; the entire proof leans on this via three places: the half-system 1,…,p−121,\dots,\tfrac{p-1}{2} requires pp odd to be a well-defined integer count, the injectivity argument in Step 1 uses that pp is prime so that aa is invertible mod pp, and the cancellation of m!m! in Step 2 uses that pp is prime so p∤m!p \nmid m!. To see what breaks if we merely drop primality (keep pp odd, but let pp be composite), take p=9p = 9 and a=2a = 2, with gcd⁡(2,9)=1\gcd(2,9)=1. Here m=p−12=4m = \tfrac{p-1}{2} = 4, and we would attempt least residues of 2⋅1,2⋅2,2⋅3,2⋅4=2,4,6,82\cdot 1, 2\cdot2, 2\cdot3, 2\cdot4 = 2,4,6,8 reduced into (−4.5,4.5)(-4.5,4.5): these are 2,4,6−9=−3,8−9=−12, 4, 6-9=-3, 8-9=-1. So μ=2\mu = 2 (even), and the "lemma" would predict (29)1\left(\frac{2}{9}\right) \overset{?}{=} 1. But the Legendre symbol (ap)\left(\frac{a}{p}\right) is only defined for pp an odd prime; for composite modulus one must instead use the Jacobi symbol, and the Jacobi symbol does not detect being a quadratic residue mod 99 in general. Indeed 22 is not a square mod 99 (squares mod 9 are 0,1,4,70,1,4,7), yet the sign-count procedure above still runs and outputs a definite parity — it simply is not computing a Legendre symbol at all, because none exists for composite pp. Worse, the key algebraic identity from Step 1, that ∣ri∣|r_i| ranges over a full permutation of {1,…,m}\{1,\dots,m\}, can fail outright for composite pp: it relied on p∣(i+j)⇒p \mid (i+j) \Rightarrow contradiction using that the only way i≡ji\equiv j or i≡−j(modp)i \equiv -j\pmod p forces literal equality — an argument valid for any pp, actually, but the deeper link to Euler's criterion (Step 3) is where primality is truly indispensable, since Euler's Criterion itself is a theorem about primes. Composite pp voids the bridge between the sign-count and any multiplicative character, so the "lemma" becomes a numerology exercise with no number-theoretic content.

Scope, edge cases & common traps

SituationWhat happens
p=2p = 2Excluded: p−12=0\tfrac{p-1}{2} = 0, the half-system is empty, and the Legendre symbol mod 22 is not part of the usual theory.
p∣ap \mid aExcluded: Legendre symbol is defined to be 00; the least residues of a⋅ia\cdot i would include 00, breaking the sign-count entirely.
aa negativeFine — the lemma applies to any integer aa coprime to pp, positive or negative; just compute least residues of aiai as stated.
pp compositeInvalid; see counterexample above — no Legendre symbol exists to equate the count to.
Confusing μ(a,p)\mu(a,p) with μ(b,p)\mu(b,p) for a≡b(modp)a \equiv b \pmod pμ\mu itself can differ for aa and b≡a(modp)b\equiv a\pmod p (it depends on the actual representative chosen for the "multiplier," not just the residue class), but the parity (−1)μ(-1)^{\mu} is a class invariant, since it must always equal (ap)\left(\frac{a}{p}\right), which only depends on a  pa\bmod p.

The mathematician behind it

Origins · 1 minCarl Friedrich Gauss and how this was discovered
CF
Carl Friedrich Gauss
1777–1855 · Göttingen, Germany

Gauss developed this lemma as part of his lifelong obsession with the Law of Quadratic Reciprocity, which he called the "golden theorem" (theorema aureum) and proved by essentially this counting technique among his several independent proofs (he eventually gave eight). Gauss's Disquisitiones Arithmeticae (1801) systematized modular arithmetic itself, introducing the congruence notation still used today, and quadratic residues were one of its central topics. The lemma bearing his name appears as a tool refined across his second, third, and later proofs of reciprocity, illustrating his practice of returning to a single theorem repeatedly to extract ever more structural understanding.

History
- 1796 — Gauss, at age 19, discovers his first proof of quadratic reciprocity.
- 1801 — Disquisitiones Arithmeticae published, systematizing residues, congruences, and reciprocity.
- 1808 — Gauss publishes further proofs of reciprocity using the least-residue counting technique now called Gauss's Lemma.
- 1844–1845 — Ferdinand Eisenstein refines the lemma into a geometric lattice-point count, giving a cleaner path from Gauss's Lemma directly to reciprocity.
- 20th century — the lemma becomes a standard textbook stepping-stone (e.g. in Hardy & Wright, Ireland & Rosen) between Euler's Criterion and full reciprocity.
What exactly does μ(a,p)\mu(a,p) count, in plain language?

It counts how many of the numbers a,2a,3a,…,p−12⋅aa, 2a, 3a, \dots, \tfrac{p-1}{2}\cdot a, after being reduced modulo pp into the symmetric range (−p/2,p/2)(-p/2, p/2), land on the negative side. Concretely: take each multiple, subtract off the nearest multiple of pp so the result is as small in absolute value as possible, and check its sign. If that "balanced remainder" is negative, it contributes to the count. The parity (even or odd) of this count is what the lemma links directly to whether aa is a square mod pp.

Why is this called a "lemma" rather than a theorem, given how much work the proof takes?

Historically it is termed a lemma because in Gauss's own development, and in the standard modern treatment, its main role is as a stepping stone toward the Law of Quadratic Reciprocity, which is regarded as the theorem the whole subject is building toward. In terms of pure logical content, though, Gauss's Lemma is a complete, self-contained, non-trivial result: it fully computes the Legendre symbol via an independent combinatorial method, and could reasonably stand as a theorem in its own right. The naming reflects its historical function more than its logical weight.

Does the value of μ(a,p)\mu(a,p) itself depend on the choice of representative for aa, or only its parity?

The exact integer μ(a,p)\mu(a,p) can genuinely change if you replace aa by a+pa + p (a different representative of the same residue class), because the actual least residues computed will differ. What Gauss's Lemma guarantees is that the parity of μ\mu — whether it's even or odd — depends only on the residue class of aa mod pp, because that parity always equals (ap)∈{1,−1}\left(\frac{a}{p}\right) \in \{1,-1\}, a quantity that manifestly only depends on a  pa \bmod p. So μ\mu is representative-dependent but (−1)μ(-1)^\mu is not.

How does Gauss's Lemma relate to Euler's Criterion — are they saying the same thing?

They characterize the same object, (ap)\left(\frac{a}{p}\right), via two logically different routes. Euler's Criterion identifies it with a(p−1)/2  pa^{(p-1)/2}\bmod p, an algebraic/exponential description tied to the cyclic structure of (Z/pZ)×(\mathbb{Z}/p\mathbb{Z})^\times. Gauss's Lemma identifies it with (−1)μ(-1)^\mu, a combinatorial/geometric description tied to counting sign flips. The proof of Gauss's Lemma in fact uses Euler's Criterion as one ingredient (Step 3), so logically Gauss's Lemma is a refinement built on top of Euler's Criterion, translating an exponential fact into a directly countable one.

Can Gauss's Lemma be used to compute (2p)\left(\frac{2}{p}\right) directly?

Yes, and this is one of its most quoted applications. Applying the lemma with a=2a=2, one counts how many multiples 2,4,6,…,p−12, 4, 6, \dots, p-1 exceed p/2p/2 before reduction (since doubling numbers below p/2p/2 never wraps around, only those pushing past p/2p/2 need reduction, each contributing exactly one negative least residue). A short case analysis on p  8p \bmod 8 shows this count's parity matches (p2−1)/8  2(p^2-1)/8 \bmod 2, yielding the classical supplementary law (2p)=(−1)(p2−1)/8\left(\frac{2}{p}\right) = (-1)^{(p^2-1)/8}, i.e. (2p)=1\left(\frac{2}{p}\right)=1 exactly when p≡±1(mod8)p \equiv \pm 1 \pmod 8.

Is there a slicker, geometric way to see why the lemma is true?

Yes — this is essentially Eisenstein's refinement. One shows μ\mu equals the number of lattice points (x,y)(x,y) with integer xx satisfying 1≤x≤p−121 \le x \le \tfrac{p-1}{2} that make ax  pax \bmod p land in the upper half, translated into a count of lattice points strictly below a certain line segment in a rectangle. This reformulation is what lets Eisenstein push the same idea into a symmetric double-counting argument for two primes p,qp, q simultaneously, which is precisely the mechanism that proves full quadratic reciprocity.

Does Gauss's Lemma generalize beyond quadratic residues, e.g. to cubic residues?

The literal statement is specific to quadratic residues and the Legendre symbol, since it is built on the sign involution x↦−xx \mapsto -x, which only has order 22. However, the underlying strategy — track an action of the multiplicative group on residues through a chosen fundamental domain, and extract a character value from the resulting combinatorics — has analogues in higher reciprocity laws (cubic, biquadratic, and general power residue symbols), though those require replacing "sign" with roots of unity of higher order and a correspondingly more elaborate bookkeeping device.

Before this

Where this leads