欧拉判别法

1. 定理表述

设 $p$ 是奇素数，整数 $a$ 与 $p$ 互素（即 $\gcd (a,p)=1$）。

• 平方剩余判定： $a$ 是模 $p$ 的平方剩余，当且仅当： $a^{\frac{p-1}{2}}\equiv 1(\mathrm{mod}p)$

• 平方非剩余判定： $a$ 是模 $p$ 的平方非剩余，当且仅当： $a^{\frac{p-1}{2}}\equiv -1(\mathrm{mod}p)$

2. 与勒让德符号的关系

欧拉判别法实际上给出了勒让德符号的计算公式。对于任意整数 $a$（若 $p\mid a$ 则为 0）： $\left(\frac{a}{p}\right)\equiv a^{\frac{p-1}{2}}(\mathrm{mod}p)$ 由于勒让德符号的取值只能是 $1,-1,0$，且 $a^{\frac{p-1}{2}}$ 在模 $p$ 下也只能同余于 $1,-1,0$，因此两者在数值上完全对应。

3. 证明思路

该定理基于 费马小定理：

1. 由费马小定理，对于任意与 $p$ 互素的 $a$，有 $a^{p-1}\equiv 1(\mathrm{mod}p)$。
2. 利用平方差公式因式分解： $a^{p-1}-1=(a^{\frac{p-1}{2}}-1)(a^{\frac{p-1}{2}}+1)\equiv 0(\mathrm{mod}p)$
3. 这说明 $a^{\frac{p-1}{2}}$ 模 $p$ 的值只能是 $1$ 或 $-1$。
4. 若 $a$ 是平方剩余（存在 $x$ 使 $x^2\equiv a$），则 $a^{\frac{p-1}{2}}\equiv (x^2{)}^{\frac{p-1}{2}}\equiv x^{p-1}\equiv 1(\mathrm{mod}p)$。
5. 利用拉格朗日定理可知，同余式 $x^{\frac{p-1}{2}}\equiv 1$ 最多有 $\frac{p-1}{2}$ 个解，而平方剩余恰好有这么多，因此剩下的即为平方非剩余，对应值 $-1$。

4. 计算示例

题目：判断 $3$ 是否为模 $17$ 的平方剩余。

解：

1. 模数 $p=17$，指数为 $\frac{17-1}{2}=8$。
2. 计算 $3^8(\mathrm{mod}17)$：
   • $3^2=9$
   • $3^4=81=4\times 17+13\equiv 13\equiv -4(\mathrm{mod}17)$
   • $3^8\equiv (-4{)}^2=16(\mathrm{mod}17)$
3. 因为 $16\equiv -1(\mathrm{mod}17)$。
4. 结论：根据欧拉判别法，$3$ 是模 $17$ 的平方非剩余（即方程 $x^2\equiv 3(\mathrm{mod}17)$ 无解）。