gen-define-quadratic-residues-and-give-one-short-worked-example-bf94

Define quadratic residues and give one short worked example.

# Quadratic Residues ## Definition An integer **a** is a **quadratic residue modulo n** if there exists an integer x such that: $$x^2 \equiv a \pmod{n}$$ In other words, *a* is a quadratic residue mod *n* if *a* is congruent to a perfect square modulo *n*. ## Worked Example **Question:** Is 2 a quadratic residue modulo 7? **Solution:** We need to check if there exists an *x* such that $x^2 \equiv 2 \pmod{7}$. Check all squares modulo 7: - $0^2 \equiv 0 \pmod{7}$ - $1^2 \equiv 1 \pmod{7}$ - $2^2 \equiv 4 \pmod{7}$ - $3^2 \equiv 9 \equiv 2 \pmod{7}$ ✓ Since $3^2 \equiv 2 \pmod{7}$, **yes, 2 is a quadratic residue modulo 7**. --- *Note:* We only need to check up to $x = 3$ because $(7-k)^2 \equiv k^2 \pmod{7}$, so the pattern repeats.