歐拉準則

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

敘述編輯

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