欧拉准则

若${\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 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
• 二次互反律
• 潘承洞、潘承彪，《初等数论》，北京大学出版社。

• 参考证明(中文)