Before we look at Euler's Criterion, we are going to make two distinct definitions regarding quadratic congruences:

Definition: "a" is called a quadratic residue (mod m) if $x^2 \equiv a \pmod m$ has solutions, and is called a quadratic non-residue (mod m) if the congruence does not have any solutions.

Euler's Criterion

Theorem (Euler's Criterion): If p is an odd prime where $p \nmid a$, then the quadratic congruence $x^2 \equiv a \pmod m$ has solutions or no solutions depending if $a^{(\frac{p - 1}{2})} \equiv 1 \pmod p \quad \mathbb{or} \quad a^{(\frac{p - 1}{2})} \equiv -1 \pmod p$.

Proof of Euler's Criterion

• Proof: Suppose that g is a primitive root of the odd prime p. It thus follows that $a \equiv g^k \pmod {p}$ for some integer k.

• If k is even, then $x^2 \equiv a \pmod {p}$ has the solution of the least residue of g^k/2 since it follows that:

(1)

\begin{align} a^{\frac{p - 1}{2}} \equiv \left ( g^k \right ){\frac{p - 1}{2}} \equiv \left ( g^{\frac{k}{2}} \right )^{p - 1} \equiv 1 \pmod {p} \end{align}

• Now suppose that k is odd. It thus follows that $g^{\frac{p - 1}{2}} = -1$ since g is a primitive root. Hence:

(2)

\begin{align} a^{\frac{p - 1}{2}} \equiv \left ( g^k \right ) ^ {\frac{p - 1}{2}} \equiv \left ( g ^{\frac{p - 1}{2}} \right)^k \equiv (-1)^k \equiv -1 \pmod {p} \end{align}

• So when k is odd, there does not exist a solution to the quadratic congruence $x^2 \equiv a \pmod {p}$.

Example 1

Using Euler's Criterion, decide whether or not the quadratic congruence $x^2 \equiv 7 \pmod {31}$ has a solution or not.

To use Euler's Criterion, we must determine whether 7¹⁵ is congruent to 1 or -1 modulo 31. We note that 31 is an odd prime, and 31 does not divide 7, and hence we can apply Euler's Criterion.

First, let's use successive squaring to figure out what 7¹⁵ is congruent to (mod 31):

(3)

\begin{align} 7 \equiv 7 \pmod {31} \\ 7^2 \equiv 18 \pmod {31} \\ 7^4 \equiv (18)^2 = 324 \equiv 14 \pmod {31} \\ 7^8 \equiv (14)^2 = 196 \equiv 10 \pmod {31} \\ 7^{15} = 7^8 \cdot 7^4 \cdot 7^2 \cdot 7 \equiv (10)(14)(18)(7) = 17640 \equiv 1 \pmod {31} \end{align}

Since $7^{15} \equiv 1 \pmod {31}$, it follows by Euler's Criterion that there exists solutions to $x^2 \equiv 7 \pmod {31}$.

Example 2

Using Euler's Criterion, decide whether or not a solution exists to the quadratic congruence $x \equiv 15 \pmod {29}$.

Once again we note that 29 is an odd prime, and 29 does not divide 15. By Euler's Criterion, we need to decide whether 15¹⁴ is congruent to 1 or -1 (mod 29). We will do this once again by successive squaring:

(4)

\begin{align} 15 \equiv 15 \pmod {29} \\ 15^2 \equiv 22 \pmod {29} \\ 15^4 \equiv (22)^2 = 484 \equiv 20 \pmod {29} \\ 15^8 \equiv (20)^2 = 400 \equiv 23 \pmod {29} \\ 15^{14} = 15^8 \cdot 15^4 \cdot 15^2 \equiv (23)(20)(22) = 10120 \equiv 28 \equiv -1 \pmod {29} \end{align}

By Euler's Criterion, it follows that since $15^{14} \equiv -1 \pmod {29}$, there exists no solutions to the quadratic congruence $x^2 \equiv 15 \pmod {29}$.