第二节--完全剩余系

初等数论 第二章 同 余第二节 完全剩余系由带余数除法我们知道，对于给定的正整数 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) = {  , 10, 5, 0 , 5, 10,  }，R1(5) = {  , 9 , 4 , 1 , 6 , 11,  }，R2(5) = {  , 8 , 3 , 2 , 7 , 12,  }，R3(5) = {  , 7 , 2 , 3 , 8 , 13,  }，R4(5) = {  , 6 , 1 , 4 , 9 , 14,  }。定义 2 设 m 是正整数，从模 m 的每一个剩余类中任取一个数 xi（0  i  m  1），称集合{x0, x1, ,xm  1}是模 m 的一个完全剩余系（或简称为完全系）。由于 xi的选取是任意的，所以模 m 的完全剩余系有无穷多个，通常称(ⅰ) {0, 1, 2, , 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, , xm}是模 m 的一个完全剩余系，则{ax1  b, ax2  b, , axm  b}也是模 m 的一个完全剩余系。【证明】 由定理 1，只需证明：若 xi  xj，则 axi  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 只需证明：若...