State/Eulers criterion

From SlugmathWiki

Proposition
Proof
Metadata

Proposition: (Euler Criterion) Suppose that $a$ is an integer and $p$ is an odd prime number. Then,

$\bar a^{(p-1)/2} = \bar 1$, mod $p$, if and only if $\bar a$ is a nonzero quadratic residue, mod $p$.
$\bar a^{(p-1)/2} = \overline{-1}$, mod $p$, if and only if $\bar a$ is nonzero, and not a quadratic residue, mod $p$.
$\bar a^{(p-1)/2} = \bar 0$, mod $p$, if and only if $\bar a = \bar 0$, i.e., $a$ is a multiple of $p$.

Logical Connections

This statement logically relies on the following definitions and statements: Def/Quadratic residue, Def/Residue, State/Root counting over a field, State/Multiplicative inverses exist mod p, State/No nonzero nilpotents in a field, State/Half of nonzero residues are quadratic residues, State/Fermats little theorem

The following statements and definitions rely on the material of this page: Def/Legendre symbol

To visualize the logical connections between this statements and other items of mathematical knowledge, you can visit the following cluster(s), and click the "Visualize" tab: Clust/Theory of quadratic residues

Let $a$ be an integer, and $p$ an odd prime number.

Let $\FF_p$ denote the set of residues, mod $p$. Partition the set $\FF_p$ into three subsets, denoted $R_0$, $R_+$, $R_-$, where:

$R_0 = \{ \bar 0 \}$.
$R_+$ is the set of nonzero quadratic residues, mod $p$.
$R_-$ is the set of elements of $\FF_p$ which are not quadratic residues.

Similarly, one may partition $\FF_p$ into three subsets, denoted $L_0$, $L_+$, $L_-$, where:

$L_0$ is the set of residues $a$ such that $a^{(p-1)/2} = 0$ (mod $p$).
$L_+$ is the set of residues $a$ such that $a^{(p-1)/2} = -1$ (mod $p$).
$L_-$ is the set of residues $a$ such that $a^{(p-1)/2} =$ (mod $p$).

It suffices to prove that $R_0 = L_0$, $R_+ = L_+$, and $R_- = L_-$. We prove this using a counting argument.

	Consider the sets $R_0$, $L_0$, $R_+$, $L_+$, $R_-$, $L_-$ as defined above.
	Observe that: $L_+$ has at most $(p-1)/2$ elements, since its elements are roots of the polynomial $X^{(p-1)/2} -$ of degree $(p-1)/2$( using root-counting over a field and the fact that $\FF_p$ is a field ) $L_-$ has at most $(p-1)/2$ elements, since its elements are roots of the polynomial $X^{(p+1)/2} +$. $L_0$ has only one element (using the fact that there are no nonzero nilpotents in a field.) Since half of the nonzero residues are quadratic residues, $R_+$ has $(p-1)/2$ elements. If $a \in R_+$, then there exists a nonzero residue $b$ such that $b^2 = a$. Hence, $a^{(p-1)/2} = b^{p-1} =$, by Fermat's little theorem. Thus, we find that: $R_+ \subset L_+$. Since $R_+$ has $(p-1)/2$ elements, and $L_+$ has at most $(p-1)/2$ elements, and $R_+ \subset L_+$, we find that $R_+ = L_+$. We also find that $R_0 = L_0 = \{ \bar 0 \}$. Since $R_-$ is the complement of $R_+ \cup R_0$, and $L_-$ is the complement of $L_+ \cup L_0$, and $R_+ = L_+$ and $R_0 = L_0$, it follows that $R_- = L_-$.
	Hence $R_0 = L_0$, $R_+ = L_+$, and $R_- = L_-$.

These equalities of sets imply precisely the following statements:

$a^{(p-1)/2} =$, mod $p$, if and only if $a$ is a nonzero quadratic residue, mod $p$.
$a^{(p-1)/2} = -1$, mod $p$, if and only if $a$ is nonzero, and not a quadratic residue, mod $p$.
$a^{(p-1)/2} = 0$, mod $p$, if and only if $a$ is a multiple of $p$.

State/Eulers criterion

From SlugmathWiki

Logical Connections

Views

Personal tools

Navigation

Mathematics

Pegagogy

Search

Toolbox