Euler 准则
| 欧拉准则 | |
|---|---|
| 术语名称 | 欧拉准则 |
| 英语名称 | Euler's criterion |
| 别名 | 欧拉判别法, 欧拉判别条件 |
欧拉准则(Euler's criterion)指判定一个整数是否是质数模下的二次剩余的一种判定标准。
定理
对奇质数 [math]\displaystyle{ p }[/math] 和整数 [math]\displaystyle{ a }[/math] ，满足 [math]\displaystyle{ \operatorname{gcd}(a, p)=1 }[/math] ，则有：
[math]\displaystyle{ a^{\frac{p-1}{2}} \equiv \begin{cases} 1 \pmod p &, \exists x ( x^2 \equiv a \pmod p ) \\ -1 \pmod p &, \lnot\exists x ( x^2 \equiv a \pmod p ) \\ \end{cases} }[/math]
注：右侧可以被改写成 Legendre 符号。
推论
对质数 [math]\displaystyle{ p }[/math] ，
- [math]\displaystyle{ 1, 2, \dots, n-1 }[/math] 中，二次剩余和二次非剩余必各占一半。
- 任意两个二次剩余相乘都是二次剩余，任意两个二次非剩余相乘也是二次剩余，只有一个二次剩余和一个二次非剩余相乘时，得到二次非剩余。
- 如果把 [math]\displaystyle{ 1, 2, \dots, n-1 }[/math] 分成两个非空集合 [math]\displaystyle{ C_1, C_2 }[/math] ，使得任意 [math]\displaystyle{ C_1 C_1 \subseteq C_1 }[/math] 、 [math]\displaystyle{ C_2 C_2 \subseteq C_2 }[/math] 、 [math]\displaystyle{ C_1 C_2 \subseteq C_2 }[/math] ，则有唯一解 [math]\displaystyle{ C_1 }[/math] 取二次剩余集合、 [math]\displaystyle{ C_2 }[/math] 取二次非剩余集合。
- 考虑模逆的话，二次剩余的模逆都是二次剩余，非二次剩余的模逆都是非二次剩余。