关于同余介绍

[拼音]：tongyu

[外文]：congruence

数论中的重要概念。给定一个正整数m，如果二整数α、b)满足m│α-b)(α-b)被m整除)，就称整数α、b)对模m同余，记作α呏b)(mod m)。对模m同余是整数的一个等价关系。利用同余的定义可得以下基本性质：

（1）若α1呏b)1(mod m)，α2呏b)2(mod m)，则α1±α2呏b)1±b)2(mod m)，α1α2呏b)1b)2(mod m)。

（2）若αс呏b)с(mod m)，则。

余数相同的整数集合，就叫做剩余类。确切地说，若m是一个给定的正整数，则全体整数可以分成m个集，记作C0，C1，…，Cm-1，其中Cr(r=0，1，…，m-1)是由一切形如qm＋r(q=0，±1，±2，…)的整数所组成的集。这些集合具有性质：

（1）每一个整数必包含在而且仅包含在上述一个集合里。

（2）两个整数同在一个集合的充分必要条件是它们对模m同余。这样的m个集C0，C1，…，Cm-1叫做模m的剩余类。由此可引出抽象代数中重要的概念，如群论中的陪集，环论中的剩余类等。任取，这m 个数α0，α1，…，αm-1称为模m的一个完全剩余系。最常用的完全剩余系是0，1，…， m-1。如果(k，m)＝1，l是任给的整数，α0，α1，…，αm-1是模m 的一个完全剩余系，那么，kα0+l，kα1+l，…，kαm-1+l也是模m的一个完全剩余系。但是，当m呏0(mod2)时，如果α0，α1，…，αm-1和 b)0，b)1，…，b)m-1分别是模m的一个完全剩余系，那么α0+b)0，α1+b)1，…，αm-1+b)m-1就不是模m 的一个完全剩余系。1948年，S.乔拉等人证明了:设m>2，如果α0，α1，…，αm-1和b)0，b)1，…， b)m-1分别是模m 的一个完全剩余系， 那么α0b)0，α1b)1，…，αm-1b)m-1不是模m 的一个完全剩余系。

1640年，P.de费马宣布他证明了：如果p是一个素数，x是一个整数，满足p凲x，则p｜xp-1-1。这个重要的定理叫做费马小定理。1736年，L.欧拉首先给出了这一定理的证明。1760年，他又作了重要推广:若m是一个正整数，对于每一个满足(x，m)=1的整数x，则有，这就是欧拉定理。其中φ(m)叫做欧拉函数，它表示0，1，…，m-1中与m互素的数的个数。在C0，C1，…，Cm-1中， 恰有φ(m)个类，其中每一个数都和m互素，在这φ(m)个类中各取一数，得到φ(m)个数，叫做模m的一个缩系。运用缩系的性质，很容易证明欧拉定理。设 是模m的一个缩系，(x，m)=1，那么也是模m的一个缩系，于是，即得出欧拉定理。当m是素数时，就得到费马小定理。设m的标准分解式为，利用缩系的性质可证

。

同余式的求解中，一次同余式是最基本的。设整系数n次(n>0)多项式ƒ(x)=αnxn+…+α1x+α0，m是一个正整数且不能整除αn，则

(1)

叫做模m 的n 次同余式。如果整数 α是（1）的解且α呏α┡(mod m)，那么α┡也是(1)的解，因此，(1)的不同解是指满足(1)的模 m互不同余的数。对于一次同余式 αx呏b)(mod m)有解的充分必要条件是(α，m)│b)，若有解则有(α，m)个解。一次同余式组是指

。 (2)

在中国古代《孙子算经》中，对某些具体的一次同余式组已有解法，把这一解法加以推广，就是著名的孙子剩余定理：设m1， m2，…， mk是k个两两互素的正整数

，

则同余式组(2)的解是

，

式中。孙子剩余定理又被称之为中国剩余定理，是数论中一个重要的定理，除了数论本身，数学的许多其他分支以及一些应用学科都要用到它。例如，设m＝m1m2…mk，m1， m2，…，mk两两互素，利用孙子剩余定理可将同余式(1)的求解问题化为同余式组ƒ(x)呏0(mod mi)(i＝1，2，…，k)的求解问题，于是就只需要研究(1)中m是素数方幂的情形了。又如，可将0≤x<m中的一切整数x，用表示，这叫做模系数记数法，这里m＝m1m2…mk，m1，m2，…，mk两两互素，而表示x模mi的最小非负剩余。

如果已知x的模系数记数法，就可用孙子定理找出x。这个记数法的优点是加法和乘法无须进位，它在计算机方面有应用。

关于素数为模的同余式，1770年，J.-L.拉格朗日证明了如下定理：设p是素数，那么模 p的n次同余式的解数不大于 n（重解也计算在内）。人们称之为拉格朗日定理。由此立即可以得威尔森定理：如果 p是素数，那么(p-1)!+1呏0(mod p)。因为xp-1-1呏0(mod p)有p-1个解1，…，p-1，故由拉格朗日定理可得

xp-1-1呏(x-1)(x-2)…(x-(p-1))(mod p)，

将x=0代入上式得-1呏(-1)p(p-1)!(mod p)，这就证明了威尔森定理。威尔森定理的逆定理也是成立的，可用反证法简单证出。用拉格朗日定理还可证明：当p≥5是一个素数时，则有。这个定理是1862年，由J.沃斯顿霍姆证明的。

设ƒ(x1，x2，…，xn)是n元整系数多项式，p是一个奇素数，对于同余式ƒ(x1，x2，…，xn) 呏0(mod p)的解(x1，x2，…，xn)(0≤xj<p，j=1，2，…，n)的个数N 的研究，是数论的重要课题之一。

早在1801年，C.F.高斯就研究了同余式αx3-b)y3呏1(mod p)的解的个数，这里p呏1(mod 3)和同余式αx4-b)y4呏1(mod p)的解的个数，这里p呏1(mod 4)。

设ƒ(x)模 p无重因式，1924年，E.阿廷猜想同余式y2呏ƒ(x)(mod p)，在ƒ(x)的次数为3和4时，N 分别满足和，1936年，H.哈塞证明了这一猜想，并且还证明了对于一般含q个元的有限域，把以上两式中p换成q，也是对的。1948年，韦伊对于一般的ƒ(x，y)=0在有限域上得到类似的结果， 他猜想对于ƒ(x1，x2，…，xn)=0也有类似的结果。1973年，P.德利涅证明了韦伊猜想。他的杰出工作获得了1978年的国际数学家会议的费尔兹奖。

参考书目

1. W.M.Schmidt，Equations over Finite Fields: an Elementary Approach， Lecture Notes in Math.536，Springer-Verlag， New York， 1976.