gen-briefly-explain-quadratic-residues-and-one-common-misconcept-f7c0

Briefly explain quadratic residues and one common misconception about it.

# Quadratic Residues **Definition:** A number *a* is a quadratic residue modulo *n* if there exists an integer *x* such that x² ≡ a (mod n). In other words, *a* is a quadratic residue if it's a perfect square in modular arithmetic. **Example:** Modulo 7, the quadratic residues are {1, 2, 4}: - 1² ≡ 1 (mod 7) - 2² ≡ 4 (mod 7) - 3² ≡ 2 (mod 7) ## Common Misconception **Misconception:** "If *a* is a quadratic residue mod *n*, then there's only one value of *x* that satisfies x² ≡ a (mod n)." **Reality:** There are typically *multiple* solutions. For prime moduli *p*, if *a* is a quadratic residue, there are exactly **two** solutions (except when *a* ≡ 0). For example, mod 7: both 3² ≡ 2 and 4² ≡ 2, since 4 ≡ -3 (mod 7). More generally, if *x* is a solution, so is -*x* (and these are distinct unless *x* ≡ 0).