二次剩餘

在數論中，特別在同餘理論裏，一個整數${\displaystyle X}$對另一個整數${\displaystyle p}$的二次剩餘（英語：Quadratic residue）指${\displaystyle X}$的平方${\displaystyle X^{2}}$除以${\displaystyle p}$得到的餘數。

當存在某個${\displaystyle X}$，式子${\displaystyle X^{2}\equiv d{\pmod {p}}}$成立時，稱「${\displaystyle d}$是模${\displaystyle p}$的二次剩餘」

當對任意${\displaystyle X}$，${\displaystyle X^{2}\equiv d{\pmod {p}}}$不成立時，稱「${\displaystyle d}$是模${\displaystyle 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
n2	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世紀，費馬、歐拉、拉格朗日和勒讓德等數論學家對二次剩餘理論作了初步的研究，證明了一些定理^[1]並作出了一些相關的猜想^[2]，但首先對二次剩餘進行有系統的研究的數學家是高斯。他在著作《算術研究》（Disquisitiones Arithmeticae，1801年）中首次引入了術語「二次剩餘」與「二次非剩餘」，並聲明在不至於導致混淆的行文中，可以省略「二次」兩字。

為了得到關於一個整數${\displaystyle n}$的所有二次剩餘（在一個完全剩餘系中），我們可以直接計算0, 1,..., n − 1的平方模${\displaystyle n}$的餘數。但只要注意到a² ≡(n − a)²(mod n)，我們就可以減少一半的計算量，只算到n/2了。於是，關於${\displaystyle n}$的二次剩餘的個數不可能超過n/2 + 1（n為偶數）或(n + 1)/2（n為奇數）^[3]。

兩個二次剩餘的乘積必然還是二次剩餘。

基本結論

質數二次剩餘

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

以下討論${\displaystyle p}$是奇質數的情況：

對於${\displaystyle X}$，${\displaystyle X^{2}\equiv d{\pmod {p}}}$而言，能滿足「${\displaystyle d}$是模${\displaystyle p}$的二次剩餘」的${\displaystyle d}$共有${\displaystyle {\frac {(p+1)}{2}}}$個（剩餘類），分別為：

${\displaystyle 0^{2},1^{2},...\left({{\frac {(p-1)}{2}}-1}\right)^{2},\left({\frac {p-1}{2}}\right)^{2}}$（0計算在內）

此外是${\displaystyle {\frac {(p-1)}{2}}}$個二次非剩餘。但在很多情況下，我們只考慮乘法群Z/pZ，因此不將0包括在內。^[4]這樣，每個二次剩餘的乘法逆元仍然是二次剩餘；二次非剩餘的乘法逆元仍然是二次非剩餘。^[5]二次剩餘的個數與二次非剩餘的個數相等，都是${\displaystyle {\frac {(p-1)}{2}}}$。^[4]此外，兩個二次非剩餘的乘積是二次剩餘，二次剩餘和二次非剩餘的乘積是二次非剩餘。^[5]

應用二次互反律可以知道，當${\displaystyle p}$模4餘1時，-1是${\displaystyle p}$的二次剩餘；如果${\displaystyle p}$模4餘3，那麼，-1是${\displaystyle p}$的二次非剩餘。

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

質數乘方的二次剩餘

每個奇數的平方都模8餘1，因此模4也餘1。設a是一個奇數。m為8，16或2的更高次方，那麼a是關於m的二次剩餘若且唯若a ≡ 1(mod 8)^[6]。

比如說，在模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^k(8n + 1)形式的所有數，其中${\displaystyle k}$、${\displaystyle n}$為整數。

對於奇質數${\displaystyle p}$以及與${\displaystyle p}$ 互質的整數${\displaystyle A}$，${\displaystyle A}$是關於${\displaystyle p}$的若干次乘方的剩餘若且唯若它是關於${\displaystyle p}$的剩餘。

設模的是pⁿ（n次乘方），

那麼p^kA

當k ≥ n時是模pⁿ的剩餘；

當k < n並為奇數時是模pⁿ的非剩餘。

當k < n並為偶數時，

如果${\displaystyle A}$是關於${\displaystyle p}$的剩餘，那麼p^kA就是模pⁿ的剩餘；

如果${\displaystyle A}$是關於${\displaystyle p}$的非剩餘，那麼p^kA就是模pⁿ的非剩餘^[7]。

合數二次剩餘

首先可以看出，

如果a是模n的剩餘，並且p^k 整除n，那麼a是模p^k的剩餘。

如果a是模n的非剩餘，那麼存在p^k 整除n，使得a是模p^k的非剩餘。

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

比如，對於模15的情況
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14（粗斜體為二次剩餘）。
兩個二次非剩餘2和8的乘積是二次剩餘1，但另外兩個二次非剩餘2和7的乘積是二次非剩餘14。

相關記號

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

${\displaystyle \left({\frac {a}{p}}\right)={\begin{cases}\;\;\,0\\+1\\-1\end{cases}}}$	如果p整除a；
	如果a是模p的二次剩餘且p不整除a
	如果a是模p的二次非剩餘。

之所以將0另分一類有兩個原因。首先，這使公式和定理敍述方便。其次，二次特徵是一個從乘法群Z/pZ射到複數域的群同態，${\displaystyle ({\tfrac {np}{p}})=0}$可以將這個同態擴張到整數構成的乘法半群^[11]。

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

勒讓德符號中的分母只限奇質數，對於一般的奇合數，有推廣的雅可比符號。雅可比符號的性質比前者複雜。如果a R m那麼${\displaystyle ({\tfrac {a}{m}})=1}$，如果${\displaystyle ({\tfrac {a}{m}})=-1}$那麼a N m。但如果${\displaystyle ({\tfrac {a}{m}})=1}$，我們不能知道a R m還是a N m。

推廣

二次剩餘的推廣叫做高次剩餘，是研究任意${\displaystyle X}$，${\displaystyle X^{n}\equiv d{\pmod {p}}}$中${\displaystyle d}$是否為模${\displaystyle p}$的${\displaystyle n}$次剩餘的問題。

相關條目

• 勒讓德符號
• 同餘
• 歐拉準則
• 二次互反律
• 三次互反律