二次剩餘

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

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

當對任意$X$，$X^2 \equiv d \pmod{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

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

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

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

## 基本結論

### 質數二次剩餘

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

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

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

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

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

應用二次互反律可以知道，當$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時，所有的奇數的平方分別是：

12 ≡ 152 ≡ 1

32 ≡ 132 ≡ 9

52 ≡ 112 ≡ 25

72 ≡ 92 ≡ 17

模8都餘1。而偶數的二次剩餘是：

02 ≡ 82 ≡ 162 ≡ 0

22 ≡ 62≡ 102 ≡ 142≡ 4

42 ≡ 122 ≡ 16

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

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

設模的是pn（n次乘方）。

那麼pkA

當k ≥ n時是模pn的剩餘。

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

當k < n並為偶數時。

如果$A$是關於$p$的剩餘，那麼pkA就是模pn的剩餘。

如果$A$是關於$p$的非剩餘，那麼pkA就是模pn的非剩餘。

### 合數二次剩餘

首先可以看出。

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

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

對於模合數的情況，兩個剩餘的乘積仍然是剩餘，剩餘和非剩餘的乘積必為非剩餘，但是兩個非剩餘的乘積則可能是剩餘、非剩餘或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 R 8，3,5,7 N 8。儘管這種記號在某些方面來說十分簡潔，但現今最常用的是勒讓德符號，或稱二次特徵（見狄利克雷特徵）。對於整數a及奇質數p。

$\left(\frac{a}{p}\right) =\begin{cases}\;\;\,0 \\+1 \\-1 \end{cases}$｜如果p整除a。

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

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

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

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

## 推廣

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

## 注釋及參考來源

- 閔嗣鶴、嚴士健，《初等數論》，第二版，高等教育出版社，2001年。

## 外部連結

- 李宗儒，高斯二次互反律