二次非剩餘

數論基本概念之一。它是初等數論中非常重要的結果,不僅可用來判斷二次同餘式是否有解,還有很多用途。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。

相關記號

高斯使用RN來分別表示二次剩餘及二次非剩餘。例如: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

熱門詞條

聯絡我們