欧拉准则

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

叙述

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

${\displaystyle d}$ 是模${\displaystyle p}$ 的二次剩余当且仅当：

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

${\displaystyle d}$ 是模${\displaystyle p}$ 的非二次剩余当且仅当：

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

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

举例

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

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

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

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

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

运用同余性质和勒让德符号可以加快检验速度。继续算下去，可以得到：

对于质数${\displaystyle p=13,19,\cdots ,{\frac {17}{p}}=+1}$ （也就是说17是模这些质数的二次剩余）。

对于质数${\displaystyle p=3,5,7,11,23,\cdots ,{\frac {17}{p}}=-1}$ （也就是说17是模这些质数的二次非剩余）。

例子二：对指定的质数p，寻找其二次剩余

哪些数是模17的二次剩余？

我们可以手工计算：

${\displaystyle 1^{2}=1}$ 

${\displaystyle 2^{2}=4}$ 

${\displaystyle 3^{2}=9}$ 

${\displaystyle 4^{2}=16}$ 

${\displaystyle 5^{2}=25\equiv 8{\pmod {17}}}$ 

${\displaystyle 6^{2}=36\equiv 2{\pmod {17}}}$ 

${\displaystyle 7^{2}=49\equiv 15{\pmod {17}}}$ 

${\displaystyle 8^{2}=64\equiv 13{\pmod {17}}}$ 

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

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

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

證明

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

${\displaystyle (d^{\frac {p-1}{2}}-1)\cdot (d^{\frac {p-1}{2}}+1)\equiv 0{\pmod {p}}}$ 

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

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

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

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

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

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

${\displaystyle a^{j{\frac {p-1}{2}}}\equiv 1{\pmod {p}}}$ 

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

參考资料

• Legendre Symbol^{[永久失效連結]}
• 二次互反律^{[永久失效連結]}
• 潘承洞、潘承彪，《初等数论》，北京大学出版社。

外部链接

• 参考证明(中文)^{[永久失效連結]}