For a prime number , let be the sum of the least positive quadratic residues below . Then
For example, at the relevant quadratic residues are , and their sum is .
To prove the identity, put , let be the sum of all least positive nonzero quadratic residues, and let count those above . The second supplementary law for quadratic reciprocity gives , so doubling permutes these residue classes. Reducing each doubled representative modulo subtracts exactly times. Hence , or .
Since , the first supplementary law for quadratic reciprocity says is a quadratic nonresidue. Exactly one of is therefore a quadratic residue for each . The lower-half choices sum to ; the upper-half choices sum to . Consequently
Substituting gives . Both congruence conditions have a role: one makes doubling a permutation, and the other makes each opposite pair contain exactly one quadratic residue.
For an odd prime , the number of integers such that both and are quadratic residues modulo is
For example, modulo the quadratic residues are . The qualifying pairs are and , giving .
Write for the Legendre symbol. On the specified range neither input is zero, so the indicator of the required event is . Expand and sum. The complete Legendre-symbol sum gives
The quadratic Legendre-symbol correlation gives : extending to the full finite field only adds the zero terms at . Thus the count is . The first supplementary law for quadratic reciprocity identifies and completes the formula.
Suppose . Then is a unit modulo n for modulus , and Fermat's little theorem implies
Since is an odd prime number, and are distinct residue classes. Therefore is even, and .
Conversely, put . Pair each integer with in the factorial. Wilson theorem yields
When , is even, so satisfies . This proves the first supplementary law for quadratic reciprocity without assuming a primitive root. Hence
The two solutions are and modulo : their difference is nonzero, and factoring shows that a degree-two polynomial over the field of residues modulo has no further roots.
Gauss lemma states that if and of the least positive residues of
exceed , then .
To prove it, replace each residue exceeding by its negative, obtaining numbers in . No two of them are equal modulo : such an equality would give , hence in the allowed range. They therefore permute , and multiplication gives
Cancel the nonzero factorial and apply Euler's criterion to obtain the lemma.
For , all least positive residues exceed . Hence the first supplementary law for quadratic reciprocity is
For an odd prime , the Legendre symbol is
Euler criterion states that
If , both sides vanish. Otherwise choose a primitive root and write . Since ,
The power is a square exactly when is even, proving the criterion. Taking gives the first supplementary law for quadratic reciprocity
Write . When , the first supplementary law for quadratic reciprocity gives , so . Pairing with gives
The sum of the nontrivial character over all nonzero residue classes is zero. Because its two half-sums are equal when ,
Hence
The first supplementary law for quadratic reciprocity is
It also follows immediately from Euler's criterion applied to .
Euler's criterion states, for an odd prime ,
Apply it to . The integer is when and when . Since those signs are distinct modulo an odd prime, the modular congruence determines the actual Legendre symbol:
This is the first supplementary law for quadratic reciprocity.
For distinct odd primes , quadratic reciprocity states
Here the Legendre symbol records whether a nonzero congruence class is a quadratic residue. The first supplementary law for quadratic reciprocity and second supplementary law for quadratic reciprocity give
Thus minus one is a square exactly when , and two is a square exactly when or .
To test the specified congruence class, factor . Since , multiplicativity of the Legendre symbol and quadratic reciprocity yield
There is no sign change on swapping and because . Finally , so multiplicativity of the Legendre symbol gives , since . Therefore
Quadratic reciprocity Created 2026-09-24 Updated 2026-10-13
Quadratic reciprocity compares two questions: is the prime number a quadratic residue modulo , and is a quadratic residue modulo ? Let be distinct odd primes. In terms of the Legendre symbol,
The two Legendre symbols have opposite signs exactly when both primes are modulo ; otherwise they are equal. Their values are nonzero because the primes are distinct. Equal signs can mean two quadratic residues or two quadratic nonresidues: reciprocity compares the answers rather than declaring either answer positive.[ref]
For a direct computation, the nonzero quadratic residues modulo are respectively , , and . Squaring just suffices because and have the same square modulo an odd prime .
The pair has a sign flip, whereas has two negative signs. These small quadratic residue tables make the distinction tangible.
Figure 1.
Small prime square-residue tables distinguish opposite and equal Legendre symbol signs
. Each row uses half the nonzero inputs; the missing entries are unnecessary. The comparisons and are exact finite examples of quadratic reciprocity, not evidence by themselves for every prime pair. Details.
The first supplementary law for quadratic reciprocity handles numerator , and the second supplementary law for quadratic reciprocity handles numerator :
For an odd prime , is a quadratic residue exactly when , while is a quadratic residue exactly when . The remaining odd congruence classes modulo , namely , make a quadratic nonresidue. These laws fill the cases excluded from swapping distinct odd primes.[ref]
Square root of minus one modulo a prime Created 2026-10-07 Updated 2026-11-05
The quadratic congruence is soluble exactly when or . At , take .
For an odd prime , any solution is nonzero modulo . Fermat's little theorem gives
so is even and . Conversely, put when . Pairing opposite factors in the factorial gives
Wilson's theorem therefore gives , constructing a solution. For example, at the construction gives and . The criterion is the first supplementary law for quadratic reciprocity expressed as existence of a square root.
Weighted complete Legendre-symbol sum Created 2026-09-24 Updated 2026-11-05
For an odd prime , put
Then if , and for every .
For the first statement, the first supplementary law for quadratic reciprocity gives , where is the Legendre symbol. Pairing with gives
The same pairing in the complete Legendre-symbol sum shows that this half sum is zero, proving the exact equality.
For the second statement, multiplication by permutes the nonzero residue classes modulo . Reducing the weighted sum modulo and using multiplicativity of the Legendre symbol therefore gives . The coefficient is either or , and hence is invertible for . Thus . The restriction is necessary: at , .