Prove the sign that appears when primes are exchanged

Try

Ask whether five is a square modulo thirteen. Reciprocity turns the question into whether thirteen is a square modulo five, with no sign change because five is one modulo four. Since thirteen reduces to three and the nonzero squares modulo five are one and four, the answer is no. This reduces a larger-prime question to a smaller-prime calculation, but the sign rule must be proved rather than guessed.

Predict

Predict the exception to simple symmetry. For primes three and seven, three is a nonsquare modulo seven while seven is a square modulo three. Both primes are three modulo four, and their symbols have opposite signs. The theorem states (p/q)(q/p)=(−1)^(((p−1)/2)((q−1)/2)) for distinct odd primes. The product is negative exactly in that both-three-mod-four case.

Experiment

For p=3 and q=7, use the rectangle 1≤i≤1 and 1≤j≤3.

Lattice point	Compare 7i and 3j	Side of line
(1, 1)	7>3	j< 7i/3
(1, 2)	7>6	j< 7i/3
(1, 3)	7< 9	i< 3j/7

The two floor sums are two and one, totaling three. Their parity is odd, giving the negative reciprocity sign. This table is the smallest nontrivial instance of the general counting proof.

Understand

First convert Gauss’s lemma into Eisenstein’s parity formula for positive odd a coprime to p. Write ai=pqᵢ+rᵢ for i=1,…, m, m=(p−1)/2. Replace each rᵢ>p/2 by p−rᵢ; the resulting magnitudes permute 1,…, m. Modulo two, Σrᵢ≡Σi+N, because each replacement changes parity by one when p is odd. Summing ai=pqᵢ+rᵢ and using oddness of a, p gives Σqᵢ≡N modulo two. Thus (a/p)=(−1)^Σ⌊ai/p⌋. This step is why the floor-sum formula is being used only with odd numerators here.

Apply

Now take a=q and exchange p, q. In the rectangle 1≤i≤(p−1)/2, 1≤j≤(q−1)/2, no lattice point lies on qi=pj: coprimality would force p|i. The sum Σᵢ⌊qi/p⌋ counts points with pj< qi; the other sum Σⱼ⌊pj/q⌋ counts points with qi< pj. The floors stay within the opposite half-range, and there are no equality cases. Every rectangle point is counted exactly once, so the two sums add to ((p−1)/2)((q−1)/2). Multiplying their parity signs proves quadratic reciprocity. Together with the supplementary laws for minus one and two, this is a complete mechanism for reducing many Legendre-symbol calculations.

When performing repeated reciprocity reductions, keep a separate running sign. Reduce the numerator modulo the denominator, remove square factors, apply the supplementary rules for minus one and two, and swap distinct odd primes with the parity sign when needed. A numerical answer should be verified by direct squaring for a small example. This algorithmic bookkeeping is not the proof of reciprocity; the lattice partition above supplies the reason the accumulated sign is correct.

Continue

When applying the theorem, reduce numerators modulo the prime, factor them using symbol multiplicativity, and account for every reciprocity sign. A successful symbol calculation proves existence or nonexistence of a root modulo that prime, but does not automatically construct it. The next lesson combines residue tests, completing the square and CRT to solve actual congruences. Composite Jacobi symbols will be useful for computation, but a value of one there will not by itself certify a square root.

Return to the number theory unit to choose a targeted retry. Continue with turn residue tests into complete solution sets.