Tiêu chuẩn Euler

Vì $(\mathbb{Z}/p\mathbb{Z})^{*}$ là nhóm xyclic cấp $p-1$ (một sự kiện chuẩn cho môđun nguyên tố), ta cố định một căn nguyên thủy $g$ và viết $a \equiv g^k \pmod p$ với $0 \le k \le p-2$. Thặng dư bậc hai theo môđun $p$ chính là các lũy thừa chẵn của $g$: nếu $a=g^{2m}$ thì $x=g^m$ thỏa $x^2\equiv a$, và ngược lại mọi bình phương $x^2=(g^j)^2=g^{2j}$ đều là lũy thừa chẵn. Vậy $a$ là thặng dư bậc hai đúng khi $k$ chẵn.

Bây giờ tính $a^{(p-1)/2} \equiv g^{k(p-1)/2} \pmod p$. Nếu $k$ chẵn, viết $k=2m$; khi đó $g^{k(p-1)/2}=g^{m(p-1)}=(g^{p-1})^m\equiv 1^m=1\pmod p$ theo định lý Fermat nhỏ, khớp với trường hợp thặng dư.

Nếu $k$ lẻ, thì $g^{k(p-1)/2}$ là một căn bậc hai của $g^{k(p-1)}=(g^{p-1})^k\equiv 1\pmod p$, nên $a^{(p-1)/2}\equiv \pm 1$. Nó không thể bằng $1$: nếu vậy, cấp của $g$ phải chia hết $k(p-1)/2$, nhưng $\operatorname{ord}(g)=p-1$ và $k$ lẻ nghĩa là $k(p-1)/2$ không phải bội của $p-1$ trừ khi $(p-1)/2$ đã là bội, mâu thuẫn với việc $g$ là căn nguyên thủy có cấp đúng bằng $p-1$. Vậy $a^{(p-1)/2}\equiv -1\pmod p$ đúng khi $k$ lẻ, tức đúng khi $a$ là bất thặng dư.

Gộp cả hai trường hợp: $a^{(p-1)/2}\equiv 1\pmod p$ khi và chỉ khi $a$ là thặng dư bậc hai, và $\equiv -1$ trong trường hợp còn lại, đó chính xác là phát biểu $\left(\dfrac{a}{p}\right) \equiv a^{\frac{p-1}{2}} \pmod{p}$.