第二节 完全剩余系

1、初等数论 第二章 同 余第二节 完全剩余系由带余数除法我们知道，对于给定的正整数m，可以将所有的整数按照被m除的余数分成m类。本节将对此作进一步的研究。一、知识与方法定义1 给定正整数m，对于每个整数i，0 £ i £ m - 1，称集合Ri(m) = n|n º i (mod m)，nÎZ 是模m的一个剩余类。显然，每个整数必定属于且仅属于某一个Ri(m)（0 £ i £ m - 1），而且，属于同一剩余类的任何两个整数对模m是同余的，不同剩余类中的任何两个整数对模m是不同余的。例如，模 5的五个剩余类是R0(5) = L , -1

2、0, -5, 0 , 5, 10, L ，R1(5) = L , -9 , -4 , 1 , 6 , 11, L ，R2(5) = L , -8 , -3 , 2 , 7 , 12, L ，R3(5) = L , -7 , -2 , 3 , 8 , 13, L ，R4(5) = L , -6 , -1 , 4 , 9 , 14, L 。定义2 设m是正整数，从模m的每一个剩余类中任取一个数xi（0 £ i £ m - 1），称集合x0, x1, L,xm - 1是模m的一个完全剩余系（或简称为完全系）。由于xi的选取是任意的，所以模m的完全剩余系有无穷多个，通常称() 0,

3、 1, 2, L, m - 1是模m的最小非负完全剩余系；() 或,是模m的绝对最小完全剩余系。例如，集合0, 6, 7, 13, 24是模5的一个完全剩余系，集合0, 1, 2, 3, 4是模5的最小非负完全剩余系。定理1 整数集合A是模m的完全剩余系的充要条件是() A中含有m个整数；() A中任何两个整数对模m不同余。【证明】定理2 设m ³ 1，a，b是整数，(a, m) = 1，x1, x2, L, xm是模m的一个完全剩余系，则ax1 + b, ax2 + b, L, axm + b也是模m的一个完全剩余系。【证明】 由定理1，只需证明：若xi ¹ xj，则ax

4、i + baxj + b (mod m)。 (1)事实上，若axi + b º axj + b (mod m)，则axi º axj (mod m)，由此及第一节定理5得到xi º xj (mod m)，因此xi = xj。所以式(1)必定成立。证毕。定理3 设m1, m2ÎN，AÎZ，(A, m1) = 1，又设，分别是模m1与模m2的完全剩余系，则R = Ax + m1y；xÎX，yÎY 是模m1m2的一个完全剩余系。【证明】 由定理1只需证明：若x ¢, x ¢¢ÎX，y

5、62;, y ¢¢ÎY，并且Ax ¢ + m1y ¢ º Ax ¢¢ + m1y ¢¢ (mod m1m2)， (2)则 x ¢ = x ¢¢，y ¢ = y ¢¢事实上，由第一节定理5及式(2)，有Ax ¢ º Ax ¢¢ (mod m1) Þ x ¢ º x ¢¢ (mod m1) Þ x ¢ = x ¢¢

6、;，再由式(2)，又推出m1y ¢ º m1y ¢¢ (mod m1m2) Þ y ¢ º y ¢¢ (mod m2) Þ y ¢ = y ¢¢ 。证毕。推论 若m1, m2ÎN，(m1, m2) = 1，则当x1与x2分别通过模m1与模m2的完全剩余系时，m2x1 + m1x2通过模m1m2的完全剩余系。定理4 设miÎN（1 £ i £ n），则当xi通过模mi（1 £ i £ n）的完全剩余系时，x

7、= x1 + m1x2 + m1m2x3 + L + m1m2Lmn - 1xn通过模m1m2Lmn的完全剩余系。【证明】 对n施行归纳法。当n = 2时，由定理3知定理结论成立。假设定理结论当n = k时成立，即当xi（2 £ i £ k + 1）分别通过模mi的完全剩余系时，y = x2 + m2x3 + m2m3x4 + L + m2Lmkxk + 1通过模m2m3Lmk + 1的完全剩余系。由定理3，当x1通过模m1的完全剩余系，xi（2 £ i £ k + 1）通过模mi的完全剩余系时，x1 + m1y = x1 + m1(x2 + m2x3

8、+ L + m2Lmkxk + 1)= x1 + m1x2 + m1m2x3 + L + m1m2Lmkxk + 1通过模m1m2Lmk + 1的完全剩余系。即定理结论对于n = k + 1也成立。定理由归纳法得证。证毕。定理5 设miÎN，AiÎZ（1 £ i £ n），并且满足下面的条件：() (mi, mj) = 1，1 £ i, j £ n，i ¹ j；() (Ai, mi) = 1，1 £ i £ n；() mi½Aj ，1 £ i, j £ n，i ¹

9、j 。则当xi（1 £ i £ n）通过模mi的完全剩余系Xi时，y = A1x1 + A2x2 + L + Anxn通过模m1m2Lmn的完全剩余系。【证明】由定理1只需证明：若xi¢, xi¢¢ÎXi，1 £ i £ n，则由A1x1¢ + A2x2¢ + L + Anxn¢ º A1x1¢¢ + A2x2¢¢ + L + Anxn¢¢ (mod m1Lmn) (3)可以得到xi¢ = xi¢

10、¢，1 £ i £ n。事实上，由条件()及式(3)易得，对于任意的i，1 £ i £ n，有Aixi¢ º Aixi¢¢ (mod mi)。由此并利用条件()和第一节定理5推得xi¢ º xi¢¢ (mod mi)，因此xi¢ = xi¢¢。证毕。二、例题讲解1.设A = x1, x2, L, xm是模m的一个完全剩余系，以x表示x的小数部分 证明：若(a, m) = 1，则【证明】 当x通过模m的完全剩余系时，ax + b也通过模m

11、的完全剩余系，因此对于任意的i（1 £ i £ m），axi + b一定与且只与某个整数j（1 £ j £ m）同余，即存在整数k，使得axi + b = km + j，（1 £ j £ m）从而2.设p ³ 5是素数，aÎ 2, 3, L, p - 2 ，则在数列a，2a，3a，L，(p - 1)a，pa (4) 中有且仅有一个数b，满足b º 1 (mod p) (5) 此外，若b = ka，则k ¹ a，kÎ2, 3, L, p - 2。 【解答】 因为(a, p) = 1，所以

12、由定理2，式(4)中的数构成模p的一个完全剩余系，因此必有数b满足式(5)设b = ka，那么() k ¹ a，否则，b = a2 º 1 (mod p)，即p½(a + 1)(a - 1)，因此p½a - 1或p½a + 1，这与2 £ a £ p - 2矛盾；() k ¹ 1，否则，b = 1×a º 1 (mod p)，这与2 £ a £ p - 2矛盾；() k ¹ -1，否则，b = -a º 1 (mod p)，这与2 £ a

13、63; p - 2矛盾。若又有k ¢，2 £ k ¢ £ p - 2，使得b º k ¢a (mod p)，则k ¢a º ka (mod p) 因(a, p) = 1，所以k º k ¢ (mod p)，从而p½k - k ¢，这是不可能的。这证明了唯一性。3.(Wilson定理) 设p是素数，则(p - 1)! º -1 (mod p)。【解答】 不妨设p5。由例2容易推出对于2, 3, L, p - 2，中的每个整数a，都存在唯一的整数k，2 £ k £ p - 2，使得 ka º 1 (mod p)。 (6)因此，整数2, 3, L, p - 2可以两两配对使得式(6)成立。所以2×3×L×(p - 2) º 1 (mod p)，从而 1×2×3×L×(p - 2)(p - 1) º p - 1 º -1 (mod p)。4. 设m > 0是偶数，a1, a2, L, am与b1, b2, L, bm都是模m的完全剩余系，证明：a1 + b1, a2 + b2