📂Number Theory

Euler's Criterion

Theorem¹

For a prime $p \ne 2$, $$ a^{{p-1} \over {2}} \equiv \left( {a \over p} \right) \pmod{p} $$

Explanation

According to this, when you want to see whether a single $a$ is a quadratic residue or a non-residue, you can simply go ahead and compute it. Of course, exponentiation is not such an easy task, but it is still better than computing every number. The proof itself is not very difficult, but since it uses many lemmas, some prior study makes it easier to understand.

Proof

Let us consider the cases where $a$ is a QR and where $a$ is an NR separately.

Case 1. $a$ is a QR

Since $a$ is a QR, $a = b^2$ for some $b$, and the following holds. $$ a^{p-1 \over 2} \equiv b^2{p-1 \over 2} \equiv b^{p-1} \pmod{p} $$

Fermat’s little theorem: $a^{p-1} \equiv 1 \pmod{p}$

By Fermat’s little theorem, $b^{p-1} \equiv 1 \pmod{p}$, so $$ a^{p-1 \over 2} \equiv \left( {a \over p} \right) \equiv 1 \pmod{p} $$

---

Case 2. $a$ is an NR

We start from the congruence equation $x^{p-1} - 1 \equiv 0 \pmod{p}$.

Fundamental theorem of algebra for congruence equations: For $f(x)=a_{ 0 }x^{ d }+a_{ 1 }x^{ d-1 }+ \cdots +a_{ d-1 }x+a_{ d }$, the equation $f(x)\equiv 0 \pmod{p}$ has at most $d$ incongruent solutions.

By the fundamental theorem of algebra, the congruence equation below has $p-1$ incongruent solutions.

$$ 0 \equiv x^{p-1} - 1 \equiv (x^{p-1 \over 2} +1) (x^{p-1 \over 2} -1) \pmod{p} $$

Number of QRs and NRs: For a prime $p$ greater than $2$, there exist exactly $\displaystyle {(p-1) \over 2}$ QRs and NRs each.

Meanwhile, for a prime $p$, there exist exactly $\displaystyle {p-1 \over 2}$ QRs and $\displaystyle {p-1 \over 2}$ NRs, and as seen in Case 1, the $\displaystyle {p-1 \over 2}$ QRs are solutions of $\displaystyle (x^{p-1 \over 2} -1) \equiv 0 \pmod{p}$. That is, the remaining $\displaystyle {p-1 \over 2}$ NRs must be solutions of $(x^{p-1 \over 2} +1) \equiv 0 \pmod{p}$. Therefore, the following holds. $$ a^{p-1 \over 2} \equiv \left( {a \over p} \right) \equiv -1 \pmod{p} $$

---

Combining Cases 1 and 2, we obtain the following. $$ a^{p-1 \over 2} \equiv \left( {a \over p} \right) \pmod{p} $$

■