第二节 完全剩余系 2010.11定义1 给定正整数m，对于每个整数i，0 i m 1， 称集合Ri(m) = n|n i (mod m)，nZ 。 是模m的一个剩余类。 剩余类每个整数属于且仅属于某一个Ri(m)（0 i m 1）， 属于同一剩余类的任何两个整数对模m是同余的， 不同剩余类中的任何两个整数对模m是不同余的。完全剩余系 定义2 设m是正整数，从模m的每一个剩余类中 任取一个数xi（0 i m 1）， 称集合x0, x1, ,xm-1是 模m的一个完全剩余系（或简称为完全系）。 模m的完全剩余系有无穷多个 模m的最小非负完全剩余系 :0, 1, 2, , m 1 模m的绝对最小完全剩余系: 定理1 整数集合A是模m的完全剩余系的充要条件是 () A中含有m个整数；() A中任何两个整数对模m不同余。讨论： 设m 0是整数，a1, a2, , am 与b1, b2, , bm都是模m的完全剩余系， a1b1,a2b2,ambm是不是模m的完全剩余系呢？ 定理2 设m 1，a，b是整数，(a, m) = 1， x1, x2, , xm是模m的一个完全剩余系， 则ax1 b, ax2 b, , axm b也是 模m的一个完全剩余系。 完全剩余系的构造完全剩余系的构造 定理3 设m1, m2N，AZ，(A, m1) = 1，又设 分别是模m1与模m2的完全剩余系，则 R = Ax m1y；xX，yY 是模m1m2的一个完全剩余系。 只需证：若x , x X，y , y Y，且 Ax m1y Ax m1y (mod m1m2)， 则x = x ，y = y 。 推论 若m1, m2N，(m1, m2) = 1， 则当x1与x2分别通过模m1与模m2的完全剩余系时， m2x1 m1x2通过模m1m2的完全剩余系。 定理5 设miN，AiZ（1 i n），且满足下面条件： () (mi, mj) = 1，1 i, j n，i j； () (Ai, mi) = 1，1 i n； () miAj ，1 i, j n，i j 。 则当xi（1 i n）通过模mi的完全剩余系Xi时， y = A1x1 A2x2 Anxn 通过模m1m2mn的完全剩余系。 只需证明：若xi, xiXi，1 i n，则由 A1x1A2x2Anxn A1x1A2x2 Anxn (mod m1mn) 可以得到xi=xi，1 i n。 定理4 设miN（1 i n），则当xi通过模 mi（1 i n）的完全剩余系时， x = x1 m1x2 m1m2x3 m1m2mn-1xn 通过模m1m2mn的完全剩余系。证明 对n施行归纳法。例1 设A = x1, x2, ,xm是模m的一个完全剩余系， 以x表示x的小数部分，证明：若(a, m) = 1，则 关于剩余类的运算 如果将模m（正整数）的剩余类看成一个元 素，剩余类的相等就可以用同余来刻画。 模的剩余类的对同余运算（加法与乘法） 作成一个环，称为剩余类环。 如果模是合数，那么就有不等于零的剩余 类，相乘后为零，即有零因子。 当模m为素数p时，上述的环构成一个域。 它有p个元素，是有限域的一个重要例子。例2 设p 5是素数，a2,3,p2，则在数列 a，2a，3a，(p1)a，pa 中有且仅有一个数b，满足b 1 (mod p)。 此外，若b=ka，则k a，k2,3, ,p2。 例3(Wilson定理) 设p是素数，则(p 1)! 1 (mod p)。