二次剩余 - 维基百科,自由的百科全书
在数论中,特别在同余理论裏,一个整数对另一个整数的二次剩余(英語: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]。
- 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]。
首先可以看出,
对于模合数的情况,两个剩余的乘积仍然是剩余,剩余和非剩余的乘积必为非剩余,但是两个非剩余的乘积则可能是剩余、非剩余或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。
推广
[编辑]二次剩餘的推廣叫做高次剩餘,是研究任意,中是否為模的次剩餘的問題。
相關條目
[编辑]注释及参考来源
[编辑]- 闵嗣鹤、严士健,《初等数论》,第二版,高等教育出版社,2001年。