歐拉準則

在數論中，二次剩餘的歐拉判別法（又稱歐拉準則）是用來判定給定的整數是否是一個質數的二次剩餘。

敘述

若$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\leq j\leq 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$的二次剩餘。

參考資料

• Legendre Symbol
• 二次互反律
• 潘承洞、潘承彪，《初等數論》，北京大學出版社。

外部連結

• 參考證明(中文)