定義

在數論中,特別在同餘理論里,一個整數X對另一個整數p的 二次剩餘(英語:Quadratic residue)指X的平方除以p得到的餘數。

當存在某個X,式子 成立時,稱 “d是模p的二次剩餘”
當對任意不成立時,稱 “ d是模 p的二次非剩餘”
幾個自然數
下表列出了1至25對2至25的二次剩餘。
n | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 |
n | 1 | 4 | 9 | 16 | 25 | 36 | 49 | 64 | 81 | 100 | 121 | 144 | 169 | 196 | 225 | 256 | 289 | 324 | 361 | 400 | 441 | 484 | 529 | 576 | 625 |
mod 2 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
mod 3 | 1 | 1 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 1 |
mod 4 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
mod 5 | 1 | 4 | 4 | 1 | 0 | 1 | 4 | 4 | 1 | 0 | 1 | 4 | 4 | 1 | 0 | 1 | 4 | 4 | 1 | 0 | 1 | 4 | 4 | 1 | 0 |
mod 6 | 1 | 4 | 3 | 4 | 1 | 0 | 1 | 4 | 3 | 4 | 1 | 0 | 1 | 4 | 3 | 4 | 1 | 0 | 1 | 4 | 3 | 4 | 1 | 0 | 1 |
mod 7 | 1 | 4 | 2 | 2 | 4 | 1 | 0 | 1 | 4 | 2 | 2 | 4 | 1 | 0 | 1 | 4 | 2 | 2 | 4 | 1 | 0 | 1 | 4 | 2 | 2 |
mod 8 | 1 | 4 | 1 | 0 | 1 | 4 | 1 | 0 | 1 | 4 | 1 | 0 | 1 | 4 | 1 | 0 | 1 | 4 | 1 | 0 | 1 | 4 | 1 | 0 | 1 |
mod 9 | 1 | 4 | 0 | 7 | 7 | 0 | 4 | 1 | 0 | 1 | 4 | 0 | 7 | 7 | 0 | 4 | 1 | 0 | 1 | 4 | 0 | 7 | 7 | 0 | 4 |
mod 10 | 1 | 4 | 9 | 6 | 5 | 6 | 9 | 4 | 1 | 0 | 1 | 4 | 9 | 6 | 5 | 6 | 9 | 4 | 1 | 0 | 1 | 4 | 9 | 6 | 5 |
mod 11 | 1 | 4 | 9 | 5 | 3 | 3 | 5 | 9 | 4 | 1 | 0 | 1 | 4 | 9 | 5 | 3 | 3 | 5 | 9 | 4 | 1 | 0 | 1 | 4 | 9 |
mod 12 | 1 | 4 | 9 | 4 | 1 | 0 | 1 | 4 | 9 | 4 | 1 | 0 | 1 | 4 | 9 | 4 | 1 | 0 | 1 | 4 | 9 | 4 | 1 | 0 | 1 |
mod 13 | 1 | 4 | 9 | 3 | 12 | 10 | 10 | 12 | 3 | 9 | 4 | 1 | 0 | 1 | 4 | 9 | 3 | 12 | 10 | 10 | 12 | 3 | 9 | 4 | 1 |
mod 14 | 1 | 4 | 9 | 2 | 11 | 8 | 7 | 8 | 11 | 2 | 9 | 4 | 1 | 0 | 1 | 4 | 9 | 2 | 11 | 8 | 7 | 8 | 11 | 2 | 9 |
mod 15 | 1 | 4 | 9 | 1 | 10 | 6 | 4 | 4 | 6 | 10 | 1 | 9 | 4 | 1 | 0 | 1 | 4 | 9 | 1 | 10 | 6 | 4 | 4 | 6 | 10 |
mod 16 | 1 | 4 | 9 | 0 | 9 | 4 | 1 | 0 | 1 | 4 | 9 | 0 | 9 | 4 | 1 | 0 | 1 | 4 | 9 | 0 | 9 | 4 | 1 | 0 | 1 |
mod 17 | 1 | 4 | 9 | 16 | 8 | 2 | 15 | 13 | 13 | 15 | 2 | 8 | 16 | 9 | 4 | 1 | 0 | 1 | 4 | 9 | 16 | 8 | 2 | 15 | 13 |
mod 18 | 1 | 4 | 9 | 16 | 7 | 0 | 13 | 10 | 9 | 10 | 13 | 0 | 7 | 16 | 9 | 4 | 1 | 0 | 1 | 4 | 9 | 16 | 7 | 0 | 13 |
mod 19 | 1 | 4 | 9 | 16 | 6 | 17 | 11 | 7 | 5 | 5 | 7 | 11 | 17 | 6 | 16 | 9 | 4 | 1 | 0 | 1 | 4 | 9 | 16 | 6 | 17 |
mod 20 | 1 | 4 | 9 | 16 | 5 | 16 | 9 | 4 | 1 | 0 | 1 | 4 | 9 | 16 | 5 | 16 | 9 | 4 | 1 | 0 | 1 | 4 | 9 | 16 | 5 |
mod 21 | 1 | 4 | 9 | 16 | 4 | 15 | 7 | 1 | 18 | 16 | 16 | 18 | 1 | 7 | 15 | 4 | 16 | 9 | 4 | 1 | 0 | 1 | 4 | 9 | 16 |
mod 22 | 1 | 4 | 9 | 16 | 3 | 14 | 5 | 20 | 15 | 12 | 11 | 12 | 15 | 20 | 5 | 14 | 3 | 16 | 9 | 4 | 1 | 0 | 1 | 4 | 9 |
mod 23 | 1 | 4 | 9 | 16 | 2 | 13 | 3 | 18 | 12 | 8 | 6 | 6 | 8 | 12 | 18 | 3 | 13 | 2 | 16 | 9 | 4 | 1 | 0 | 1 | 4 |
mod 24 | 1 | 4 | 9 | 16 | 1 | 12 | 1 | 16 | 9 | 4 | 1 | 0 | 1 | 4 | 9 | 16 | 1 | 12 | 1 | 16 | 9 | 4 | 1 | 0 | 1 |
mod 25 | 1 | 4 | 9 | 16 | 0 | 11 | 24 | 14 | 6 | 0 | 21 | 19 | 19 | 21 | 0 | 6 | 14 | 24 | 11 | 0 | 16 | 9 | 4 | 1 | 0 |
歷史及概念
從17世紀到18世紀,費馬、歐拉、拉格朗日和勒讓德等數論學家對二次剩餘理論作了初步的研究,證明了一些定理並作出了一些相關的猜想,但首先對二次剩餘進行有系統的研究的數學家是高斯。他在著作《算術研究》( Disquisitiones Arithmeticae,1801年)中首次引入了術語“二次剩餘”與“二次非剩餘”,並聲明在不至於導致混淆的行文中,可以省略“二次”兩字。
為了得到關於一個整數 n的所有二次剩餘(在一個完全剩餘系中),我們可以直接計算0, 1,…, n− 1的平方模n的餘數。但只要注意到 a≡( n− a)(mod n),我們就可以減少一半的計算量,只算到 n/2了。於是,關於n的二次剩餘的個數不可能超過 n/2 + 1( n為偶數)或( n+ 1)/2( n為奇數)。
兩個二次剩餘的乘積必然還是二次剩餘。
基本結論
質數二次剩餘
對於質數2,每個整數都是它的二次剩餘。
以下討論p是奇質數的情況:


對於X, 而言,能滿足“d是模 p的二次剩餘”的 d共有 個(剩餘類),分別為:

(0計算在內)

此外是 個二次非剩餘。但在很多情況下,我們只考慮乘法群 Z/pZ,因此不將0包括在內。這樣,每個二次剩餘的乘法逆元仍然是二次剩餘;二次非剩餘的乘法逆元仍然是二次非剩餘。二次剩餘的個數與二次非剩餘的個數相等,都是。此外,兩個二次非剩餘的乘積是二次剩餘,二次剩餘和二次非剩餘的乘積是二次非剩餘。
套用二次互反律可以知道,當p模4餘1時,-1是p的二次剩餘;如果p模4餘3,那么,-1是p的二次非剩餘。
要知道d是否為模p的二次剩餘,可以運用歐拉判別法(或叫歐拉準則)。
質數乘方
每個奇數的平方都模8餘1,因此模4也餘1。設 a是一個奇數。 m為8,16或2的更高次方,那么 a是關於 m的二次剩餘若且唯若 a≡ 1(mod 8)。
比如說,在模32時,所有的奇數的平方分別是:
•1≡ 15≡ 1
•3≡ 13≡ 9
•5≡ 11≡ 25
•7≡ 9≡ 17
模8都餘1。而偶數的二次剩餘是:
•0≡ 8≡ 16≡ 0
•2≡ 6≡ 10≡ 14≡ 4
•4≡ 12≡ 16
可以看出,關於8,16或2的更高次方的二次剩餘是具有4(8 n+ 1)形式的所有數,其中k、n為整數。
對於奇質數p以及與p互質的整數A,A是關於p的若干次乘方的剩餘若且唯若它是關於p的剩餘。
設模的是 p(n次乘方),
•那么pA
•當k≥n時是模p的剩餘;
•當k
當 k< n並為偶數時,
•如果A是關於p的剩餘,那么pA就是模p的剩餘;
•如果A是關於p的非剩餘,那么pA就是模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射到複數域的群同態,可以將這個同態擴張到整數構成的乘法半群。
相比高斯的記號,勒讓德符號的優勢在於可以寫在公式里(作為一個數字值)。此外勒讓德符號可以推廣到三次以至高次剩餘。



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

二次剩餘的推廣叫做高次剩餘,是研究任意X,中d是否為模p的n次剩餘的問題。