跳转到内容

二次剩余

维基百科,自由的百科全书

数论中,特别在同余理论裏,一个整数对另一个整数二次剩余(英語: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 ≡(na)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
kn时是模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]RN来分别表示二次剩余及二次非剩余。例如: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

推广

二次剩餘的推廣叫做高次剩餘,是研究任意是否為模次剩餘的問題。

相關條目

注释及参考来源

  1. ^ Lemmemeyer, Ch. 1
  2. ^ Lemmermeyer, pp 6–8, p. 16 ff
  3. ^ Gauss, Disquisitiones Arithmeticae(以下称DA), art. 94
  4. ^ 4.0 4.1 Gauss, DA, art. 96
  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函数是必须的。
  • 闵嗣鹤、严士健,《初等数论》,第二版,高等教育出版社,2001年。

外部链接