數論中,二次剩餘歐拉判別法(又稱歐拉準則)是用來判定給定的整數是否是一個質數二次剩餘

敘述

編輯

 是奇質數 不能整除 ,則:

 是模 的二次剩餘當且僅當
 
 是模 的非二次剩餘當且僅當:
 

勒讓德符號表示,即為:  

舉例

編輯

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

編輯

 。對於怎樣的質數 ,17是模 的二次剩餘呢?

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

首先測試 。我們有: ,因此17不是模3的二次剩餘。

再來測試 。我們有: ,因此17是模13的二次剩餘。實際上我們有: ,而 .

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

對於質數 (也就是說17是模這些質數的二次剩餘)。
對於質數 (也就是說17是模這些質數的二次非剩餘)。

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

編輯

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

我們可以手工計算:

 
 
 
 
 
 
 
 

於是得到:所有模17的二次剩餘的集合是 。要注意的是我們只需要算到8,因為 ,9的平方與8的平方模17是同餘的: .(同理不需計算比9大的數)。

但是對於驗證一個數是不是模17的二次剩餘,就不必將所有模17的二次剩餘全部算出。比如說要檢驗數字3是否是模17的二次剩餘,只需要計算 ,然後由歐拉準則判定3不是模17的二次剩餘。

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

證明

編輯

首先,由於 是一個奇素數,由費馬小定理 。但是 是一個偶數,所以有

 

 是一個素數,所以  中必有一個是 的倍數。因此  的餘數必然是1或-1。

  • 證明若 是模 的二次剩餘,則 

 是模 的二次剩餘,則存在   互質。根據費馬小定理得:

 
  • 證明若 ,則 是模 的二次剩餘

 是一個奇素數,所以關於 原根存在。設  的一個原根,則存在 使得 。於是

 

  的一個原根,因此  的指數是 ,於是 整除 。這說明 是一個偶數。令 ,就有  是模 的二次剩餘。

參考資料

編輯

外部連結

編輯