Euler's Criterion

Let $p$ be an odd prime and $a$ an integer not divisible by $p$ . Euler used the existence of primitive roots to show that $\left(\frac{a}{p}\right)$ is congruent to $a^{(p-1)/2}$ modulo $p$ . We will use this fact repeatedly below in both proofs of Theorem 4.1.7.

Proposition 4.2 (Euler's Criterion)   We have $\left(\frac{a}{p}\right)=1$ if and only if

$$a^{(p-1)/2}\equiv 1\pmod{p}.$$

Proof. The map $\varphi :(\mathbb{Z}/p\mathbb{Z}{})^*\to (\mathbb{Z}/p\mathbb{Z}{})^*$ given by $\varphi (a)= a^{(p-1)/2}$ is a group homomorphism, since powering is a group homomorphism of any abelian group (see Exercise 4.2). Let $\psi:(\mathbb{Z}/p\mathbb{Z}{})^*\to \{\pm 1\}$ be the homomorphism $\psi(a) = \left(\frac{a}{p}\right)$ of Lemma 4.1.4. If $a\in \ker(\psi)$ , then $a=b^2$ for some $b\in(\mathbb{Z}/p\mathbb{Z}{})^*$ , so

$$\varphi (a)=a^{(p-1)/2} = (b^2)^{(p-1)/2} = b^{p-1} = 1.$$

Thus $\ker(\psi)\subset \ker(\varphi )$ . By Lemma 4.1.4, $\ker(\psi)$ has index $2$ in $(\mathbb{Z}/p\mathbb{Z}{})^*$ , i.e., $\char93 (\mathbb{Z}/p\mathbb{Z}{})^*=2\cdot \char93 \ker(\psi)$ . Since the kernel of a homomorphism is a group, and the order of a subgroup divides the order of the group, we have either $\ker(\varphi )=\ker(\psi)$ or $\varphi =1$ . If $\varphi =1$ , the polynomial $x^{(p-1)/2}-1$ has $p-1$ roots in the field $\mathbb{Z}/p\mathbb{Z}{}$ , which contradicts Proposition 2.5.3. Thus $\ker(\varphi )=\ker(\psi)$ , which proves the proposition. $\qedsymbol$

SAGE Example 4.2   From a computational point of view, Corollary 4.2.3 provides a convenient way to compute $\left(\frac{a}{p}\right)$ , which we illustrate in SAGE:

sage: def kr(a, p):
...    if Mod(a,p)^((p-1)//2) == 1:
...       return 1
...    else:
...       return -1
sage: for a in range(1,5):
...    print a, kr(a,5)
1 1
2 -1
3 -1
4 1

Corollary 4.2   The equation $x^2\equiv a\pmod{p}$ has no solution if and only if $a^{(p-1)/2}\equiv -1\pmod{p}$ . Thus $\left(\frac{a}{p}\right) \equiv a^{(p-1)/2}\pmod{p}$ .

Proof. This follows from Proposition 4.2.1 and the fact that the polynomial $x^2-1$ has no roots besides $+1$ and $-1$ (which follows from Proposition 2.5.5). $\qedsymbol$

As additional computational motivation for the value of Corollary 4.2.3, note that to evaluate $\left(\frac{a}{p}\right)$ using Theorem 4.1.7 would not be practical if $a$ and $p$ are both very large, because it would require factoring $a$ . However, Corollary 4.2.3 provides a method for evaluating $\left(\frac{a}{p}\right)$ without factoring $a$ .

Example 4.2   Suppose $p=11$ . By squaring each element of $(\mathbb{Z}/11\mathbb{Z}{})^*$ , we see that the squares modulo $11$ are $\{1,3,4,5,9\}$ . We compute $a^{(p-1)/2}=a^{5}$ for each $a\in (\mathbb{Z}/11\mathbb{Z}{})^*$ and get

$$1^{5} = 1, 2^{5} = -1, 3^{5} = 1, 4^{5} = 1, 5^{5} = 1,$$

$$6^{5} = -1, 7^{5} = -1, 8^{5} = -1, 9^{5} = 1, 10^{5} = -1.$$

Thus the $a$ with $a^5=1$ are $\{1,3,4,5,9\}$ , just as Proposition 4.2.1 predicts.

Example 4.2   We determine whether or not $3$ is a square modulo the prime $p=726377359$ . Using SAGE we find that

sage: p = 726377359
sage: Mod(3, p)^((p-1)//2)
726377358

so

$$3^{(p-1)/2}\equiv -1\pmod{726377359}.$$

Thus $3$ is not a square modulo $p$ . This computation wasn't difficult, but it would have been tedious by hand. Since $3$ is small, the law of quadratic reciprocity provides a way to answer this question, which could easily be carried out by hand:

$$\left(\frac{3}{726377359}\right) = (-1)^{(3-1)/2\cdot (726377359-1)/2} \left(\frac{726377359}{3}\right)$$

$$= (-1) \cdot \left(\frac{1}{3}\right) = -1.$$