欧拉判别法

p 是奇素数，$(a,p)=1$，a 是模 p 平方剩余的充要条件是

$$a^{(p-1)/2}\equiv 1(modp)$$

不是的条件是：

$$a^{(p-1)/2}\equiv -1(modp)$$

---

证明： 充分性

$$b^2\equiv a$$ $$a^{(p-1)/2}\equiv b^{2\cdot (p-1)/2}\equiv b^{p-1}\equiv 1$$

必要性

由于

$$(x^{(p-1)/2}-1)|(x^p-x)$$

所以根据 素数模同余式解的个数不超过它的次数 得到下面方程一定有 $\frac{p-1}{2}$ 个解

$$x^{(p-1)/2}\equiv 1(modp)$$