第三节 简化剩余系.doc

初等数论 第二章 同 余第三节 简化剩余系在模m的完全剩余系中，与m互素的整数所成的集合有一些特殊的性质，我们要在这一节中对它们做些研究。定义1 设R是模m的一个剩余类，若有aR，使得(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函数，或Eulerj函数。例如，容易验证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)），xiB，有(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, 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的完全剩余系。因此只需证明A 中所有与m1m2互素的整数的集合R是集合A。显然，A 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互素，所以(m2x + m1y, m1m2) = 1，于是m2x + m1yR。因此A R。综合以上，得到A = R。证毕。定理4 设m, nN，(m, n) = 1，则j(mn) = j(m)j(n)。证明 这是定理3的直接推论。证毕。定理5 设n是正整数，p1, p2, L, pk是它的全部素因数，则j(n) =。证明 设n的标准分解式是n =，由定理4得到j(n) =。 (1)对任意的素数p，j(pa)等于数列1, 2, L, pa中与pa（也就是与p）互素的整数的个数，因此j(pa) = pa -，将上式与式(1)联合，证明了定理。证毕。由定理5可知，j(n) = 1的充要条件是n = 1或2。例1 设整数n 2，证明：nj(n)，即在数列1, 2, L, n中，与n互素的整数之和是nj(n)。解 设在1, 2, L, n中与n互素的j(n)个数是a1, a2, L, aj(n)，(ai, n) = 1，1 ai n - 1，1 i j(n)，则(n - ai, n) = 1，1 n - ai n - 1，1 i j(n)，因此，集合a1, a2, L, aj(n)与集合n - a1, n - a2, L, n - aj(n)是相同的，于是a1 + a2 + L + aj(n) = (n - a1) + (n - a2) + L + (n - aj(n)，2(a1 + a2 + L + aj(n) = nj(n)，因此a1 + a2 + L + aj(n) =nj(n)。例2 设n是正整数，则= n，此处是对n的所有正约数求和。解 将正整数1, 2, L, n按它们与整数n的最大的公约数分类，则n =。例3 设nN，证明：() 若n是奇数，则j(4n) = 2j(n)；() j(n) =的充要条件是n = 2k，kN；() j(n) =的充要条件是n = 2k3l，k, lN；() 若6n，则j(n) ；() 若n - 1与n + 1都是素数，n 4，则j(n) 。解 () 我们有j(4n) = j(22n) = j(22)j(n) = 2j(n)；() 若n = 2k，则j(2k) =，若j(n) =，设n = 2kn1，2n1，则由= j(n) = j(2kn1) = j(2k)j(n1) =2k - 1j(n1) =推出j(n1) = n1，所以n1 = 1，即n = 2k；() 若n = 2k3l，则j(n) = j(2k)j(3l) =。若j(n) =，设n = 2k3ln1，6n1，则由推出j(n1) = n1，所以n1 = 1，即n = 2k3l；() 设n = 2k3ln1，6n1，则j(n) = j(2k)j(3l)j(n1) =；() 因为n 4，所以n - 1与n + 1都是奇素数，所以n是偶数。因为n - 1 3，所以n - 1与n + 1都不等于3，当然不被3整除，所以3n，因此6n。再由上面已经证明的结论()，即可得到结论()。例4 证明：若m, nN，则j(mn) = (m, n)j(m, n)；解 显然mn与m, n有相同的素因数，设它们是pi（1 i k），则由此两式及mn = (m, n)m, n即可得证。习 题 三1. 证明定理1。2. 设m1, m2, L, mn是两两互素的正整数，xi分别通过模mi的简化剩余系（1 i n），m = m1m2Lmn，Mi =，则M1x1 + M2x2 + L + Mnxn通过模m的简化剩余系。3. 设m 1，(a, m) = 1，x1, x2, , xj(m)是模m的