Definition:Quadratic Residue

From ProofWiki
Jump to navigation Jump to search

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


Warning

The definition of the quadratic residue must be qualified as follows:

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.


Also see

  • Results about quadratic residues can be found here.


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Definition:Quadratic_Residue&oldid=716286"