Number TheoryDifficulty 55-10090 tagged problems

Quadratic Residues

Quadratic Residues is the habit of classifying which residues can occur as squares modulo an integer or prime. In contest math, that habit turns a crowded setup into a relation the student can test, bound, count, or compute. MathGrit teaches it as a recognizable signal, a deliberate move, and a final translation back to the original question.

Practice this technique Match my level

The Key Result

$$\text{For odd prime } p,\ \text{exactly } \frac{p-1}{2} \text{ nonzero residues are squares, and } a^{\frac{p-1}{2}} \equiv \pm 1 \pmod{p}$$

Modulo an odd prime, only half the nonzero residues are perfect squares (quadratic residues), and Euler's criterion tells you which by raising to the power $(p-1)/2$.

Why It Works

1
By Fermat, $a^{p-1} \equiv 1$, so $\left(a^{(p-1)/2} - 1\right)\left(a^{(p-1)/2} + 1\right) \equiv 0 \pmod p$, forcing $a^{(p-1)/2} \equiv \pm 1$.
2
If $a \equiv b^2$ is a square, then $a^{(p-1)/2} \equiv b^{p-1} \equiv 1 \pmod p$ (Euler's criterion).
3
The map $x \mapsto x^2$ on nonzero residues is two-to-one (since $x$ and $-x$ share a square and $x \not\equiv -x$ for odd $p$), so its image has $\frac{p-1}{2}$ elements.
4
Those $\frac{p-1}{2}$ values are exactly the quadratic residues; the rest are non-residues with $a^{(p-1)/2} \equiv -1$.

Worked Examples

Example 1

Is $3$ a quadratic residue modulo $7$? List all quadratic residues mod $7$.

1
Square the residues $1$ through $6$ mod $7$: $1^2=1$, $2^2=4$, $3^2 = 9 \equiv 2$, $4^2 = 16 \equiv 2$, $5^2 = 25 \equiv 4$, $6^2 = 36 \equiv 1$.
2
The distinct squares are $\{1, 2, 4\}$ — exactly $\frac{7-1}{2} = 3$ of them.
3
$3$ is not in $\{1, 2, 4\}$, so it is a non-residue.
4
Check with Euler's criterion: $3^{(7-1)/2} = 3^3 = 27 \equiv 6 \equiv -1 \pmod 7$, confirming $3$ is a non-residue.

Answer:

$3$ is a non-residue; the quadratic residues mod $7$ are $\{1, 2, 4\}$.

Warm-up

Use Euler's criterion to decide whether $2$ is a quadratic residue modulo $7$.

1
Euler's criterion: $\left(\frac{2}{7}\right) \equiv 2^{(7-1)/2} = 2^3 \pmod 7$.
2
Compute $2^3 = 8 \equiv 1 \pmod 7$.
3
A result of $+1$ means $2$ is a quadratic residue mod $7$.
4
Confirm directly: $3^2 = 9 \equiv 2 \pmod 7$, so $x \equiv \pm 3$ solve $x^2 \equiv 2 \pmod 7$.

Answer:

$2$ is a quadratic residue mod $7$ ($x \equiv \pm 3$).

Contest level

Determine whether $10$ is a quadratic residue modulo $13$, using the Legendre symbol's multiplicativity and quadratic reciprocity.

1
Factor inside the symbol: $\left(\frac{10}{13}\right) = \left(\frac{2}{13}\right)\left(\frac{5}{13}\right)$.
2
$\left(\frac{2}{13}\right)$: the supplement says $2$ is a QR mod $p$ iff $p \equiv \pm 1 \pmod 8$. Since $13 \equiv 5 \pmod 8$, $\left(\frac{2}{13}\right) = -1$.
3
$\left(\frac{5}{13}\right)$: since $5 \equiv 1 \pmod 4$, reciprocity gives $\left(\frac{5}{13}\right) = \left(\frac{13}{5}\right) = \left(\frac{3}{5}\right)$. The QRs mod $5$ are $\{1, 4\}$, and $3 \notin \{1,4\}$, so $\left(\frac{5}{13}\right) = -1$.
4
Multiply: $\left(\frac{10}{13}\right) = (-1)(-1) = +1$, so $10$ is a QR mod $13$. Indeed $6^2 = 36 \equiv 10 \pmod{13}$, so $x \equiv \pm 6$.

Answer:

$10$ is a quadratic residue mod $13$ ($x \equiv \pm 6$).

Olympiad / Challenge

Prove that there are infinitely many primes congruent to $1 \pmod 4$.

1
Suppose, for contradiction, only finitely many such primes $p_1, \dots, p_k$ exist. Let $N = (2 p_1 p_2 \cdots p_k)^2 + 1$, which is odd and $> 1$, so it has some odd prime factor $q$.
2
Then $q \mid N$ means $(2 p_1 \cdots p_k)^2 \equiv -1 \pmod q$, so $-1$ is a quadratic residue modulo $q$.
3
But $-1$ is a QR mod an odd prime $q$ iff $q \equiv 1 \pmod 4$ (by Euler's criterion, $(-1)^{(q-1)/2} = 1 \iff \tfrac{q-1}{2}$ even). Hence $q \equiv 1 \pmod 4$.
4
Yet $q$ cannot be any $p_i$: each $p_i \mid (2p_1\cdots p_k)^2$, so $p_i \mid N$ would force $p_i \mid 1$. So $q$ is a prime $\equiv 1 \pmod 4$ outside the list — contradiction. Therefore infinitely many primes are $\equiv 1 \pmod 4$.

Answer:

Infinitely many primes are $\equiv 1 \pmod 4$ (via $-1$ being a QR only mod such primes).

Going Deeper

Generalization: the Legendre symbol $\left(\frac{a}{p}\right)$ is completely multiplicative in $a$, and the law of quadratic reciprocity, $\left(\frac{p}{q}\right)\left(\frac{q}{p}\right) = (-1)^{\frac{p-1}{2}\cdot\frac{q-1}{2}}$, together with the supplements $\left(\frac{-1}{p}\right) = (-1)^{(p-1)/2}$ and $\left(\frac{2}{p}\right) = (-1)^{(p^2-1)/8}$, lets you evaluate any symbol fast. The Jacobi symbol extends this to composite moduli for computation.
Where it appears: deciding solvability of $x^2 \equiv a \pmod p$, determining which primes a quadratic form represents, proving primes lie in fixed residue classes (e.g. infinitely many primes $\equiv 1 \pmod 4$), and analyzing when $-1$, $2$, or $-3$ is a square mod $p$.
Pitfall: $\left(\frac{a}{p}\right) = 1$ tells you a square root EXISTS but not its value, and the criterion is for ODD primes $p$ with $p \nmid a$ (handle $p = 2$ and $p \mid a$ separately, where $a \equiv 0$). Also $\left(\frac{a}{p}\right)\left(\frac{b}{p}\right) = \left(\frac{ab}{p}\right)$ means a product of two NON-residues is a RESIDUE — non-residues do not 'stay' non-residues under multiplication.

Spot the Signal

Look for problems where the key step is classifying which residues can occur as squares modulo an integer or prime.
You can describe the hard part as classifying which residues can occur as squares modulo an integer or prime, but a direct attack starts producing clutter.
The problem rewards preserving structure instead of expanding, listing, or guessing too early.

Learn the Move

Start by identify the integer constraint that calls for quadratic residues, then rewrite the givens around it.
Name the relation that makes Quadratic Residues legal before doing computation.
Use the new relation to replace the messiest part of the problem with a cleaner one.
Translate the result back to the quantity the problem actually asks for.

Avoid These Traps

Do not use Quadratic Residues just because the surface looks familiar; verify the required condition first.
Applying Quadratic Residues because it sounds relevant, without checking the trigger first.
Stopping after spotting the technique instead of finishing the calculation or proof.

MathGrit Coach Note

Let quadratic residues reveal the integer structure; then compute only what remains.

Try it on:

Practice a contest problem where the key step is classifying which residues can occur as squares modulo an integer or prime.

Back to techniques

Number TheoryDifficulty 55-10090 tagged problems

Quadratic Residues

Practice this technique Match my level

The Key Result

$$\text{For odd prime } p,\ \text{exactly } \frac{p-1}{2} \text{ nonzero residues are squares, and } a^{\frac{p-1}{2}} \equiv \pm 1 \pmod{p}$$

Modulo an odd prime, only half the nonzero residues are perfect squares (quadratic residues), and Euler's criterion tells you which by raising to the power $(p-1)/2$.

Why It Works

1
By Fermat, $a^{p-1} \equiv 1$, so $\left(a^{(p-1)/2} - 1\right)\left(a^{(p-1)/2} + 1\right) \equiv 0 \pmod p$, forcing $a^{(p-1)/2} \equiv \pm 1$.
2
If $a \equiv b^2$ is a square, then $a^{(p-1)/2} \equiv b^{p-1} \equiv 1 \pmod p$ (Euler's criterion).
3
The map $x \mapsto x^2$ on nonzero residues is two-to-one (since $x$ and $-x$ share a square and $x \not\equiv -x$ for odd $p$), so its image has $\frac{p-1}{2}$ elements.
4
Those $\frac{p-1}{2}$ values are exactly the quadratic residues; the rest are non-residues with $a^{(p-1)/2} \equiv -1$.

Worked Examples

Example 1

Is $3$ a quadratic residue modulo $7$? List all quadratic residues mod $7$.

1
Square the residues $1$ through $6$ mod $7$: $1^2=1$, $2^2=4$, $3^2 = 9 \equiv 2$, $4^2 = 16 \equiv 2$, $5^2 = 25 \equiv 4$, $6^2 = 36 \equiv 1$.
2
The distinct squares are $\{1, 2, 4\}$ — exactly $\frac{7-1}{2} = 3$ of them.
3
$3$ is not in $\{1, 2, 4\}$, so it is a non-residue.
4
Check with Euler's criterion: $3^{(7-1)/2} = 3^3 = 27 \equiv 6 \equiv -1 \pmod 7$, confirming $3$ is a non-residue.

Answer:

$3$ is a non-residue; the quadratic residues mod $7$ are $\{1, 2, 4\}$.

Warm-up

Use Euler's criterion to decide whether $2$ is a quadratic residue modulo $7$.

1
Euler's criterion: $\left(\frac{2}{7}\right) \equiv 2^{(7-1)/2} = 2^3 \pmod 7$.
2
Compute $2^3 = 8 \equiv 1 \pmod 7$.
3
A result of $+1$ means $2$ is a quadratic residue mod $7$.
4
Confirm directly: $3^2 = 9 \equiv 2 \pmod 7$, so $x \equiv \pm 3$ solve $x^2 \equiv 2 \pmod 7$.

Answer:

$2$ is a quadratic residue mod $7$ ($x \equiv \pm 3$).

Contest level

Determine whether $10$ is a quadratic residue modulo $13$, using the Legendre symbol's multiplicativity and quadratic reciprocity.

1
Factor inside the symbol: $\left(\frac{10}{13}\right) = \left(\frac{2}{13}\right)\left(\frac{5}{13}\right)$.
2
$\left(\frac{2}{13}\right)$: the supplement says $2$ is a QR mod $p$ iff $p \equiv \pm 1 \pmod 8$. Since $13 \equiv 5 \pmod 8$, $\left(\frac{2}{13}\right) = -1$.
3
$\left(\frac{5}{13}\right)$: since $5 \equiv 1 \pmod 4$, reciprocity gives $\left(\frac{5}{13}\right) = \left(\frac{13}{5}\right) = \left(\frac{3}{5}\right)$. The QRs mod $5$ are $\{1, 4\}$, and $3 \notin \{1,4\}$, so $\left(\frac{5}{13}\right) = -1$.
4
Multiply: $\left(\frac{10}{13}\right) = (-1)(-1) = +1$, so $10$ is a QR mod $13$. Indeed $6^2 = 36 \equiv 10 \pmod{13}$, so $x \equiv \pm 6$.

Answer:

$10$ is a quadratic residue mod $13$ ($x \equiv \pm 6$).

Olympiad / Challenge

Prove that there are infinitely many primes congruent to $1 \pmod 4$.

1
Suppose, for contradiction, only finitely many such primes $p_1, \dots, p_k$ exist. Let $N = (2 p_1 p_2 \cdots p_k)^2 + 1$, which is odd and $> 1$, so it has some odd prime factor $q$.
2
Then $q \mid N$ means $(2 p_1 \cdots p_k)^2 \equiv -1 \pmod q$, so $-1$ is a quadratic residue modulo $q$.
3
But $-1$ is a QR mod an odd prime $q$ iff $q \equiv 1 \pmod 4$ (by Euler's criterion, $(-1)^{(q-1)/2} = 1 \iff \tfrac{q-1}{2}$ even). Hence $q \equiv 1 \pmod 4$.
4
Yet $q$ cannot be any $p_i$: each $p_i \mid (2p_1\cdots p_k)^2$, so $p_i \mid N$ would force $p_i \mid 1$. So $q$ is a prime $\equiv 1 \pmod 4$ outside the list — contradiction. Therefore infinitely many primes are $\equiv 1 \pmod 4$.

Answer:

Infinitely many primes are $\equiv 1 \pmod 4$ (via $-1$ being a QR only mod such primes).

Going Deeper

Generalization: the Legendre symbol $\left(\frac{a}{p}\right)$ is completely multiplicative in $a$, and the law of quadratic reciprocity, $\left(\frac{p}{q}\right)\left(\frac{q}{p}\right) = (-1)^{\frac{p-1}{2}\cdot\frac{q-1}{2}}$, together with the supplements $\left(\frac{-1}{p}\right) = (-1)^{(p-1)/2}$ and $\left(\frac{2}{p}\right) = (-1)^{(p^2-1)/8}$, lets you evaluate any symbol fast. The Jacobi symbol extends this to composite moduli for computation.
Where it appears: deciding solvability of $x^2 \equiv a \pmod p$, determining which primes a quadratic form represents, proving primes lie in fixed residue classes (e.g. infinitely many primes $\equiv 1 \pmod 4$), and analyzing when $-1$, $2$, or $-3$ is a square mod $p$.
Pitfall: $\left(\frac{a}{p}\right) = 1$ tells you a square root EXISTS but not its value, and the criterion is for ODD primes $p$ with $p \nmid a$ (handle $p = 2$ and $p \mid a$ separately, where $a \equiv 0$). Also $\left(\frac{a}{p}\right)\left(\frac{b}{p}\right) = \left(\frac{ab}{p}\right)$ means a product of two NON-residues is a RESIDUE — non-residues do not 'stay' non-residues under multiplication.

Spot the Signal

Look for problems where the key step is classifying which residues can occur as squares modulo an integer or prime.
You can describe the hard part as classifying which residues can occur as squares modulo an integer or prime, but a direct attack starts producing clutter.
The problem rewards preserving structure instead of expanding, listing, or guessing too early.

Learn the Move

Start by identify the integer constraint that calls for quadratic residues, then rewrite the givens around it.
Name the relation that makes Quadratic Residues legal before doing computation.
Use the new relation to replace the messiest part of the problem with a cleaner one.
Translate the result back to the quantity the problem actually asks for.

Avoid These Traps

Do not use Quadratic Residues just because the surface looks familiar; verify the required condition first.
Applying Quadratic Residues because it sounds relevant, without checking the trigger first.
Stopping after spotting the technique instead of finishing the calculation or proof.

MathGrit Coach Note

Let quadratic residues reveal the integer structure; then compute only what remains.

Try it on:

Practice a contest problem where the key step is classifying which residues can occur as squares modulo an integer or prime.