什么是二次剩余

教育
关注：5.17K次

研究一般的二次同余式αx2+bx+с呏0(modm)，可归结为讨论形如

的同余式，其中m>1，(m，n)=1。若它有解，则n叫作模m 的二次剩余；若它无解，则n叫作模m 的二次非剩余。设p 是一个奇素数，在模p的缩系中有

个二次剩余和

个二次非剩余，且12，22，…，

就是模p的全部二次剩余。如果n是模p的二次剩余，则

，如果n是模p的二次非剩余，则

勒让德符号与二次互反律

设p

n，当n是模p的二次剩余，记为

；当n是模p 的二次非剩余，记为

。符号

叫做勒让德符号。它是 A.-M.勒让德于1798年引入的，对于计算n是否模p的二次剩余，带来很大的方便。勒让德符号有以下一些简单的性质：

（1）当n呏n┡(modp)时，

；

（2）

；

（3）

，

；

（4）

。因此，任给一个整数 n，只需计算

，

（q 为奇素数）这三种值。1801年，C.F.高斯证明了以下结果：设p 是奇素数，（p，n）=1，在

个数n，2n，…，

模p的最小正剩余数中有l个大于

，则

，一般叫做高斯引理。由高斯引理可知

。1801年，高斯还用这个引理证明了著名的二次互反律：设p>2，q>2是两个素数，p≠q，则

，这是初等数论中至关重要的定理，它不仅能够方便地计算勒让德符号的值，而且在数论许多方面都非常有用。例：计算

，因为438=2·3·73，所以

。二次互反律由L.欧拉首先提出，而由高斯于1796年首先证明。后来，各种证明不断出现，迄今已有 150多个不同的证明。高斯自己就给出了好几个证明，其中第三个证明是运用高斯引理得出的。二次互反律引起许多数学家对代数数域中高次互反律的研究，从而使得在这个方面出现了不少意义深刻的工作。

雅可比符号

设m是一个正奇数，m=p1…pt，pi(i=1，2，…，t)是素数，（m，n）=1，则

叫做雅可比符号。引入勒让德符号，运用二次互反定律，可判断二次同余式是否有解，但计算时需要把一个正整数分解成标准分解式，而计算雅可比符号就不需要这样做。利用勒让德符号的性质，容易推得：

（1）

和

。

（2）若m和n是二正奇数，且(m，n)=1，则

。需要注意的是，当

时，则x2呏n(mod m)无解，但当

时，x2呏n(mod m)不一定有解。

原根和指数

设h为一整数，n为正整数，(h，n)=1，适合hl呏1(mod n)的最小正整数l叫做h对模n的次数。如果l=φ(n)，此时h称为模n的原根。1773年，L.欧拉首先证明了素数p有原根存在。1785年，勒让德证明了;设

，恰有φ(l)个模p互不同余的数对模p 的次数为l。1801年，高斯证明了：n 有原根存在的充分必要条件是n=2，4，pl，2pl，这里l≥1，p是奇素数。设g是素数p的一个原根，对任一整数n，(n，p)＝1，必有一数 α使n呏gα(modp)，0≤α<p-1，α叫做n对模p的指数，以α=indgn表示，在不致混淆时，简写成 α＝indn，它具有与通常对数类似的性质。例如，如果p

αb，则indαb呏indα+indb(modp-1)。指数的引入，对于简化问题有帮助。

估计模p 的最小正原根的上界是著名的原根问题之一。设 m为p-1的不同素因数的个数，g（p）表示模p的最小正原根，可证得

。运用更精密的方法，1959～1962年，D.A.伯吉斯与王元独立地证明了

，其中ε为任意正数，而与“

”有关的常数仅依赖于ε。另一个重要的原根问题是E.阿廷在 1927年提出的猜想：对于任意不等于1、p-1及完全平方的正整数α，必定存在无穷多个素数p，以α为原根。人们称之为阿廷猜想。这一猜想尚未解决。

原根和指数可应用于代数编码和数字信号处理等领域。例如，运用原根存在的定理，1968的，C.M.雷德证明了长为p的离散傅里叶变换(DFT)可化为循环卷积，其中p为奇素数。后来人们还证明了长为pl和2pl的情形。

k次剩余

设k>1，m>1，(m，n)=1，若二项同余式xk呏n(modm)有解，则n叫做模m 的k次剩余；若无解，则n叫做模m 的k次非剩余。模m 的情形可化为模pα的情形，α≥1，p是素数。p=2的情形是容易解决的。设p是一个奇素数，n是模pα的k次剩余的充分必要条件是d=(k，φ(pα))整除indgn，其中g是模pα的一个原根。恰有