Definition:Quadratic Residue

Definition

Let $p$ be an odd prime.

Let $a \in \Z$ be an integer such that $a \not \equiv 0 \pmod p$.

Then $a$ is a quadratic residue of $p$ if and only if $x^2 \equiv a \pmod p$ has a solution.

That is, if and only if:

$\exists x \in \Z: x^2 \equiv a \pmod p$

Quadratic Non-Residue

If there is no such integer $x$ such that $x^2 \equiv a \pmod p$, then $a$ is a quadratic non-residue of $p$.

Quadratic Character

$a$ is either a quadratic residue or a quadratic non-residue of $p$.

Whether it is or not is known as the quadratic character of $a$ modulo $p$.

Examples

Quadratic Residues Modulo $3$

There exists exactly $1$ quadratic residue modulo $3$, and that is $1$.

Quadratic Residues Modulo $5$

The set of quadratic residues modulo $5$ is:

$\set {1, 4}$

Quadratic Residues Modulo $7$

The set of quadratic residues modulo $7$ is:

$\set {1, 2, 4}$

Quadratic Residues Modulo $11$

The set of quadratic residues modulo $11$ is:

$\set {1, 3, 4, 5, 9}$

Quadratic Residues Modulo $17$

The set of quadratic residues modulo $17$ is:

$\set {1, 2, 4, 8, 9, 13, 15, 16}$

Quadratic Residues Modulo $29$

The set of quadratic residues modulo $29$ is:

$\set {1, 4, 5, 6, 7, 9, 13, 16, 20, 22, 23, 24, 25, 28}$

Quadratic Residues Modulo $61$

The set of quadratic residues modulo $61$ is:

$\set {1, 3, 4, 5, 9, 12, 13, 14, 15, 16, 19, 20, 22, 25, 27, 34, 36, 39, 41, 42, 45, 46, 47, 48, 49, 53, 56, 57, 58, 60}$

Also see

• Definition:Legendre Symbol.

• Number of Quadratic Residues of Prime

• Congruent Integers are of same Quadratic Character

• Results about quadratic residues can be found here.

Note

The case where $a = 0$ has been excluded from the definition, despite the fact that $0 = 0^2$ and so is definitely a square.

The case where $p = 2$ is also excluded, where the only non-zero residue $1$ is also a square.

The main reason for this is so that some useful results can be expressed in a convenient form.

For example, this means that from Number of Quadratic Residues of Prime the number of quadratic residues of $p$ is always equal to $\dfrac {p - 1} 2$, which is the same as the number of quadratic non-residues.

Sources

• 1971: George E. Andrews: Number Theory ... (previous) ... (next): $\text {3-5}$ The Use of Computers in Number Theory: Exercise $6$
• 1989: Ephraim J. Borowski and Jonathan M. Borwein: Dictionary of Mathematics ... (previous) ... (next): quadratic residue
• 1998: David Nelson: The Penguin Dictionary of Mathematics (2nd ed.) ... (previous) ... (next): quadratic residue
• 2008: David Nelson: The Penguin Dictionary of Mathematics (4th ed.) ... (previous) ... (next): quadratic residue
• 2008: Ian Stewart: Taming the Infinite ... (previous) ... (next): Chapter $7$: Patterns in Numbers: Gauss