二次剩余

维基百科,自由的百科全书
跳转至: 导航搜索

数论中,特别在同余理论裏,一个整数 X 对另一个整数 p二次剩餘英语Quadratic residue)指 X平方 X^2 除以 p 得到的余数

當對於某個d及某個X,式子 X^2 \equiv d \pmod{p} 成立時,稱d是模p的二次剩餘」

當對於某個d及某個XX^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
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年)中首次引入了术语“二次剩余”与“二次非剩余”,并声明在不至于导致混淆的行文中,可以省略“二次”两字。

为了得到关于一个整数n的所有二次剩余(在一个完全剩余系中),我们可以直接计算0, 1, …, n − 1的平方模n的余数。但只要注意到a2 ≡ (na)2 (mod n),我们就可以减少一半的计算量,只算到n/2了。于是,关于n的二次剩余的个数不可能超过n/2 + 1 (n 为偶数)或 (n + 1)/2 (n 为奇数)[3]

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


基本结论[编辑]

质数二次剩余[编辑]

对于质数2,每个整数都是它的二次剩余。

以下討論p是奇質數的情況:

對於XX^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是pf的二次剩余;如果p模4余3,那么,-1是p的二次非剩余。

要知道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)形式的所有数,其中 kn 为整数。

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

设模的是 pn (n 次乘方),

那么 pkA
kn 时是模 pn 的剩余;
k < n 并为奇数时是模 pn 的非剩余。

k < n 并为偶数时,

如果 A 是关于 p 的剩余,那么 pkA 就是模 pn 的剩余;
如果 A 是关于 p 的非剩余,那么 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

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

之所以将0另分一类有两个原因。首先,这使公式和定理叙述方便。其次,二次特征是一个从乘法群 Z/pZ 射到复数域的群同态(\tfrac{np}{p}) = 0 可以将这个同态扩张到整数构成的乘法半群[11]

相比高斯的记号,勒让德符号的优势在于可以写在公式里(作为一个数字值)。此外勒让德符号可以推广到三次以至高次剩余。

勒让德符号中的分母只限奇质数,对于一般的合数,有推广的雅可比符号。雅可比符号的性质比前者复杂。如果 a R m 那么(\tfrac{a}{m}) = 1,如果(\tfrac{a}{m}) = -1那么 a N m。但如果(\tfrac{a}{m}) = 1,我们不能知道 a R m 还是 a N m

推广[编辑]

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

相關條目[编辑]

注释及参考来源[编辑]

  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年。

外部链接[编辑]