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
For an odd prime p, a nonzero quadratic residue is a nonzero remainder a with x^2 congruent to a for some x. Roots pair as x and p - x. There are no other roots: p dividing (x - y)(x + y) forces y congruent to x or -x. Thus there are (p - 1)/2 nonzero squares. Square bases 1 through (p - 1)/2 to list them. Zero is also a square, but is excluded from this count. For a primitive root g, the even powers give exactly the nonzero squares.
For an odd prime p, the Legendre symbol (a/p) is 0 if p divides a, 1 if a is a nonzero square modulo p, and -1 otherwise. This notation is a symbol, not a fraction. Reduce the numerator modulo p first. The symbol is multiplicative: (ab/p) = (a/p)(b/p). A square factor not divisible by p contributes 1. A factor divisible by p makes the product symbol zero.
Euler's criterion says that, for an odd prime p not dividing a, a^((p - 1)/2) is congruent to (a/p) modulo p. Remainder 1 means a square; remainder p - 1 represents -1 and means a nonsquare. Compute by squaring and multiplying remainders. If p divides a, the positive half power gives 0. The full power a^(p - 1) gives 1 for every nonzero remainder, so it cannot distinguish squares.
Primitive roots explain the two nonzero outcomes. Let g be primitive modulo p. The power g^((p - 1)/2) squares to 1 but is not 1, so it is -1 modulo p. Write a = g^r modulo p. Then a^((p - 1)/2) is congruent to (-1)^r. Even exponent indices give squares and outcome 1; odd indices give nonsquares and outcome -1.
Two supplementary laws handle -1 and 2. For an odd prime p, (-1/p) is 1 when p leaves remainder 1 modulo 4, and -1 when it leaves 3. Also, (2/p) is 1 when p leaves 1 or 7 modulo 8, and -1 when it leaves 3 or 5. These laws test squareness without listing roots or computing Euler's power.
Quadratic reciprocity applies to distinct odd primes p and q. The symbols (p/q) and (q/p) have opposite signs if both primes leave remainder 3 modulo 4; otherwise they are equal. Reduce the numerator after a swap. Factor a composite numerator and use multiplicativity. Use the supplementary laws for factors -1 and 2. Check divisibility before swapping.
Evaluate (5/17). Since 5 leaves remainder 1 modulo 4, reciprocity keeps the sign: (5/17) = (17/5). Reduce 17 modulo 5 to obtain (2/5). The law for 2 gives -1 because 5 leaves remainder 5 modulo 8. Therefore 5 is a nonsquare modulo 17.
For an odd prime, half the nonzero remainders are squares. Use Euler's criterion, the supplementary laws and signed reciprocity to evaluate Legendre symbols.
The lesson, questions, worked solutions and base flashcards were written for this dataset.
The readings and extra questions were written for this dataset. The flashcards retain imported facts-collection material with corrections; their source terms have not been verified.
More to read
Why square roots form pairs
Work modulo an odd prime p. Opposite bases x and p - x have equal squares. If x^2 and y^2 agree, then p divides (x - y)(x + y). Since p is prime, one factor is divisible by p, so y agrees with x or -x. For a nonzero square these roots are distinct. The p - 1 nonzero bases therefore form (p - 1)/2 pairs, one pair for each nonzero square. Zero contributes one further square remainder.
Choose Euler's half exponent
For an odd prime p not dividing a, Euler's criterion uses exponent (p - 1)/2. Remainder 1 identifies a square, while remainder p - 1 identifies a nonsquare. Modulo 5, 2^2 gives 4, representing -1, so 2 is a nonsquare. Squaring again gives 1. That full exponent p - 1 would give 1 for squares as well, losing the distinction. When p divides the base, every positive power instead gives remainder zero.
Track the sign when swapping primes
To evaluate (5/23), first check that 5 and 23 are distinct odd primes. Because 5 is 1 modulo 4, reciprocity permits the swap without a sign change. Reduce (23/5) to (3/5). The nonzero squares modulo 5 are 1 and 4, so (3/5) = -1. When both primes are 3 modulo 4, a swap instead introduces a minus sign. For a composite numerator, factor it and multiply its factor symbols; do not apply the prime-swap rule to it directly.
2 · Watch
En anglaisTake it off screen
Where it sits
Learn first
This opens up
17 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.