查看“︁Euler 准则”︁的源代码

[[分类:同余理论]]
[[分类:以 Euler 命名]]
{{InfoBox
|name=欧拉准则
|eng_name=Euler's criterion
|aliases=欧拉判别法,欧拉判别条件
}}
'''<ins>欧拉</ins>准则'''('''Euler's criterion''')指判定一个整数是否是[[质数]]模下的[[二次剩余]]的一种判定标准。

== 定理 ==

对奇质数 <math>p</math> 和整数 <math>a</math> ，满足 <math>\operatorname{gcd}(a, p)=1</math> ，则有：

<math>
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>p</math> ，

* <math>1, 2, \dots, n-1</math> 中，二次剩余和二次非剩余必各占一半。
* 任意两个二次剩余相乘都是二次剩余，任意两个二次非剩余相乘也是二次剩余，只有一个二次剩余和一个二次非剩余相乘时，得到二次非剩余。
** 如果把 <math>1, 2, \dots, n-1</math> 分成两个非[[空集|空]][[集合]] <math>C_1, C_2</math> ，使得任意 <math>C_1 C_1 \subseteq C_1</math> 、 <math>C_2 C_2 \subseteq C_2</math> 、 <math>C_1 C_2 \subseteq C_2</math> ，则有唯一解 <math>C_1</math> 取二次剩余集合、 <math>C_2</math> 取二次非剩余集合。
* 考虑模逆的话，二次剩余的模逆都是二次剩余，非二次剩余的模逆都是非二次剩余。


{{同余理论}}