欧拉准则

在数论中，二次剩余的歐拉判別法（又稱歐拉準則）是用来判定给定的整数是否是一个质数的二次剩余。

叙述
若p是奇質數且p不能整除d，則：

: d是模p的二次剩余当且仅当：

:: d^{ \frac{p-1}{2}} \equiv 1 \pmod{p}

: d是模p的非二次剩余当且仅当：

:: d^{ \frac{p-1}{2}} \equiv -1 \pmod{p}

以勒让德符号表示，即為：
d^{ \frac{p-1}{2}} \equiv \left( \frac{d}{p}\right) \pmod{p}

举例
例子一：对于给定数，寻找其为二次剩余的模数
令a=17。对于怎样的质数p，17是模p的二次剩余呢？

根据判别法里给出的准则，我们可以从小的质数开始检验。

首先测试p=3。我们有：17^{\frac{3-1}{2}}=17^1\equiv 2\pmod{3}\equiv -1\pmod{3}，因此17不是模3的二次剩余。

再来测试p=13。我们有：17^{\frac{13-1}{2}}=17^6\equiv 1\pmod{13}，因此17是模13的二次剩余。实际上我们有：17\equiv 4\pmod{13}，而2^2=4.

运用同余性质和勒让德符号可以加快检验速度。继续算下去，可以得到：
:对于质数p=13,19,\cdots,\frac{17}{p}=+1（也就是说17是模这些质数的二次剩余）。
:对于质数p=3,5,7,11,23,\cdots,\frac{17}{p}=-1（也就是说17是模这些质数的二次非剩余）。

例子二：对指定的质数p，寻找其二次剩余
哪些数是模17的二次剩余？

我们可以手工计算：
: 1^2=1
: 2^2=4
: 3^2=9
: 4^2=16
: 5^2=25\equiv 8\pmod{17}
: 6^2 = 36 \equiv 2 \pmod{17}
: 7^2 = 49 \equiv 15 \pmod{17}
: 8^2 = 64 \equiv 13 \pmod{17}

于是得到：所有模17的二次剩余的集合是\{1,2,4,8,9,13,15,16\}。要注意的是我们只需要算到8，因为9=17-8 ，9的平方与8的平方模17是同余的：9^2=(-8)^2=8^2\equiv 13\pmod{17} .（同理不需计算比9大的数）。

但是对于验证一个数是不是模17的二次剩余，就不必将所有模17的二次剩余全部算出。比如说要检验数字3是否是模17的二次剩余，只需要计算3^{\frac{17-1}{2}}=3^8\equiv 81^2\equiv (-4)^2\equiv -1\pmod{17} ，然后由欧拉准则判定3不是模17的二次剩余。

欧拉准则与高斯引理以及二次互反律有关，并且在定义欧拉-雅可比伪素数（见伪素数）时会用到。

證明
首先，由于p是一个奇素数，由费马小定理，d^{p-1} \equiv 1 \pmod{p}。但是p-1是一个偶数，所以有
:(d^{ \frac{p-1}{2} } -1) \cdot (d^{ \frac{p-1}{2} }+1) \equiv 0 \pmod{p}

p是一个素数，所以d^{ \frac{p-1}{2} } -1和d^{ \frac{p-1}{2} }+1 中必有一个是p的倍数。因此d^{ \frac{p-1}{2} } 模p的余数必然是1或-1。

• 證明若d是模p的二次剩餘，則d^{ \frac{p-1}{2}} \equiv 1 \pmod{p}

若d是模p的二次剩餘，則存在x^2 \equiv d \pmod{p}，p跟d,x互質。根據費馬小定理得：

: d^{ \frac{p-1}{2}} \equiv x^{p-1} \equiv 1 \pmod{p}

• 證明若d^{ \frac{p-1}{2} } \equiv 1 \pmod{p}，則d是模p的二次剩餘

p是一个奇素数，所以关于p的原根存在。设a是p的一个原根，则存在1 \le j \le p-1使得d=a^j。于是
:a^{j \frac{p-1}{2} } \equiv 1 \pmod{p}

a是p的一个原根，因此a模p的指数是p-1，于是p-1整除 \frac{ j(p-1) }{2} 。这说明j是一个偶数。令i = \frac{j}{2}，就有(a^i)^2 =a^{2i} = d。d是模p的二次剩余。

參考资料

• [http://grosz.math.txstate.edu/~dhaz/prob_sets/notes/node30.html#eqnnp12 Legendre Symbol]

*[http://www.math.ntu.edu.tw/msa/act/mathcamp/95page/lecture/K.doc 二次互反律]

• 潘承洞、潘承彪，《初等数论》，北京大学出版社。

外部链接
*[http://lxy.hztc.edu.cn/cdsl/wlkt/html/ch5/ch5_5.htm 参考证明(中文)]