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

___________________________________________________________________________________________________________________

Quadratic Residue

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}

    Advertisements

4 thoughts on “Euler’s Criterion

  1. Pingback: The Legendre symbol | Exploring Number Theory

  2. Pingback: Fermat numbers | Exploring Number Theory

  3. Pingback: Pepin’s Primality Test | Mathematical Cryptography

  4. Pingback: Number Theory | MA | Study of Everything

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s