二次剩余

在数论中，特别在同余理论里，一个整数$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年。

## 外部链接

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