第三节 简化剩余系.doc

文档介绍：初等数论第二章同余
第三节简化剩余系
在模m的完全剩余系中,与m互素的整数所成的集合有一些特殊的性质,我们要在这一节中对它们做些研究。
定义1 设R是模m的一个剩余类,若有aÎR,使得(a, m) = 1,则称R是模m的一个简化剩余类。
显然,若R是模的简化剩余类,则R中的每个整数都与m互素。
例如,模4的简化剩余类有两个:
R1(4) = { L, -7 , -3, 1 , 5 , 9 , L },
R3(4) = { L, -5 , -1 , 3 , 7 , 11 , L }。
定义2 对于正整数k,令函数j(k)的值等于模k的所有简化剩余类的个数,称j(k)为Euler函数,或Euler—j函数。
例如,容易验证j(2) = 1,j(3) = 2,j(4) = 2,j(7) = 6。
显然,j(m)就是在m的一个完全剩余系中与m互素的整数的个数。
定义3 对于正整数m,从模m的每个简化剩余类中各取一个数xi,构成一个集合{x1, x2, L,xj(m)},称为模m的一个简化剩余系(或简称为简化系)。
显然,由于选取方式的任意性,模m的简化剩余系有无穷多个。
例如,集合{9, -5, -3, -1}是模8的简化剩余系,集合{1, 3, 5, 7}也是模8的简化剩余系,通常称最小非负简化剩余系。
定理1 整数集合A是模m的简化剩余系的充要条件是
(ⅰ) A中含有j(m)个整数;
(ⅱ) A中的任何两个整数对模m不同余;
(ⅲ) A中的每个整数都与m互素。
证明留作****题。
定理2 设a是整数,(a, m) = 1,B = {x1, x2, L, xj(m)}是模m的简化剩余系,则集合A = {ax1, ax2, L, axj(m)}也是模m的简化剩余系。
证明显然,集合A中有j(m)个整数。其次,由于(a, m) = 1,所以,对于任意的xi(1 £ i £ j(m)),xiÎB,有(axi, m) = (xi, m) = 1。因此,A中的每一个数都与m互素。最后,我们指出,A中的任何两个不同的整数对模m不同余。事实上,若有x ¢, x ¢¢ÎB,使得
a x ¢ º ax ¢¢ (mod m),
那么,因为(a, m) = 1,所以x ¢ º x ¢¢ (mod m),于是x ¢ = x ¢¢。由以上结论及定理1可知集合A是模m的一个简化系。证毕。
注:在定理2的条件下,若b是整数,集合
{ax1 + b, ax2 + b,, L, axj(m) + b}
不一定是模m的简化剩余系。例如,取m = 4,a = 1,b = 1,以及模4的简化剩余系{1, 3}。
定理3 设m1, m2ÎN,(m1, m2) = 1,又设
分别是模m1与m2的简化剩余系,则
A = { m1y + m2x;xÎX,yÎY }
是模m1m2的简化剩余系。
证明由第二节定理3推论可知,若以X ¢与Y ¢分别表示模m1与m2的完全剩余系,使得X Ì X ¢,Y Ì Y ¢,则
A ¢ = { m1y + m2x;xÎX ¢,yÎY ¢ }
是模m1m2的完全剩余系。因此只需证明A ¢中所有与m1m2互素的整数的集合R是集合A。显然,A Í A’。
若m1y + m2xÎR,则(m1y + m2x, m1m2)