欧拉准则

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

叙述

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

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

$d^{\frac{p-1}{2}}\equiv 1(\mathrm{mod}p)$

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

$d^{\frac{p-1}{2}}\equiv -1(\mathrm{mod}p)$

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

举例

例子一：对于给定数，寻找其为二次剩余的模数

令$a=17$。对于怎样的质数$p$，17是模$p$的二次剩余呢？

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

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

再来测试$p=13$。我们有：$17^{\frac{13-1}{2}}=17^6\equiv 1(\mathrm{mod}13)$，因此17是模13的二次剩余。实际上我们有：$17\equiv 4(\mathrm{mod}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(\mathrm{mod}17)$

$6^2=36\equiv 2(\mathrm{mod}17)$

$7^2=49\equiv 15(\mathrm{mod}17)$

$8^2=64\equiv 13(\mathrm{mod}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(\mathrm{mod}17)$.（同理不需计算比9大的数）。

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

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

證明

首先，由于$p$是一个奇素数，由费马小定理，$d^{p-1}\equiv 1(\mathrm{mod}p)$。但是$p-1$是一个偶数，所以有

$(d^{\frac{p-1}{2}}-1)\cdot (d^{\frac{p-1}{2}}+1)\equiv 0(\mathrm{mod}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(\mathrm{mod}p)$

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

$d^{\frac{p-1}{2}}\equiv x^{p-1}\equiv 1(\mathrm{mod}p)$

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

$p$是一个奇素数，所以关于$p$的原根存在。设$a$是$p$的一个原根，则存在$1\le j\le p-1$使得$d=a^j$。于是

$a^{j\frac{p-1}{2}}\equiv 1(\mathrm{mod}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$的二次剩余。

參考资料

• Legendre SymbolTemplate:Dead link
• 二次互反律Template:Dead link
• 潘承洞、潘承彪，《初等数论》，北京大学出版社。

外部链接

• 参考证明(中文)Template:Dead link