二次剩余

在数论中，特别在同余理论裏，一个整数${\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
n^2	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}$ 次剩餘的問題。

相關條目

• 勒让德符号
• 同餘
• 欧拉准则
• 二次互反律
• 三次互反律

注释及参考来源

1. Lemmemeyer, Ch. 1
2. Lemmermeyer, pp 6–8, p. 16 ff
3. Gauss, Disquisitiones Arithmeticae（以下称DA）, art. 94
4. Gauss, DA, art. 96
5. 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函数是必须的。

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

外部链接

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