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

若${\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是模这些质数的二次非剩余）。

哪些数是模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^{[永久失效連結]}
• 二次互反律^{[永久失效連結]}
• 潘承洞、潘承彪，《初等数论》，北京大学出版社。

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