Motivation
The equation asks whether a particular residue belongs to the image of squaring. A primitive root converts it into an exponent congruence, but computing a discrete logarithm may be unnecessary work. Quadratic reciprocity instead compares two different prime moduli. Together with a few elementary supplementary rules, it reduces many residue questions to much smaller ones.
There are several logical stages. First recognize the two possible signs attached to a nonzero residue. Next recover that sign from a finite permutation of signed residues. Finally count the same rectangle of lattice points in two ways. The proof will explain the reciprocity sign rather than asking the reader to memorize an unexplained exception when two primes are three modulo four.
All primes in the main argument are odd. The field root bound, Fermat's theorem for prime moduli, and elementary congruence arithmetic were proved in earlier notes. No statement about all composite moduli is silently obtained by replacing a prime with an odd integer.
Definitions
Definition 6.1.1
(Quadratic residues and the Legendre symbol)
For an odd prime , a nonzero residue is a quadratic residue when for some . Otherwise it is a quadratic nonresidue. Define
This Legendre symbol depends on the numerator only modulo . It is not a fraction, and an operation resembling cancellation of fractions has no meaning without a proved symbol identity.
Exactly nonzero classes are squares. The squaring map on the nonzero classes identifies exactly the pair : equality gives in the field, hence or , and these two choices are distinct in odd characteristic. This elementary count supplies the input for Euler's criterion below.
Concept lensAlgebraic
The symbol as the parity of a discrete logarithm
If is a primitive root modulo and with , then
Exponents are read modulo the even number , so the parity of is well defined. An even exponent is visibly a square, and conversely gives , an even exponent. In this description the symbol is the unique surjective homomorphism from the cyclic unit group onto , and multiplicativity in the numerator is immediate.
Theorems
Theorem 6.1.2
(Euler's criterion and Gauss's lemma)
For , Euler's criterion is
Set . For , let be the least positive residue of modulo , and let count those . Then
Theorem 6.1.3
(Quadratic reciprocity and its supplementary laws)
For distinct odd primes ,
For every odd prime ,
The two reciprocal symbols have opposite signs exactly when both primes are three modulo four; in the other cases they agree.
Proof sketch or proof idea
Proof
(Euler's criterion by counting squares)
Let . Every nonzero square satisfies modulo by Fermat. There are exactly such classes. The polynomial has at most roots in the field, so no nonsquare satisfies this equation. For any unit , Fermat also gives . Factoring the difference of squares shows is either one or minus one. A nonsquare must therefore give minus one, proving Euler's criterion.
It follows that the symbol is multiplicative in its numerator. For units , Euler's criterion makes the product of the two corresponding signs. Since one and minus one are distinct modulo an odd prime, the signs agree as integers. If a numerator is divisible by , both sides of the multiplicativity equation are zero. This proves the rule for all integer numerators and justifies factoring a numerator during later calculations.
A signed permutation proves Gauss's lemma
Proof
(A signed permutation of )
Replace by when , and by when . These signed representatives lie in . Their absolute values are all different: equality would give , hence . For indices between one and , the positive case forces equality, while rules out the negative case. Thus the absolute values permute .
Multiply the signed residues. On one hand the product is congruent to ; on the other it is exactly . None of the factors of is divisible by , so cancellation is legitimate. Euler's criterion gives the displayed sign formula. The proof needs a permutation of absolute values, not a claim that the positive residues themselves are precisely .
The supplementary laws
Proof
(Counting wraparounds for and )
For , the least positive residues are , all greater than . Gauss's count is , proving the first law. For , the residues are the ordinary integers , with no wraparound. Exactly
of them exceed . For congruent to modulo eight, this count has parity , respectively. The integer has the same respective parities. Gauss's lemma proves the second law, including every odd prime class. The number two is handled by this supplementary argument, not by a reciprocity formula whose hypotheses require two odd primes.
Converting signs into floor sums
Proof
(Gauss's count as a floor sum)
We need one parity identity. Let be a positive odd integer coprime to , write
and let be the absolute representatives from Gauss's lemma. Their sum is . Replacing a negative signed representative by its positive residue changes into , so
Modulo two, this is . But are odd, so summing the division equations gives . Comparing the two expressions proves . Hence
Oddness of was used in this parity argument. Applying the floor formula to an arbitrary even numerator without its hypothesis would lose exactly the sign information just tracked.
The explorer below counts the residues of above for any odd prime and numerator , compares Gauss's sign with Euler's criterion and a brute-force list of squares, and shows where the floor formula fails for even .
Counterexample mode
The floor-sum formula needs an odd numerator
A tempting claim is that for every numerator coprime to . Take and , so . Then , which predicts . But the nonzero squares modulo are and , so . Gauss's count itself is correct: the residues contain one value above , so . The parity step used that is odd, and it fails here. For use the supplementary count instead.
A rectangle completes reciprocity
Proof
(Counting lattice points in the rectangle)
Let and . Consider the integer points with and . None lies on the line : otherwise primality and distinctness of would force , impossible in this range.
For each fixed , the number of points with is . This number is at most because , and equality with an integer boundary never occurs. Similarly, for each fixed , the number with is . These two disjoint sets partition the rectangle, giving
Apply the floor-sign identity first to numerator and then to numerator . Multiplying the resulting signs gives , exactly quadratic reciprocity. Every lattice point has been counted once, and the absence of boundary points is where the distinct-prime hypothesis enters. The two sides of the line need not contain equal numbers of points. Reciprocity uses the parity of their sum, not equality of the two counts; this is why an odd-area rectangle produces opposite symbols.
Proof X-ray
Why a geometric count determines an arithmetic sign
The chain has three bridges, and each uses a different hypothesis. Gauss's lemma turns the symbol into the parity of , the number of negative signed representatives; it needs only that is odd, so that is an integer and . The floor-sum identity then needs an odd numerator, because it compares with modulo . Reciprocity applies it twice, with numerators and , which is why both primes must be odd.
The key move is the rectangle. Each floor sum counts the lattice points on one side of the line , and distinctness of the primes guarantees that no point lies on the line, so the two counts add up to exactly . The two sides need not contain equal numbers of points: for , there is one point on each side, and for , the counts are and . Only the parity of the total matters, and the exceptional sign is , the parity of the rectangle's area.
Worked examples
Worked example 6.1.4
(Reducing a symbol without finding a square root)
Compute . Both primes are one modulo four, so reciprocity gives . Multiplicativity reduces the last symbol to . Since is one modulo four, reciprocity again gives . Thus thirty-seven is a nonzero square modulo one hundred and one. This calculation decides existence without constructing its roots; those are separate tasks.
Worked example 6.1.5
(A residue decision followed by an actual root check)
For , reciprocity has positive sign, and . A root is thirteen because ; its negative is twenty-eight. They are distinct and are the only roots, since a degree-two polynomial over the field has at most two. The symbol proved existence, the substitution found a witness, and the root bound proved completeness.
Worked example 6.1.6
(A composite symbol cannot replace the prime theorem)
For a positive odd integer , define the Jacobi symbol by , with the empty product at equal to one. Then . Nevertheless two is not a square modulo fifteen, because reducing any proposed square root modulo three would give a square equal to two there, impossible. Also , so replacing by fifteen in Euler's criterion fails. A Jacobi sign is a product of local signs, not a complete composite-modulus square test.
A reliable calculation routine
First check whether the numerator vanishes modulo the prime; that case gives symbol zero. Otherwise reduce it to a convenient representative and factor out signs, factors of two, or repeated square factors using the proved identities. Apply reciprocity to odd prime factors, recording the minus sign before reducing the new numerator. The successive smaller moduli organize the computation, but factoring a large numerator is not declared free.
At the end, ask what the symbol actually establishes. A positive Legendre symbol gives two roots for a nonzero target, not a formula for those roots. A negative symbol excludes roots. A positive Jacobi symbol may leave incompatible local signs, as the example shows. Separating the decision, construction, and completeness questions keeps an efficient symbolic calculation from claiming more than it proves.
Lifting a nonzero square root to odd prime powers
There is a useful controlled extension beyond fields. Fix an odd prime , assume , and suppose for . Every lift of this residue to modulus has the form with taken modulo . Write . Expanding the square shows that a lift is a root exactly when
The remaining term vanishes modulo because . Since is odd and is nonzero modulo , the coefficient is invertible. There is exactly one value of . Each nonzero root therefore lifts uniquely through every higher power of this prime. Every root at the higher modulus reduces to one at the lower modulus, so this construction gives both existence and completeness, not just candidate roots.
For example, the root thirteen of five modulo forty-one has . The next equation is , solved by . Thus is a root modulo : indeed . Its negative supplies the other lifted root. This computation constructs a root once a prime-level root is known; reciprocity alone did not find that initial root.
Finally let a positive odd composite modulus have distinct prime-power factors, and assume the target is coprime to it. Each prime factor gives either no root or two roots at every power, according to its Legendre symbol. The Chinese remainder theorem combines the choices independently. Hence there are no roots if any local symbol is negative, and otherwise exactly roots, where is the number of distinct prime divisors. This conclusion does not cover nonunit targets or powers of two; in those cases the invertibility used in the lifting equation can fail. It also explains precisely why a positive Jacobi product is weaker than checking every local sign separately.
Common mistakes
Common mistake
(Dropping the sign when both primes are modulo )
For both primes are , so reciprocity gives . Dropping the sign gives , which is wrong: the nonzero squares modulo are , and is not among them.
Common mistake
(Applying reciprocity to a composite or even numerator)
The law relates two distinct odd primes. A symbol such as cannot be inverted to “”, which is not a Legendre symbol. Factor first: , using the second supplementary law for and reciprocity only for . As a check, and give .
Euler's criterion is a congruence whose right side is the integer sign zero, one, or minus one. Gauss's lemma is an equality of signs. Their connection uses the fact that one and minus one remain distinct modulo an odd prime. Composite rings can have extra roots of a polynomial and nonunit factors, which is why the field hypotheses in both proofs matter.
Summary
Euler's criterion encodes squareness as a sign. Gauss's lemma obtains it from a signed residue permutation, the supplementary laws handle minus one and two, and a rectangle of lattice points supplies the reciprocity sign. The completed proof decides many prime-modulus square questions while retaining clear limits on root finding and composite-modulus conclusions.
Exercises
Quick check
(Compute and , giving the applicable supplementary rules.)
Solution · Answer
Since , . Since , . Both are applications of the proved supplementary laws, not uses of reciprocity with an even prime.
Quick check
(Compute and . When the latter is positive, find and verify both roots of .)
Solution · Answer
Both and are , so . For the other pair, . The roots are and : their squares and are both . They are negatives, and the field root bound excludes any further roots.
Quick check
(Use Gauss's lemma directly to compute , listing the signed representatives and the negative count.)
Solution · Answer
The positive residues of modulo are , and their signed representatives are . Exactly one is negative, so the symbol is . The absolute values display the required permutation explicitly.
Quick check
(Prove that if and is a square modulo a positive odd , then its Jacobi symbol is one. Explain why the converse fails.)
Solution · Answer
Reducing a square modulo each prime divisor of gives a nonzero square because is coprime to . Every Legendre factor is therefore , and their powers multiply to . The example disproves the converse: two negative local signs multiply to a positive Jacobi sign even though neither local square equation is solvable.