# Euler’s Criterion

In this post we discuss a beautiful connection between Fermat’s little theorem and the solvability of a quadratic congruence equation. The discussion leads to a theorem that is commonly called Euler’s Criterion.

___________________________________________________________________________________________________________________

The Setting

Let $p$ be an odd prime number. Let $a$ be a positive integer that is relative prime to $p$. According to Fermat’s little theorem, we have $\displaystyle a^{p-1} \equiv 1 \ (\text{mod} \ p)$, which can be written as $\displaystyle (a^{\frac{p-1}{2}})^2 \equiv 1 \ (\text{mod} \ p)$. So the number $\displaystyle a^{\frac{p-1}{2}}$ represent solutions to the equation $y^2 \equiv 1 \ (\text{mod} \ p)$. It can be shown that the equation $y^2 \equiv 1 \ (\text{mod} \ p)$ has exactly two solutions. The number $\displaystyle a^{\frac{p-1}{2}}$ has two possibilities. They are:

$\displaystyle a^{\frac{p-1}{2}} \equiv 1 \ (\text{mod} \ p) \ \ \ \ \text{or} \ \ \ \ a^{\frac{p-1}{2}} \equiv -1 \ (\text{mod} \ p)$

The result we wish to highlight is that each of the above two cases corresponds to either the solvability or non-solvability of the following quadratic congruence equation.

$x^2 \equiv a \ (\text{mod} \ p) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (1)$

___________________________________________________________________________________________________________________

Euler’s Criterion

The result indicated at the end of the preceding section is known as Euler’s Criterion. We have the following theorem.

Theorem 1 (Euler’s Criterion)

Let $p$ be an odd prime number. Let $a$ be a positive integer that is relative prime to $p$.

1. The equation $x^2 \equiv a \ (\text{mod} \ p)$ has solutions if and only if $\displaystyle a^{\frac{p-1}{2}} \equiv 1 \ (\text{mod} \ p)$.
2. $\text{ }$

3. The equation $x^2 \equiv a \ (\text{mod} \ p)$ has no solutions if and only if $\displaystyle a^{\frac{p-1}{2}} \equiv -1 \ (\text{mod} \ p)$.

Examples
Take $x^2 \equiv 899 \ (\text{mod} \ 50261)$ as an example. To determine whether this equation is solvable, we can check each integer in the interval $1 \le x <50261$. Euler's Criterion reduces the solvability question to a modular exponential problem. It can be shown that $\displaystyle 899^{\frac{50261-1}{2}}=899^{25130} \equiv 1 \ (\text{mod} \ p)$. Thus $x^2 \equiv 899 \ (\text{mod} \ 50261)$ has solutions.

On the other hand, the equation $x^2 \equiv 13961 \ (\text{mod} \ 50261)$ has no solutions since $\displaystyle 13961^{25130} \equiv -1 \ (\text{mod} \ p)$.

Proof of Theorem 1
We prove the first bullet point. The two bullet points in Theorem 1 are equivalent. We need only prove one of them.

$\Longrightarrow$
Suppose that $x^2 \equiv a \ (\text{mod} \ p)$ has solutions. Let $x=t$ be one solution. Then we have $t^2 \equiv a \ (\text{mod} \ p)$. The following derivation establishes the direction of $\Longrightarrow$.

$\displaystyle a^{\frac{p-1}{2}} \equiv (t^2)^{\frac{p-1}{2}} \equiv t^{p-1} \equiv 1 \ (\text{mod} \ p)$

Applying Fermat’s little theorem, which gives $t^{p-1} \equiv 1 \ (\text{mod} \ p)$ (giving the last congruence in the above derivation). To apply Fermat’s theorem, we need to show that $p \not \lvert \ t$. Suppose that $p \ \lvert \ t$. Then $p \ \lvert \ t^2$ and $t^2 \equiv 0 \ (\text{mod} \ p)$. It follows that $a \equiv 0 \ (\text{mod} \ p)$, contradicting the fact that $a$ is relatively prime to the modulus $p$.

$\Longleftarrow$
Suppose that $x^2 \equiv a \ (\text{mod} \ p)$ has no solutions. we make the following claim.

For each number $h \in \left\{1,2,\cdots,p-1 \right\}$, there exists a number $k \in \left\{1,2,\cdots,p-1 \right\}$ with $h \ne k$ such that $hk=a$.

To prove the above claim, let $k=h^{-1}a$. It is clear that $hk=a$. It remains to be shown that $h \ne k$. Suppose that $h=h^{-1}a$. Then $h^2=a$, implying that $x^2 \equiv a \ (\text{mod} \ p)$ has a solution. Thus $h \ne k$.

It follows from the claim that the set $\left\{1,2,\cdots,p-1 \right\}$ consists of $\displaystyle \frac{p-1}{2}$ many pairs of numbers, each with product $a$. So we have the following:

$\displaystyle 1 \cdot 2 \cdots p-1 \equiv a^{\frac{p-1}{2}} \ (\text{mod} \ p)$

According to Wilson’s theorem, $\displaystyle 1 \cdot 2 \cdots p-1 \equiv -1 \ (\text{mod} \ p)$. Consequently, $\displaystyle a^{\frac{p-1}{2}} \equiv -1 \ (\text{mod} \ p)$.

We have shown that if the equation $x^2 \equiv a \ (\text{mod} \ p)$ has no solutions, then $\displaystyle a^{\frac{p-1}{2}} \equiv -1 \ (\text{mod} \ p)$. Equivalently if $\displaystyle a^{\frac{p-1}{2}} \equiv 1 \ (\text{mod} \ p)$, then the equation $x^2 \equiv a \ (\text{mod} \ p)$ has solutions. $\blacksquare$

___________________________________________________________________________________________________________________

The statement that the equation $x^2 \equiv a \ (\text{mod} \ p)$ has solutions is commonly described by the term quadratic residue. We say that the number $a$ is a quadratic reside modulo $p$ if the equation $x^2 \equiv a \ (\text{mod} \ p)$ has solutions. If the number $a$ is not a quadratic reside modulo $p$, we say that it is a quadratic nonresidue modulo $p$. Whenever there is no need to make a distinction between quadratic and higher power, we will just omit the word quadratic and refer to residues and nonresidues.

Euler’s Criterion can be restated using the term quadratic residues.

Theorem 1 (Euler’s Criterion)

Let $p$ be an odd prime number. Let $a$ be a positive integer that is relative prime to $p$.

1. The number $a$ is a quadratic residue modulo $p$ if and only if $\displaystyle a^{\frac{p-1}{2}} \equiv 1 \ (\text{mod} \ p)$.
2. $\text{ }$

3. The number $a$ is a quadratic nonresidue modulo $p$ if and only if $\displaystyle a^{\frac{p-1}{2}} \equiv -1 \ (\text{mod} \ p)$.

___________________________________________________________________________________________________________________

Legendre Symbol

For those who like to be economical in the statements of mathematical results, the Legendre symbol can be used. The Legendre symbol $\displaystyle \biggl(\frac{a}{p}\biggr)$ is defined as follows:

$\displaystyle \biggl(\frac{a}{p}\biggr)=\left\{\begin{matrix}1&\ \text{if } a \text{ is a quadratic residue modulo }p \\{-1}&\ \text{if } a \text{ is a quadratic nonresidue modulo }p \end{matrix}\right.$

Euler’s Criterion can be restated as follows:

Theorem 1 (Euler’s Criterion)

Let $p$ be an odd prime number. Let $a$ be a positive integer that is relative prime to $p$. Then the following property holds.

$\displaystyle \biggl(\frac{a}{p}\biggr) \equiv \displaystyle a^{\frac{p-1}{2}} \ (\text{mod} \ p)$

___________________________________________________________________________________________________________________

$\copyright \ 2013 \text{ by Dan Ma}$