在数论中,特别在同余理论裏,一个整数对另一个整数的二次剩余(英語:Quadratic residue)指的平方除以得到的余数。
當存在某個,式子成立時,稱「是模的二次剩余」
當对任意,不成立時,稱「是模的二次非剩余」
研究二次剩余的理论称为二次剩余理论。二次剩余理论在实际上有广泛的应用,包括从噪音工程学到密码学以及大数分解。
前几个自然数的二次剩余
下表列出了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年)中首次引入了术语“二次剩余”与“二次非剩余”,并声明在不至于导致混淆的行文中,可以省略“二次”两字。
为了得到关于一个整数的所有二次剩余(在一个完全剩余系中),我们可以直接计算0, 1,…, n − 1的平方模的余数。但只要注意到a2 ≡(n − a)2(mod n),我们就可以减少一半的计算量,只算到n/2了。于是,关于的二次剩余的个数不可能超过n/2 + 1(n为偶数)或(n + 1)/2(n为奇数)[3]。
两个二次剩余的乘积必然还是二次剩余。
基本结论
质数二次剩余
对于质数2,每个整数都是它的二次剩余。
以下討論是奇質數的情況:
對於,而言,能滿足「是模的二次剩餘」的共有個(剩余类),分別為:
(0計算在內)
此外是个二次非剩余。但在很多情况下,我们只考虑乘法群Z/pZ,因此不将0包括在内。[4]这样,每个二次剩余的乘法逆元仍然是二次剩余;二次非剩余的乘法逆元仍然是二次非剩余。[5]二次剩余的个数与二次非剩余的个数相等,都是。[4]此外,两个二次非剩余的乘积是二次剩余,二次剩余和二次非剩余的乘积是二次非剩余。[5]
应用二次互反律可以知道,当模4余1时,-1是的二次剩余;如果模4余3,那么,-1是的二次非剩余。
要知道d是否為模p的二次剩餘,可以运用歐拉判別法(或叫歐拉準則)。
质数乘方的二次剩余
每个奇数的平方都模8余1,因此模4也余1。设a是一个奇数。m为8,16或2的更高次方,那么a是关于m的二次剩余当且仅当a ≡ 1(mod 8)[6]。
比如说,在模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)形式的所有数,其中、为整数。
对于奇质数以及与 互质的整数,是关于的若干次乘方的剩余当且仅当它是关于的剩余。
设模的是pn(n次乘方),
- 那么pkA
- 当k ≥ n时是模pn的剩余;
- 当k < n并为奇数时是模pn的非剩余。
当k < n并为偶数时,
- 如果是关于的剩余,那么pkA就是模pn的剩余;
- 如果是关于的非剩余,那么pkA就是模pn的非剩余[7]。
首先可以看出,
- 如果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。
相关记号
高斯使用[8]R和N来分别表示二次剩余及二次非剩余。例如:2 R 7,5 N 7,并且1 R 8,3,5,7 N 8。尽管这种记号在某些方面来说十分简洁[9][10],但现今最常用的是勒让德符号,或称二次特征(见狄利克雷特征)。对于整数a及奇质数p,
|
如果p整除a;
|
如果a是模p的二次剩余且p不整除a
|
如果a是模p的二次非剩余。
|
之所以将0另分一类有两个原因。首先,这使公式和定理叙述方便。其次,二次特征是一个从乘法群Z/pZ射到复数域的群同态,可以将这个同态扩张到整数构成的乘法半群[11]。
相比高斯的记号,勒让德符号的优势在于可以写在公式里(作为一个数字值)。此外勒让德符号可以推广到三次以至高次剩餘。
勒让德符号中的分母只限奇质数,对于一般的奇合数,有推广的雅可比符号。雅可比符号的性质比前者复杂。如果a R m那么,如果那么a N m。但如果,我们不能知道a R m还是a N m。
推广
二次剩餘的推廣叫做高次剩餘,是研究任意,中是否為模的次剩餘的問題。
相關條目
注释及参考来源
- ^ 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年。
外部链接