二次非剩餘

數論基本概念之一。它是初等數論中非常重要的結果，不僅可用來判斷二次同餘式是否有解，還有很多用途。C.F.高斯稱它為算術中的寶石，他一人先後給出多個證明。

基本介紹

• 中文名：二次非剩餘
• 簡介：數論基本概念之一
• 稱號：算術中的寶石
• 用途：判斷二次同餘式是否有解
• 學科：數理科學
• 稱謂：“算術中的寶石”

定義

在數論中，特別在同餘理論里，一個整數 對另一個整數 的二次剩餘（英語：Quadratic residue）指 的平方除以 得到的餘數。

當存在某個 ，式子 成立時，稱 是模 的二次剩餘”

當對任意 ， 不成立時，稱“是模 的二次非剩餘”

研究二次剩餘的理論稱為二次剩餘理論。二次剩餘理論在實際上有廣泛的套用，包括從噪音工程學到密碼學以及大數分解。

研究歷史以及基本概念

從17世紀到18世紀，費馬、歐拉、拉格朗日和勒讓德等數論學家對二次剩餘理論作了初步的研究，證明了一些定理並作出了一些相關的猜想，但首先對二次剩餘進行有系統的研究的數學家是高斯。他在著作《算術研究》（Disquisitiones Arithmeticae，1801年）中首次引入了術語“二次剩餘”與“二次非剩餘”，並聲明在不至於導致混淆的行文中，可以省略“二次”兩字。

基本結論

質數二次非剩餘

對於質數2，每個整數都是它的二次剩餘。

以下討論 是奇質數的情況：

對於 ， 而言，能滿足“ 是模 的二次剩餘”的 共有 個（剩餘類），分別為：

（0計算在內）

此外是 個二次非剩餘。但在很多情況下，我們只考慮乘法群Z/pZ，因此不將0包括在內。這樣，每個二次剩餘的乘法逆元仍然是二次剩餘；二次非剩餘的乘法逆元仍然是二次非剩餘。二次剩餘的個數與二次非剩餘的個數相等，都是 。此外，兩個二次非剩餘的乘積是二次剩餘，二次剩餘和二次非剩餘的乘積是二次非剩餘。

套用二次互反律可以知道，當 模4餘1時，-1是 的二次剩餘；如果 模4餘3，那么，-1是 的二次非剩餘。

要知道d是否為模p的二次剩餘，可以運用歐拉判別法（或叫歐拉準則）。

合數二次非剩餘

首先可以看出，

• 如果a是模n的剩餘，並且p整除n，那么a是模p的剩餘。
• 如果a是模n的非剩餘，那么存在p整除n，使得a是模p的非剩餘。

對於模合數的情況，兩個剩餘的乘積仍然是剩餘，剩餘和非剩餘的乘積必為非剩餘，但是兩個非剩餘的乘積則可能是剩餘、非剩餘或0。

比如，對於模15的情況

1, 2, 3,4, 5,6, 7, 8,9,10, 11, 12, 13, 14（粗斜體為二次剩餘）。

兩個二次非剩餘2和8的乘積是二次剩餘1，但另外兩個二次非剩餘2和7的乘積是二次非剩餘14。

相關記號

高斯使用R和N來分別表示二次剩餘及二次非剩餘。例如：2 R 7，5 N 7，並且1 和5 R 8，3和7 N 8。儘管這種記號在某些方面來說十分簡潔，但現今最常用的是勒讓德符號，或稱二次特徵（見狄利克雷特徵）。對於整數a及奇質數p，

	如果p整除a；
	如果a是模p的二次剩餘且p不整除a
	如果a是模p的二次非剩餘。

之所以將0另分一類有兩個原因。首先，這使公式和定理敘述方便。其次，二次特徵是一個從乘法群Z/pZ射到複數域的群同態，可以將這個同態擴張到整數構成的乘法半群。

相比高斯的記號，勒讓德符號的優勢在於可以寫在公式里（作為一個數字值）。此外勒讓德符號可以推廣到三次以至高次剩餘。

勒讓德符號中的分母只限奇質數，對於一般的合數，有推廣的雅可比符號。雅可比符號的性質比前者複雜。如果aRm那么，如果那么aNm。但如果，我們不能知道aRm還是aNm。