Quadratic Residues and the Law of Reciprocity
Decide which residues are squares modulo a prime, compute the Legendre symbol, and use reciprocity to answer the question quickly.
What a learner can do afterwards
- List the quadratic residues modulo a small prime and count them
- Apply Euler's criterion to test whether a residue is a square
- Use quadratic reciprocity and the supplementary laws to evaluate a Legendre symbol
1 · Read
Quadratic residues ask which remainders occur as squares modulo a prime. For an odd prime p, exactly half of the nonzero remainders are squares, a total of p minus 1 over 2. Modulo 5 the squares are 1 and 4. Modulo 7 they are 1, 2, and 4, since 3 squared is 9 and leaves 2. Pairs a and p minus a always share a square, which is why the list stops at half.
Euler criterion reads squareness from one power. Raise your number to half of p minus 1. Remainder 1 means it is a square, remainder minus 1 means it is not. Modulo 7 the power is 3: 2 cubed is 8 and leaves 1, so 2 is a square. One computation replaces a whole search.
Reciprocity and its helper laws answer big primes quickly. The helper law for 2 says it is a square exactly when p sits 1 above or 1 below a multiple of 8. Seven sits 1 below 8, so 2 is a square mod 7 with no powering needed. The main flip law swaps a large Legendre question into smaller ones you can finish by hand.
List small, power midsize, flip large. Test tiny moduli by squaring bases directly. Use Euler when the power is cheap. Call on reciprocity once the prime grows. Never mistake remainder 1 from random powering for the criterion: only the half power counts.
Half the remainders are squares, Euler tests them by powering, and reciprocity shrinks big cases.
2 · Watch
Take it off screen
Where it sits
Learn first
This opens up
8 questions wait behind this lesson, each with its answer explained. Every answer feeds the sky: stars light as they are learned, and dim when it is time to come back.