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 be an odd prime number. Let be a positive integer that is relative prime to . According to Fermat’s little theorem, we have , which can be written as . So the number represent solutions to the equation . It can be shown that the equation has exactly two solutions. The number has two possibilities. They are:
The result we wish to highlight is that each of the above two cases corresponds to either the solvability or nonsolvability of the following quadratic congruence equation.
___________________________________________________________________________________________________________________
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)
 The equation has solutions if and only if .
 The equation has no solutions if and only if .
Let be an odd prime number. Let be a positive integer that is relative prime to .
Examples
Take as an example. To determine whether this equation is solvable, we can check each integer in the interval . Euler's Criterion reduces the solvability question to a modular exponential problem. It can be shown that . Thus has solutions.
On the other hand, the equation has no solutions since .
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.
Suppose that has solutions. Let be one solution. Then we have . The following derivation establishes the direction of .
Applying Fermat’s little theorem, which gives (giving the last congruence in the above derivation). To apply Fermat’s theorem, we need to show that . Suppose that . Then and . It follows that , contradicting the fact that is relatively prime to the modulus .
Suppose that has no solutions. we make the following claim.

For each number , there exists a number with such that .
To prove the above claim, let . It is clear that . It remains to be shown that . Suppose that . Then , implying that has a solution. Thus .
It follows from the claim that the set consists of many pairs of numbers, each with product . So we have the following:
According to Wilson’s theorem, . Consequently, .
We have shown that if the equation has no solutions, then . Equivalently if , then the equation has solutions.
___________________________________________________________________________________________________________________
Quadratic Residue
The statement that the equation has solutions is commonly described by the term quadratic residue. We say that the number is a quadratic reside modulo if the equation has solutions. If the number is not a quadratic reside modulo , we say that it is a quadratic nonresidue modulo . 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)
 The number is a quadratic residue modulo if and only if .
 The number is a quadratic nonresidue modulo if and only if .
Let be an odd prime number. Let be a positive integer that is relative prime to .
___________________________________________________________________________________________________________________
Legendre Symbol
For those who like to be economical in the statements of mathematical results, the Legendre symbol can be used. The Legendre symbol is defined as follows:
Euler’s Criterion can be restated as follows:

Theorem 1 (Euler’s Criterion)
Let be an odd prime number. Let be a positive integer that is relative prime to . Then the following property holds.
___________________________________________________________________________________________________________________