简化剩余系与欧拉函数

1、3.3 简化剩余系与欧拉函数,一、基本概念,定义1 设R是模m的一个剩余类，若有aR，使得(a, m),= 1，则称R是模m的一个简化剩余类。,即与模m互质的剩余类。,注：若R是模的简化剩余类，则R中的数都与m互素。,例如，模4的简化剩余类有两个：,R1(4) = , 7 , 3, 1 , 5 , 9 , ，,R3(4) = , 5 , 1 , 3 , 7 , 11 , 。,定义2 对于正整数k，令函数(k)的值等于模k的所有,简化剩余类的个数，称(k)为Euler函数。,容易验证：(2) = 1，(3) = 2，(4) = 2，(7) = 6。,注：(m)就是在m的一个完全剩余系中与m互素的

2、,整数的个数，且,定义3 对于正整数m，从模m的每个简化剩余类中,各取一个数xi，构成一个集合x1, x2, ,x(m)，,称为模m的一个简化剩余系（或简称为简化系）。,注：由于选取方式的任意性，模m的简化剩余系,有无穷多个。,例如，集合9, 5, 3, 1是模8的简化剩余系；,集合1, 3, 5, 7也是模8的简化剩余系.,集合1, 3, 5, 7称为最小非负简化剩余系。,二、主要性质,定理1 整数集合A是模m的简化剩余系的充要条件是：, A中含有(m)个整数；, A中的任何两个整数对模m不同余；, A中的每个整数都与m互素。,说明：简化剩余系是某个完全剩余系中的部分元素,构成的集合，故满足

3、条件2；,由定义1易知满足条件3；,由定义3易知满足条件1。,定理2 设a是整数，(a, m) = 1，B = x1, x2, , x(m),是模m的简化剩余系，则集合,A = ax1, ax2, , ax(m),也是模m的简化剩余系。,证明 显然，集合A中有(m)个整数。,由于(a, m) = 1，,对于任意的xi（1 i (m)），xiB，,有(axi, m) = (xi, m) = 1。,故A中的每一个数都与m互素。,而且，A中的任何两个不同的整数对模m不同余。,因为，若有x , x B，使得 a x ax (mod m)，,那么， x x (mod m)，,于是x = x 。,由以上结

4、论及定理1可知集合A是模m的一个简化系。,注：在定理2的条件下，若b是整数，集合,ax1 b, ax2 b, , ax(m) b,不一定是模m的简化剩余系。,例如，取m = 4，a = 1，b = 1，,以及模4的简化剩余系1, 3。,但2，4不是模4的简化剩余系。,定理3 设m1, m2N，(m1, m2) = 1，又设,分别是模m1与m2的简化剩余系，,则 A = m1y m2x；xX，yY ,是模m1m2的简化剩余系。,证明 由第二节定理3推论可知，,若以X 与Y 分别表示,模m1与m2的完全剩余系，使得X X ，Y Y ，,则A = m1y m2x；xX ，yY 是模m1m2的完全 剩

5、余系。,因此只需证明A 中所有与m1m2互素的整数的集合R,即模m1m2的简化剩余系是集合A。,若m1y m2xR，则(m1y m2x, m1m2) = 1，,所以(m1y m2x, m1) = 1，,于是 (m2x, m1) = 1，(x, m1) = 1，xX。,同理可得到yY，因此m1y m2xA。,这说明R A。,另一方面，若m1y m2xA，则xX，yY，,即 (x, m1) = 1，(y, m2) = 1。,由此及(m1, m2) = 1得到,(m2x m1y, m1) = (m2x, m1) = 1,(m2x m1y, m2) = (m1y, m2) = 1。,因为m1与m2互素

6、，所以(m2x m1y, m1m2) = 1，,于是m2x m1yR。因此A R。,从而A = R。,推论 设m, nN，(m, n) = 1，则(mn) = (m)(n)。,证 由定理3知，若x,y分别通过m , n的简化剩余系，,则my nx通过mn的简化剩余系，,即有 my nx通过(mn)个整数。,另一方面，xnx通过(m)个整数，,ymy通过(n)个整数,从而my nx通过(m) (n)个整数。,故有 (mn) = (m)(n)。,注：可以推广到多个两两互质数的情形。,定理4 设n是正整数，p1, p2, , pk是它的全部素因数，,证 设n的标准分解式是,由定理3推论得到,对任意的

7、素数p，,(p)等于数列1, 2, , p中与p互素的整数的个数，,从而定理得证。,注：由定理4可知，(n) = 1的充要条件是n = 1或2。,考虑有重素因子和没有重素因子的情形。,三、应用举例,注意：有重素因子时，上述不等式中等号不成立！,例1 设整数n 2，证明：,即在数列1, 2, , n中，与n互素的整数之和是,证 设在1, 2, , n中与n互素的个数是(n)，,a1, a2, , a(n)，(ai, n) = 1，1 ai n 1，1 i (n)，,则 (n ai, n) = 1，1 n ai n 1，1 i (n)，,因此，集合a1, a2, , a(n),故 a1 a2 a(

8、n) = (n a1) (n a2) (n a(n)，,从而，2(a1 a2 a(n) = n(n)，,因此 a1 a2 a(n),与集合n a1, n a2, , n a(n)是相同的，,例2 设nN，证明：,1) 若n是奇数，则(4n) = 2(n)；,的充要条件是n = 2k，kN；,的充要条件是n = 2k3l，k, lN；,4) 若6n，则(n),5) 若n 1与n 1都是素数，n 4，则(n),1) 若n是奇数，则(4n) = 2(n)；,(4n) = (22n),= (22)(n),= 2(n)TH4,的充要条件是n = 2k，kN；,若n = 2k，,若(n) =,设n = 2kn1，,由 (n) = (2kn1) = (2k)(n1),=2k 1(n1),所以n1 = 1，即n = 2k；,的充要条件是n = 2k3l，k, lN；,设 n = 2k3ln1，,所以n1 = 1，即n = 2k3l；,若 n = 2k3l，,则 (n) = (2k)(3l),4) 若6n，则(n),设 n = 2k3ln1，,则 (n) = (2k)(3l)(n1),5) 若n 1与n 1都是素数，n 4，则(n),因为n 4，且n 1与n 1都是奇素数，,所以n是偶数，且n 1 3.,所以n 1与n 1都不等于3，,所以3