欧拉准则
在数论中，二次剩余的欧拉判别法（又称欧拉准则）是用来判定给定的整数是否是一个质数的二次剩余。
叙述.
若formula_1是奇质数且formula_1不能整除formula_3，则：
formula_3是模formula_1的二次剩余当且仅当：
formula_6
formula_3是模formula_1的非二次剩余当且仅当：
formula_9
以勒让德符号表示，即为：
formula_10
举例.
例子一：对于给定数，寻找其为二次剩余的模数.
令formula_11。对于怎样的质数formula_1，17是模"formula_1"的二次剩余呢？
根据判别法里给出的准则，我们可以从小的质数开始检验。
首先测试formula_14。我们有：formula_15，因此17不是模3的二次剩余。
再来测试formula_16。我们有：formula_17，因此17是模13的二次剩余。实际上我们有：formula_18，而formula_19.
运用同余性质和勒让德符号可以加快检验速度。继续算下去，可以得到：
对于质数formula_20（也就是说17是模这些质数的二次剩余）。
对于质数formula_21（也就是说17是模这些质数的二次非剩余）。
例子二：对指定的质数"p"，寻找其二次剩余.
哪些数是模17的二次剩余？
我们可以手工计算：
formula_22
formula_19
formula_24
formula_25
formula_26
formula_27
formula_28
formula_29
于是得到：所有模17的二次剩余的集合是formula_30。要注意的是我们只需要算到8，因为formula_31，9的平方与8的平方模17是同余的：formula_32.（同理不需计算比9大的数）。
但是对于验证一个数是不是模17的二次剩余，就不必将所有模17的二次剩余全部算出。比如说要检验数字3是否是模17的二次剩余，只需要计算formula_33，然后由欧拉准则判定3不是模17的二次剩余。
欧拉准则与高斯引理以及二次互反律有关，并且在定义欧拉-雅可比伪素数（见伪素数）时会用到。
证明.
首先，由于formula_1是一个奇素数，由费马小定理，formula_35。但是formula_36是一个偶数，所以有
formula_37
formula_1是一个素数，所以formula_39和formula_40中必有一个是formula_1的倍数。因此formula_42模formula_1的余数必然是1或-1。
若formula_3是模formula_1的二次剩余，则存在formula_49，formula_1跟formula_51互质。根据费马小定理得：
formula_52
formula_1是一个奇素数，所以关于formula_1的原根存在。设formula_58是formula_1的一个原根，则存在formula_60使得formula_61。于是
formula_62
formula_58是formula_1的一个原根，因此formula_58模formula_1的指数是formula_36，于是formula_36整除formula_69。这说明formula_70是一个偶数。令formula_71，就有formula_72。formula_3是模formula_1的二次剩余。
生成维基百科快照图片，大概需要3-30秒！
如果网站内容有侵犯您的版权
请联系：pinbor@iissy.com
请联系：pinbor@iissy.com
Copyright ©2014 iissy.com, All Rights Reserved.