Lower-half quadratic-residue sum for primes congruent to seven modulo eight Created 2026-09-24 Updated 2026-11-05
For a prime number , let be the sum of the least positive quadratic residues below . ThenFor 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 . ConsequentlySubstituting gives . Both congruence conditions have a role: one makes doubling a permutation, and the other makes each opposite pair contain exactly one quadratic residue.
Number of consecutive nonzero quadratic residues modulo an odd prime Created 2026-09-29 Updated 2026-11-05
For an odd prime , the number of integers such that both and are quadratic residues modulo isFor 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 givesThe 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.
Past exam of the mathematics course of the University of Cambridge 2017 ia Paper 4 5D b Solution Created 2026-09-24 Updated 2026-10-05
Suppose . Then is a unit modulo n for modulus , and Fermat's little theorem impliesSince 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 yieldsWhen , is even, so satisfies . This proves the first supplementary law for quadratic reciprocity without assuming a primitive root. HenceThe 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.
Past exam of the mathematics course of the University of Cambridge 2020 ii Paper 3 11H ii Solution Created 2026-09-24 Updated 2026-10-03
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 givesCancel 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
Past exam of the mathematics course of the University of Cambridge 2023 ii Paper 4 11G a Solution Created 2026-09-24 Updated 2026-09-25
For an odd prime , the Legendre symbol isEuler criterion states thatIf , 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
Past exam of the mathematics course of the University of Cambridge 2023 ii Paper 4 11G c i Solution Created 2026-09-24 Updated 2026-09-25
Write . When , the first supplementary law for quadratic reciprocity gives , so . Pairing with givesThe 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 isIt also follows immediately from Euler's criterion applied to .
The first supplementary law for quadratic reciprocity isIt 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 statesHere 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 giveThus 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 yieldThere 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]
NIST Digital Library of Mathematical Functions. T. M. Apostol, Chapter 27, §27.9, equation 27.9.3: distinct odd prime hypotheses and reciprocity law
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.
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
For an odd prime , any solution is nonzero modulo . Fermat's little theorem givesso is even and . Conversely, put when . Pairing opposite factors in the factorial givesWilson'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 the first statement, the first supplementary law for quadratic reciprocity gives , where is the Legendre symbol. Pairing with givesThe 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 , .
