--- title: "Quadratic Residues and the Law of Reciprocity" description: "Decide which residues are squares modulo a prime, compute the Legendre symbol, and use reciprocity to answer the question quickly." canonical: https://lightmysky.com/learn/mathematics/quadratic-residues-and-the-law-of-reciprocity-mt_0KS9eTCY4p source: https://lightmysky.com/learn/mathematics/quadratic-residues-and-the-law-of-reciprocity-mt_0KS9eTCY4p.md retrieved: 2026-11-12 --- > **Agent view.** This is the Markdown twin of the page, for tools and assistants. > When to use this site, and the call that answers each job: https://lightmysky.com/agent-instructions.md > API description (OpenAPI 3.1): https://lightmysky.com/openapi.json · Authentication: https://lightmysky.com/auth.md > Pricing: https://lightmysky.com/pricing.md · Catalog: https://lightmysky.com/llms.txt · Full catalog: https://lightmysky.com/llms-full.txt > Every machine-readable file on this domain: https://lightmysky.com/.well-known/ai-catalog.json > Ask for Markdown with `Accept: text/markdown`, a `.md` address, or `?mode=agent`. # 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. Subject: Mathematics · Area: Number Theory · Ages 21 to 22 Page: https://lightmysky.com/learn/mathematics/quadratic-residues-and-the-law-of-reciprocity-mt_0KS9eTCY4p ## Ready when they can - 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 ## Lesson: Which remainders are squares 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. *(drawing: Modulo 17, these eight bases give all eight nonzero squares. Their opposite bases repeat the same results.)* 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. *(drawing: Euler's exponent is (13 - 1)/2 = 6. Remainder 1 shows that 3 is a square modulo 13.)* 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. **Example.** 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. **Recap.** 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.* ## Practice 17 questions on this page, each with its working shown. ## Needs first - [Primitive Roots and the Units Modulo n](https://lightmysky.com/learn/mathematics/primitive-roots-and-the-units-modulo-n-mt_KwTDckkMze) ## Opens up - [The Distribution of Primes and What Is Still Open](https://lightmysky.com/learn/mathematics/the-distribution-of-primes-and-what-is-still-open-mt_PJwm9kuQWQ)