二次剩余

在数论中，特别在同余理论裏，一个整数 $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
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世纪，费马、欧拉、拉格朗日和勒让德等数论学家对二次剩余理论作了初步的研究，证明了一些定理^[1]并作出了一些相关的猜想^[2]，但首先对二次剩余进行有系统的研究的数学家是高斯。他在著作《算术研究》（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为奇数）^[3]。

两个二次剩余的乘积必然还是二次剩余。

基本结论

质数二次剩余

对于质数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包括在内。^[4]这样，每个二次剩余的乘法逆元仍然是二次剩余；二次非剩余的乘法逆元仍然是二次非剩余。^[5]二次剩余的个数与二次非剩余的个数相等，都是 ${\frac {(p-1)}{2}}$ 。^[4]此外，两个二次非剩余的乘积是二次剩余，二次剩余和二次非剩余的乘积是二次非剩余。^[5]

应用二次互反律可以知道，当 $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)^[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)形式的所有数，其中 $k$ 、 $n$ 为整数。

对于奇质数 $p$ 以及与 $p$ 互质的整数 $A$ ， $A$ 是关于 $p$ 的若干次乘方的剩余当且仅当它是关于 $p$ 的剩余。

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

那么p^kA

当k ≥ n时是模pⁿ的剩余；

当k < n并为奇数时是模pⁿ的非剩余。

当k < n并为偶数时，

如果

A

是关于

p

的剩余，那么p^kA就是模pⁿ的剩余；

如果

A

是关于

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。

推广

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

注释及参考来源

^ Lemmemeyer, Ch. 1
^ Lemmermeyer, pp 6–8, p. 16 ff
^ Gauss, Disquisitiones Arithmeticae（以下称DA）, art. 94
^ ^4.0 ^4.1 Gauss, DA, art. 96
^ ^5.0 ^5.1 Gauss, DA, art. 98
^ Gauss, DA, art. 103
^ Gauss, DA, art. 102
^ Gauss, DA, art. 131
^ 比如哈代和怀特就使用它们。
^ Gauss, DA, art 230 ff.
^ 这个扩张对于定义L函数是必须的。

闵嗣鹤、严士健，《初等数论》，第二版，高等教育出版社，2001年。

外部链接

李宗儒，高斯二次互反律^{[永久失效連結]}

[1] Lemmemeyer, Ch. 1

[2] Lemmermeyer, pp 6–8, p. 16 ff

[3] Gauss, Disquisitiones Arithmeticae（以下称DA）, art. 94

[DA96-4] 4.0 ^4.1 Gauss, DA, art. 96

[DA98-5] 5.0 ^5.1 Gauss, DA, art. 98

[6] Gauss, DA, art. 103

[7] Gauss, DA, art. 102

[8] Gauss, DA, art. 131

[9] 比如哈代和怀特就使用它们。

[10] Gauss, DA, art 230 ff.

[11] 这个扩张对于定义L函数是必须的。

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

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