1,aa2,…, 模m两两互不同余,且由(a,m)=(an,m)=1得(aa,m)=1, 从而组成模m的一个简化剩余系 定理2表明:只要(a,m)=1,我们就可以找到这样的模m的 完全剩余系和简化剩余系,它们的元素都是a的倍数;而当 (a,m)>1时,这是一定不可能的。如:5·0.5·1,…,5·7是模 8的完全剩余系,5·1,5·3,5·5,5:7是模8的简化剩余系。但 是2·0,2·1…,2·7不是模8的完全剩余系 2·1,2·3,2·5,2·7也不是模8的简化剩余系 对于不同模之间的剩余系,我们有如下结论: 定理3设m,H是两个互素的正整数,如果x,y分别遍历模 m,n的完全(简化)剩余系,则nx+my遍历模m的完全(简 化)剩余系。 证对于完全剩余系,若x1,x2…x和yy2…y分别是 模m和n的一组完全剩余系,则集合 {nx+my,i=1,2,…,m,yj=1,2,…,n}一共有mm个元素, 所以只需证明它们关于模mm两两互不同余即可。反证法, 若存在整数x,x,和y,y满足 nx,+my,= nx, +my, (mod mn) 则由上一节性质2(7)有 nx+my,≡nx,+my(modm) 和1 2 ( ) , , , aa aa aa m 模 m 两两互不同余,且由 (a,m) = (ai ,m) =1 得 (aai ,m) =1, 从而组成模 m 的一个简化剩余系。 定理 2 表明:只要 (a,m) =1 ,我们就可以找到这样的模 m 的 完全剩余系和简化剩余系,它们的元素都是 a 的倍数;而当 (a,m) 1 时,这是一定不可能的。如: 50,51, ,57 是模 8 的完全剩余系, 51,53,55,5 7 是模 8 的简化剩余系。但 是 20,21, ,27 不 是 模 8 的 完 全 剩 余 系 , 21,23,25,2 7 也不是模 8 的简化剩余系。 对于不同模之间的剩余系,我们有如下结论: 定理 3 设 m,n 是两个互素的正整数,如果 x, y 分别遍历模 m,n 的完全(简化)剩余系,则 nx + my 遍历模 mn 的完全(简 化)剩余系。 证 对于完全剩余系,若 m x , x , , x 1 2 和 n y , y , , y 1 2 分别是 模 m和n 的一组完全剩余系,则集 合 {nx my | i 1,2, ,m, j 1,2, ,n} i + j = = 一共有 mn 个元素, 所以只需证明它们关于模 mn 两两互不同余即可。反证法, 若存在整数 i j x , x 和 k l y , y 满足 nx my nx my (mod mn) i + k j + l , 则由上一节性质 2(7)有 nx my nx my (mod m) i + k j + l 和