欧拉判别法

由于 $(\mathbb{Z}/p\mathbb{Z})^{*}$ 是阶为 $p-1$ 的循环群(素数模下的标准事实),固定一个原根 $g$,写 $a \equiv g^k \pmod p$,其中 $0 \le k \le p-2$。模 $p$ 的二次剩余恰好是 $g$ 的偶数次幂:若 $a=g^{2m}$,则 $x=g^m$ 满足 $x^2\equiv a$;反之每个平方 $x^2=(g^j)^2=g^{2j}$ 都是偶数次幂。因此 $a$ 是二次剩余当且仅当 $k$ 为偶数。

现在计算 $a^{(p-1)/2} \equiv g^{k(p-1)/2} \pmod p$。若 $k$ 为偶数,记 $k=2m$,由费马小定理得 $g^{k(p-1)/2}=g^{m(p-1)}=(g^{p-1})^m\equiv 1^m=1\pmod p$,与剩余情形吻合。

若 $k$ 为奇数,则 $g^{k(p-1)/2}$ 是 $g^{k(p-1)}=(g^{p-1})^k\equiv 1\pmod p$ 的平方根,故 $a^{(p-1)/2}\equiv \pm 1$。它不能等于 $1$:否则 $g$ 的阶必须整除 $k(p-1)/2$,但 $\operatorname{ord}(g)=p-1$ 且 $k$ 为奇数意味着除非 $(p-1)/2$ 本身已是倍数,否则 $k(p-1)/2$ 不是 $p-1$ 的倍数,这与 $g$ 是阶恰为 $p-1$ 的原根矛盾。所以恰好当 $k$ 为奇数即 $a$ 为非剩余时,$a^{(p-1)/2}\equiv -1\pmod p$。

综合两种情形:$a^{(p-1)/2}\equiv 1\pmod p$ 当且仅当 $a$ 是二次剩余,否则 $\equiv -1$,这正是 $\left(\dfrac{a}{p}\right) \equiv a^{\frac{p-1}{2}} \pmod{p}$ 的断言。