📂Number Theory

Euler's Criterion

Theorem ¹

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

Explanation

It means that, to see if $a$ is a quadratic residue (QR) or a non-quadratic residue (NQR), one could just calculate blindly. Of course, exponentiation is not always an easy task, but it’s better than calculating every number. The proof itself is not too difficult, but because many auxiliary lemmas are used, some prior study is needed for easy understanding.

Proof

Let’s look into the cases where $a$ is QR and NQR.

Case 1. When $a$ is QR

Since $a$ is QR, for some $b$, $a = b^2$ holds, and the following is true. $$ 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}$

According to Fermat’s Little Theorem, $b^{p-1} \equiv 1 \pmod{p}$ is true, so $$ a^{p-1 \over 2} \equiv \left( {a \over p} \right) \equiv 1 \pmod{p} $$

---

Case 2. When $a$ is NQR

Starting with 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$ non-congruent solutions

By the Fundamental Theorem of Algebra, the below congruence equation has $p-1$ non-congruent 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 NQRs: For a prime number larger than $2$, $p$, there are exactly $\displaystyle {(p-1) \over 2}$ QRs and NQRs

Meanwhile, for the prime number $p$, there exist exactly $\displaystyle {p-1 \over 2}$ QRs and NQRs, and as seen in Case 1, the $\displaystyle {p-1 \over 2}$ QRs are solutions to $\displaystyle (x^{p-1 \over 2} -1) \equiv 0 \pmod{p}$. Hence, the remaining $\displaystyle {p-1 \over 2}$ NQRs must be solutions to $(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} $$

---

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

■