歐拉準則

若 p 是奇質數，則有：

n 是模 p 的二次剩餘當且僅當：

；

n 是模 p 的二次非剩餘當且僅當：

。

當

時，顯然滿足上述判別準則。

且模 p 意義下的負數可以轉化為正數：

，因此我們只需討論正整數。

對於任意的正整數 n，根據二次剩餘的定義，有：n 不是模 p 的二次剩餘就是模 p的二次非剩餘。

同時因為 p 是奇質數，根據費馬小定理，我們有

，即

模 p 不是 1 就是 -1。

因此我們只需證明 “n 是模 p 的二次剩餘當且僅當：

” 即可。

先證充分性，即：n 是模 p 的二次剩餘時，

。

因為 n 是模 p 的二次剩餘，有

。

同時根據費馬小定理，我們有：

，充分性得證。

再證必要性，即：當

，n 是模 p 的二次剩餘。

假設 g 為模 p 的一個原根，則一定有某個正整數 k 滿足

，因為

，所以

，因為 g 是原根，所以一定有

，因此 k 一定是個偶數，從而一定存在一個數 x 滿足

，此時有

，所以 n 是模 p 的二次剩餘，必要性得證。

綜上所述，n 是模 p 的二次剩餘是

的充要條件，證畢。

例子一：對於給定數，尋找其為二次剩餘的模數

令a = 17。對於怎樣的質數p，17是模p的二次剩餘呢？

根據判別法裏給出的準則，我們可以從小的質數開始檢驗。

首先測試p = 3。我們有：17(3 − 1)/2 = 171 ≡ 2 (mod 3) ≡ -1 (mod 3)，因此17不是模3的二次剩餘。

再來測試p = 13。我們有：17(13 − 1)/2 = 176 ≡ 1 (mod 13)，因此17是模13的二次剩餘。實際上我們有：17 ≡ 4 (mod 13)，而22 = 4.

運用同餘性質和勒讓德符號可以加快檢驗速度。繼續算下去，可以得到：

對於質數p =，(17/p) = +1（也就是説17是模這些質數的二次剩餘）。

對於質數p =，(17/p) = -1（也就是説17是模這些質數的二次非剩餘）。

例子二：對指定的質數p，尋找其二次剩餘

哪些數是模17的二次剩餘？

我們可以手工計算：

12 = 1

22 = 4

32 = 9

42 = 16

52 = 25 ≡ 8 (mod 17)

62 = 36 ≡ 2 (mod 17)

72 = 49 ≡ 15 (mod 17)

82 = 64 ≡ 13 (mod 17)

於是得到：所有模17的二次剩餘的集合是1,2,4,8,9,13,15,16。要注意的是我們只需要算到8，因為9=17-8，9的平方與8的平方模17是同餘的：92 = (−8)2 = 82 ≡ 13 (mod 17).（同理不需計算比9大的數）。

但是對於驗證一個數是不是模17的二次剩餘，就不必將所有模17的二次剩餘全部算出。比如説要檢驗數字3是否是模17的二次剩餘，只需要計算3(17 − 1)/2 = 38 ≡ 812 ≡ − 42 ≡ − 1 (mod 17)，然後由歐拉準則判定3不是模17的二次剩餘。

歐拉準則與高斯引理以及二次互反律有關，並且在定義歐拉-雅可比偽素數（見偽素數）時會用到。