关于二次剩余介绍

[拼音]：erci shengyu

[外文]：quadratic residue

研究一般的二次同余式αx2+bx+с呏0(modm)，可归结为讨论形如的同余式，其中m>1，(m，n)=1。若它有解，则n叫作模m 的二次剩余；若它无解，则n叫作模m 的二次非剩余。设p 是一个奇素数，在模p的缩系中有个二次剩余和个二次非剩余，且12，22，…，就是模p的全部二次剩余。如果n是模p的二次剩余，则，如果n是模p的二次非剩余，则

设pn，当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>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α的一个原根。恰有个模pα互不同余的k次剩余。当d=k时，模pα的k次剩余叫做真k次剩余；当d<k时，模pα的k次剩余叫做非真k次剩余。可以证明，非真k次剩余可以归结为真k次剩余来研究，而模pα的真k次剩余，又可归结为模p的真k次剩余来研究。因此，对于k次剩余，总可假定。设k>1，p是一个奇素数，p-1=kq，定义符号，其中nq(modp)表示nq模p的绝对值最小的剩余，符号叫做模p的k次剩余特征。容易证明:n是模p的k次剩余当且仅当。设，此时，n是模p的2k次非剩余当且仅当。1801年，高斯证明了以下结果:设p呏1(mod8)，p =α2+4b2，则的充分必要条件是b呏0(mod4)。高斯关于二次互反律和四次剩余的深入研究，对以后数论的发展，产生了很大的影响。代数数域中的高次互反律，即希尔伯特第9问题，从F.G.M.艾森斯坦、D.希尔伯特到高木贞治、E.阿廷，才最后得到解决。一个著名的经典结果是：设p呏1(mod6)，的充分必要条件是p =α2+27b2，α、b是整数。对于给定的不太大的n和k，的充分必要条件是p具有什么形状，近年来一直有不少工作。1969年，K.伯德证明了：设p =α2+b2，q=X2+d 2，α呏с呏1(mod2)，b呏d呏0(mod 2)，αb>0，сd>0，p 和q是素数且，则。

参考书目

1. K.Ireland and M.Rosen，A Classical Introduction to Modern Number Theory，Springer-Verlag. New York，1982.