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

# Two Proofs of Wilson’s Theorem

In this post, we give two proofs of Wilson’s theorem. The second proof uses the notion of primitive roots. The following is the statement of the theorem.

Theorem 1 (Wilson’s Theorem)

Let $p$ be a positive integer. Then $p$ is a prime number if and only if $(p-1)! \equiv -1 \ (\text{mod} \ p)$.

An alternative way of stating Wilson’s theorem is that $p$ is a prime number if and only if $(p-1)! +1$ is divisible by $p$.

___________________________________________________________________________________________________________________

One Proof

We use $\text{GCD}(a,b)$ to denote the greatest common divisor of the positive integers $a$ and $b$. We use the following lemma.

Lemma 2

Let $m$ be a prime number. Then the congruence equation $x^2 \equiv 1 \ (\text{mod} \ m)$ has exactly two solutions. They are $x=1,m-1$.

Proof of Lemma 2

It is straightforward to see that $1^2 \equiv 1 \ (\text{mod} \ m)$ and $(m-1)^2 \equiv 1 \ (\text{mod} \ m)$. It remains to show that $x=1,m-1$ are the only two solutions. To that end, we show that any solution of $x^2 \equiv 1 \ (\text{mod} \ m)$ must be one of these.

Let $t$ be a solution of the above congruence equation. This means that $t^2 \equiv 1 \ (\text{mod} \ m)$ and $0 \le t \le m-1$. So $m \ \lvert \ (t^2-1)=(t+1)(t-1)$. By Euclid’s lemma, either $m \ \lvert (t+1)$ or $m \ \lvert (t-1)$. The first case gives $t \equiv -1 \ (\text{mod} \ m)$ and the second case gives $t \equiv 1 \ (\text{mod} \ m)$. Since $0 \le t \le m-1$, the first congruence means that $t=p-1$ and the second congruence means that $t=1$. $\blacksquare$

Lemma 3

Let $a$ be a positive integer with $0 \le a \le m-1$. Then the following conditions are equivalent.

1. The number $a$ and the modulus $m$ are relatively prime, i.e., $\text{GCD}(a,m)=1$.
2. There exists a unique integer $b$ with $0 \le b \le m-1$ such that $ab \equiv 1 \ (\text{mod} \ m)$. In other words, the number $a$ has a multiplicative inverse modulo $m$.

Lemma 3 is proved in a previous post (see Theorem 1 in the post Euler’s phi function, part 1).

Proof of Theorem 1 (first proof)

$\Longleftarrow$
Suppose $p$ is a positive integer that is not prime. Then $p$ has a factor among the integers $2,3,\cdots,p-1$. Thus $d=\text{GCD}((p-1)!,p)>1$ (i.e. $(p-1)!$ and $p$ are not relatively prime).

We claim that $(p-1)! \not \equiv -1 \ (\text{mod} \ p)$. Suppose that $(p-1)! \equiv -1 \ (\text{mod} \ p)$. Then we have $(p-1)! \cdot x+ p \cdot y=-1$ for some integers $x$ and $y$. Since $d$ divides the left-hand side of the equation, $d \ \lvert \ -1$. But $d=\text{GCD}((p-1)!,p)>1$. So $(p-1)! \not \equiv -1 \ (\text{mod} \ p)$.

We have proved that if $p$ is not prime, then $(p-1)! \not \equiv -1 \ (\text{mod} \ p)$. Equivalently if $(p-1)! \equiv -1 \ (\text{mod} \ p)$, then $p$ is prime.

$\Longrightarrow$
Suppose $p$ is prime. For each $a \in \left\{1,2,3,\cdots,p-1 \right\}$, $a$ and $p$ are relatively prime. By Lemma 3, for each such $a$, there exists a unique $b$ in $\left\{1,2,3,\cdots,p-1 \right\}$ such that $ab \equiv 1 \ (\text{mod} \ p)$.

By Lemma 2, the congruence equation $x^2 \equiv 1 \ (\text{mod} \ p)$ has exactly two solutions, namely $x=1,p-1$. Thus $a=1,p-1$ are the only numbers in $\left\{1,2,3,\cdots,p-1 \right\}$ for which $a$ and its inverse $b$ are the same. For each $a \in \left\{2,3,\cdots,p-2 \right\}$, $a \ne b$.

The number $p-3$ is an even integer. There are $p-3$ many numbers in the set $\left\{2,3,\cdots,p-2 \right\}$. Based on the discussion in the preceding paragraph, the set $\left\{2,3,\cdots,p-2 \right\}$ consists of $\displaystyle \frac{p-3}{2}$ many pairs of numbers such that the product of each pair is $\equiv 1 \ (\text{mod} \ p)$. Thus we have

$2 \cdot 3 \cdots (p-2) \equiv 1 \ (\text{mod} \ p)$

We can also write $(p-2)! \equiv 1 \ (\text{mod} \ p)$. Multiply $p-1$ on both sides of the equation, we have $(p-1)! \equiv p-1 \ (\text{mod} \ p)$. Since $p-1 \equiv -1 \ (\text{mod} \ p)$, we have $(p-1)! \equiv -1 \ (\text{mod} \ p)$. $\blacksquare$

___________________________________________________________________________________________________________________

Another Proof

To carry out the following proof, we use the theorem that every prime modulus has a primitive root. A primitive root for a given prime modulus $m$ is a positive integer $g$ with $1 \le g \le m-1$ such that the least positive exponent satisfying the equation $g^x \equiv 1 \ (\text{mod} \ m)$ is $m-1$.

Another property of primitive roots that is used in the following proof is that for a given primitive root $g$ for a given prime modulus $m$, the powers of $g$ would generate the elements of the set $\left\{1,2,3,\cdots,p-1 \right\}$ (these are the least residues that are relatively prime to the prime modulus $m$).

Basic properties of primitive roots are discussed in the post called Defining Primitive Root.

Proof of Theorem 1 (second proof)

We prove the direction that if $p$ is prime, then $(p-1)! \equiv -1 \ (\text{mod} \ p)$.

$\Longrightarrow$
If $p=2$, it is clear that $(p-1)! \equiv -1 \ (\text{mod} \ p)$. Suppose $p$ is an odd prime. Then there exists a primitive root modulo $p$. Let $g$ be one such. Because $p$ is prime, every integer $x$ in the interval $1 \le x \le p-1$ is relative prime to $p$. One property of a primitive root for the prime modulus $p$ is that the powers of $g$ would generate the integers in the interval $1 \le x \le p-1$. Specifically we have the following set equality

$\left\{r_1,r_2,r_3,\cdots,r_{p-1} \right\}=\left\{1,2,3,\cdots,p-1 \right\}$

where each $r_j$ is a least residue modulo $p$, i.e., $0 \le r_j \le p-1$ and $r_j \equiv g^j \ (\text{mod} \ p)$. As a result of the above set equality, we have the following congruence equality.

$g^1 g^2 g^3 \cdots g^{p-1} \equiv r_1 \cdot r_2 \cdot r_3 \cdots r_{p-1} \equiv (p-1)! \ (\text{mod} \ p) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (1)$

The exponents in the left-hand side of the above congruence equality can be summed as follows:

$\displaystyle 1+2+3+\cdots+p-1=\frac{(p-1)p}{2}$

The congruence equality (1) can be further simplified as follows:

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

It follows from Fermat’s theorem that $g^{p-1} \equiv 1 \ (\text{mod} \ p)$. Thus the number $\displaystyle g^{\frac{p-1}{2}}$ satisfies the congruence equation $x^2 \equiv 1 \ (\text{mod} \ p)$. By Lemma 2, $x^2 \equiv 1 \ (\text{mod} \ p)$ has exactly 2 solutions, namely $x=1$ or $x=p-1$. So we have the following are two possibilities for $\displaystyle g^{\frac{p-1}{2}}$.

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

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

But the first one is not possible since $g$ is a primitive root modulo $p$. So the second congruence is true. It follows that

$\displaystyle (p-1)! \equiv g^{\frac{(p-1)p}{2}}=(-1)^p \equiv -1 \equiv \ (\text{mod} \ p)$

The above derivation concludes the proof of the theorem. $\blacksquare$

___________________________________________________________________________________________________________________

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