[科普中國(guó)]-二次剩余

定義

在數(shù)論中，特別在同余理論里，一個(gè)整數(shù)X對(duì)另一個(gè)整數(shù)p的二次剩余（英語(yǔ)：Quadratic residue）指X的平方除以p得到的余數(shù)。

當(dāng)存在某個(gè)X，式子 成立時(shí)，稱**“d是模p的二次剩余”**

當(dāng)對(duì)任意不成立時(shí)，稱**“ d是模 p的二次非剩余”**

幾個(gè)自然數(shù)下表列出了1至25對(duì)2至25的二次剩余。

|| || 二次剩余列表

歷史及概念從17世紀(jì)到18世紀(jì)，費(fèi)馬、歐拉、拉格朗日和勒讓德等數(shù)論學(xué)家對(duì)二次剩余理論作了初步的研究，證明了一些定理并作出了一些相關(guān)的猜想，但首先對(duì)二次剩余進(jìn)行有系統(tǒng)的研究的數(shù)學(xué)家是高斯。他在著作《算術(shù)研究》（Disquisitiones Arithmeticae，1801年）中首次引入了術(shù)語(yǔ)“二次剩余”與“二次非剩余”，并聲明在不至于導(dǎo)致混淆的行文中，可以省略“二次”兩字。

為了得到關(guān)于一個(gè)整數(shù) n的所有二次剩余（在一個(gè)完全剩余系中），我們可以直接計(jì)算0, 1,…,n? 1的平方模n的余數(shù)。但只要注意到a≡(n?a)(modn)，我們就可以減少一半的計(jì)算量，只算到n/2了。于是，關(guān)于n的二次剩余的個(gè)數(shù)不可能超過(guò)n/2 + 1（n為偶數(shù)）或(n+ 1)/2（n為奇數(shù)）。1

兩個(gè)二次剩余的乘積必然還是二次剩余。

基本結(jié)論質(zhì)數(shù)二次剩余對(duì)于質(zhì)數(shù)2，每個(gè)整數(shù)都是它的二次剩余。3

以下討論p是奇質(zhì)數(shù)的情況：

對(duì)于X， 而言，能滿足“d是模 p的二次剩余”的 d共有 個(gè)（剩余類(lèi)），分別為：

（0計(jì)算在內(nèi)）

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

應(yīng)用二次互反律可以知道，當(dāng)p模4余1時(shí)，-1是p的二次剩余；如果p模4余3，那么，-1是p的二次非剩余。

要知道d是否為模p的二次剩余，可以運(yùn)用歐拉判別法（或叫歐拉準(zhǔn)則）。

質(zhì)數(shù)乘方每個(gè)奇數(shù)的平方都模8余1，因此模4也余1。設(shè)a是一個(gè)奇數(shù)。m為8，16或2的更高次方，那么a是關(guān)于m的二次剩余當(dāng)且僅當(dāng)a≡ 1(mod 8)。

比如說(shuō)，在模32時(shí)，所有的奇數(shù)的平方分別是：

1≡ 15≡ 1

3≡ 13≡ 9

5≡ 11≡ 25

7≡ 9≡ 17

模8都余1。而偶數(shù)的二次剩余是：

0≡ 8≡ 16≡ 0

2≡ 6≡ 10≡ 14≡ 4

4≡ 12≡ 16

可以看出，關(guān)于8，16或2的更高次方的二次剩余是具有4(8n+ 1)形式的所有數(shù)，其中k、n為整數(shù)。

對(duì)于奇質(zhì)數(shù)p以及與p互質(zhì)的整數(shù)A，A是關(guān)于p的若干次乘方的剩余當(dāng)且僅當(dāng)它是關(guān)于p的剩余。

設(shè)模的是p（n次乘方），

那么pA

當(dāng)k≥n時(shí)是模p的剩余；

當(dāng)k