Turn square existence into a signed count

Try

For p=7 and a=3, the first half-multiples are 3, 6, 9, reducing to 3, 6, 2. Replace the residue six by −1, so the signed small representatives are 3,−1, 2. Their magnitudes are exactly 1, 2, 3. One sign was negative, predicting that three is a nonsquare modulo seven. This is Gauss’s lemma in a concrete form.

Predict

Predict why the magnitudes cannot collide. If ai≡±aj modulo p, cancellation gives i≡±j. With 1≤i, j≤(p−1)/2, equality is the only possibility: i+j cannot reach p. This injectivity turns the small representatives into a permutation, allowing their product to be cancelled. Without the half-range restriction, the argument would count duplicates.

Experiment

Inspect the signed reduction.

j	aj modulo 7	Representative between −3 and 3
1	3	3
2	6	−1
3	2	2

The product identity gives 3³·3!≡−3! modulo seven. Cancel 3! and obtain 3³≡−1. Verify the power directly, then compare with the square classes 1, 2, 4.

Understand

Euler’s criterion states a^((p−1)/2)≡(a/p) modulo an odd prime p. For a nonzero square a=b², Fermat gives the power one. There are exactly m=(p−1)/2 such classes, and X^m−1 has at most m roots over the field, so nonsquares cannot also give one. Fermat says their mth power squares to one, leaving minus one. For p|a both sides are zero. This supplies the necessary converse: merely showing squares give one would not suffice to identify every nonsquare.

Apply

For p∤a, take the least positive residues of a, 2a,…, ma and let N count those exceeding p/2. Negating those residues gives a permutation of 1,…, m up to sign, as the collision argument proves. Comparing products yields a^m m!≡(−1)^N m!, so Gauss’s lemma follows after cancellation and Euler’s criterion. For a=−1 every term changes sign, giving (−1/p)=(−1)^m. For a=2, the count is m−⌊p/4⌋. Checking p≡1, 3, 5, 7 modulo eight gives signs +,−,−,+, equivalently (2/p)=(−1)^((p²−1)/8).

The absolute-residue permutation used in Gauss’s lemma has a short collision proof. If ai and aj reduce to the same absolute representative, then ai is congruent to either aj or −aj. Since a is invertible modulo p, this gives i=j or i+j=p. For indices between one and (p−1)/2 the second possibility is impossible, because their sum is at most p−1. Thus all representatives are distinct and fill the half-range. This is the precise reason the product can be replaced by the half-factorial; omitting injectivity would leave a gap in the sign computation.

Continue

These supplementary laws handle the factors minus one and two in larger residue calculations. They also expose why residue conditions depend on small modulus classes. The next lesson uses Gauss’s count to compare (p/q) with (q/p). Keep the denominator prime and odd throughout these statements. A symbol for a composite denominator needs a separate definition and does not preserve every square-existence interpretation.

Return to the number theory unit to choose a targeted retry. Continue with prove the sign that appears when primes are exchanged.