# 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}$

This sequence is A010375 in the On-Line Encyclopedia of Integer Sequences (N. J. A. Sloane (Ed.), 2008).

### Quadratic Residues Modulo $17$

The set of quadratic residues modulo $17$ is:

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

This sequence is A010379 in the On-Line Encyclopedia of Integer Sequences (N. J. A. Sloane (Ed.), 2008).

### 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}$

This sequence is A010391 in the On-Line Encyclopedia of Integer Sequences (N. J. A. Sloane (Ed.), 2008).

### 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}$

This sequence is A010422 in the On-Line Encyclopedia of Integer Sequences (N. J. A. Sloane (Ed.), 2008).

## Also see

- 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$ - 2008: Ian Stewart:
*Taming the Infinite*... (previous) ... (next): Chapter $7$: Patterns in Numbers