简化剩余系与欧拉函数

1、2021/6/161 3.3 3.3 简化剩余系与欧拉函数简化剩余系与欧拉函数 一、基本概念一、基本概念 定义定义1 设设R是模是模m的一个剩余类，若有的一个剩余类，若有a R，使得，使得(a, m) = 1，则称，则称R是模是模m的一个简化剩余类的一个简化剩余类。 即与模即与模m互质的剩余类。互质的剩余类。 注：若注：若R是模的简化剩余类，则是模的简化剩余类，则R中的数都与中的数都与m互素。互素。 例如，模例如，模4的简化剩余类有两个：的简化剩余类有两个： R1(4) = , 7 , 3, 1 , 5 , 9 , ， R3(4) = , 5 , 1 , 3 , 7 , 11 , 。 2021

2、/6/162 定义定义2 对于正整数对于正整数k，令函数，令函数 (k)的值等于模的值等于模k的所有的所有 简化剩余类的个数，称简化剩余类的个数，称 (k)为为Euler函数。函数。 容易验证：容易验证： (2) = 1， (3) = 2， (4) = 2， (7) = 6。 注：注： (m)就是在就是在m的一个完全剩余系中与的一个完全剩余系中与m互素的互素的 整数的个数，且整数的个数，且 1().mm 定义定义3 对于正整数对于正整数m，从模，从模m的每个简化剩余类中的每个简化剩余类中 各取一个数各取一个数xi，构成一个集合，构成一个集合x1, x2, ,x (m)， ， 称为模称为模m的一

3、个简化剩余系（或简称为简化系）。的一个简化剩余系（或简称为简化系）。 2021/6/163 注：由于选取方式的任意性，模注：由于选取方式的任意性，模m的简化剩余系的简化剩余系 有无穷多个。有无穷多个。 例如，集合例如，集合9, 5, 3, 1是模是模8的简化剩余系；的简化剩余系； 集合集合1, 3, 5, 71, 3, 5, 7也是模也是模8 8的简化剩余系的简化剩余系. . 集合集合1, 3, 5, 71, 3, 5, 7称为最小非负简化剩余系。称为最小非负简化剩余系。 2021/6/164 二、主要性质二、主要性质 定理定理1 整数集合整数集合A是模是模m的简化剩余系的充要条件是：的简化剩

4、余系的充要条件是： A中含有中含有 (m)个整数；个整数； A中的任何两个整数对模中的任何两个整数对模m不同余；不同余； A中的每个整数都与中的每个整数都与m互素。互素。 说明：简化剩余系是某个完全剩余系中的部分元素说明：简化剩余系是某个完全剩余系中的部分元素 构成的集合，故满足条件构成的集合，故满足条件2； 由定义由定义1易知满足条件易知满足条件3； 由定义由定义3 3易知满足条件易知满足条件1 1。 2021/6/165 定理定理2 设设a是整数，是整数，(a, m) = 1，B = x1, x2, , x (m) 是模是模m的简化剩余系，则集合的简化剩余系，则集合 A = ax1, ax

5、2, , ax (m) 也是模也是模m的简化剩余系。的简化剩余系。 证明证明 显然，集合显然，集合A中有中有 (m)个整数。个整数。 由于由于(a, m) = 1， 对于任意的对于任意的xi（1 i (m)），xi B， 有有(axi, m) = (xi, m) = 1。 故故A中的每一个数都与中的每一个数都与m互素。互素。 而且，而且，A中的任何两个不同的整数对模中的任何两个不同的整数对模m不同余。不同余。 因为，若有因为，若有x , x B，使得，使得 a x ax (mod m)， 那么，那么， x x (mod m)， 于是于是x = x 。 由以上结论及定理由以上结论及定理1可知集合

6、可知集合A是模是模m的一个简化系。的一个简化系。 2021/6/166 注：在定理注：在定理2的条件下，若的条件下，若b是整数，集合是整数，集合 ax1 b, ax2 b, , ax (m) b 不一定是模不一定是模m的简化剩余系。的简化剩余系。 例如，取例如，取m = 4，a = 1，b = 1， 以及模以及模4的简化剩余系的简化剩余系1, 3。 但但2 2，4 4不是模不是模4 4的简化剩余系。的简化剩余系。 2021/6/167 定理定理3 设设m1, m2 N，(m1, m2) = 1，又设，又设 12 12()12() , mm XxxxYyyy 与与 分别是模分别是模m1与与m2的

7、简化剩余系，的简化剩余系， 则则 A = m1y m2x；x X，y Y 是模是模m1m2的简化剩余系。的简化剩余系。 证明证明 由第二节定理由第二节定理3 3推论可知，推论可知， 若以若以X 与与Y 分别表示分别表示 模模m1与与m2的完全剩余系，使得的完全剩余系，使得X X ，Y Y ， 则则A = m1y m2x；x X ，y Y 是模是模m1m2的完全的完全 剩余系。剩余系。 因此只需证明因此只需证明A 中所有与中所有与m1m2互素的整数的集合互素的整数的集合R 即模即模m1m2的简化剩余系是集合的简化剩余系是集合A。 2021/6/168 若若m1y m2x R，则，则(m1y m2

8、x, m1m2) = 1， 所以所以(m1y m2x, m1) = 1， 于是于是 (m2x, m1) = 1，(x, m1) = 1，x X。 同理可得到同理可得到y Y，因此，因此m1y m2x A。 这说明这说明R A。 另一方面，若另一方面，若m1y m2x A，则，则x X，y Y， 即即 (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，

9、于是于是m2x m1y R。因此。因此A R。 从而从而A = R。 2021/6/169 推论推论 设设m, n N，(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)。 注：可以推广

10、到多个两两互质数的情形。注：可以推广到多个两两互质数的情形。 2021/6/1610 定理定理4 设设n是正整数，是正整数，p1, p2, , pk是它的全部素因数，是它的全部素因数， | 12 1111 ( )(1)(1)(1)1.() pn k nnn pppp 则则 证证 设设n的标准分解式是的标准分解式是 1 i k i i np 由定理由定理3 3推论得到推论得到 1 ( )() i k i i np 对任意的素数对任意的素数p， (p )等于数列等于数列1, 2, , p 中与中与p 互素的整数的个数，互素的整数的个数， 1 1 ()1() p ppppp pp 因因此此， 从而定

11、理得证。从而定理得证。 1 4( )1,()THnnpn p 即即为为：为为 的的质质因因数数. . 2021/6/1611 注：由定理注：由定理4可知，可知， (n) = 1的充要条件是的充要条件是n = 1或或2。 1 k i i np 因因为为 1111 11 ( )111()()() kkkk ii iiii ii nnpp pp 考虑有重素因子和没有重素因子的情形。考虑有重素因子和没有重素因子的情形。 三、应用举例三、应用举例 注意：有重素因子时，上述不等式中等号不成立！注意：有重素因子时，上述不等式中等号不成立！ 2021/6/1612 例例1 设整数设整数n 2，证明：，证明：

12、1 ( , ) 1 1 ( ). 2 i n i n inn 即在数列即在数列1, 2, , n中，与中，与n互素的整数之和是互素的整数之和是 1 ( ). 2 nn 证证 设在设在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 (n) = (n a1) (n a2) (n a (n)， ， 从而，从而，2(a1 a2 a (n) = n (

13、n)， 因此因此 a1 a2 a (n) 1 ( ). 2 nn 与集合与集合n a1, n a2, , n a (n)是相同的，是相同的， 2021/6/1613 例例2 设设n N，证明：，证明： 1) 若若n是奇数，则是奇数，则 (4n) = 2 (n)； 的充要条件是的充要条件是n = 2k，k N； 1 2) ( ) 2 nn 的充要条件是的充要条件是n = 2k3l，k, l N； 1 3) ( ) 3 nn 4) 若若6 n，则，则 (n) 1 3 n 5) 若若n 1与与n 1都是素数，都是素数，n 4，则，则 (n) 1 3 n 2021/6/1614 1) 若若n是奇数，则

14、是奇数，则 (4n) = 2 (n)； (4n) = (22n) = (22) (n) = 2 (n)TH4 1 4( )1,()THnnpn p 为为 的的质质因因数数. . 2021/6/1615 的充要条件是的充要条件是n = 2k，k N； 1 2) ( ) 2 nn 若若n = 2k， 1 (2 ) TH4 21 2 () kk 则则 1 2k 1 2 n 若若 (n) = 1 2 n设设n = 2kn1， 1 2 n n 1 2 n 由由 (n) = (2kn1) = (2k) (n1 ) =2 k 1 (n1) 1 1 1 1() 2 2 k n n n 1 1 1() 2 n

15、n n 11 ()nn 所以所以n1 = 1，即，即n = 2k； 2021/6/1616 的充要条件是的充要条件是n = 2k3l，k, l N； 1 3) ( ) 3 nn 111 213 1 233 () () kl n 1 ( ), 3 nn 若若 设设 n = 2k3ln1， 11 2,3nn n n 1 1 ( )(2 3) 3 kl nnn由由 1 (2 ) (3 ) () kl n 11 ()nn 所以所以n1 = 1，即，即n = 2k3l； 若若 n = 2k3l， 则则 (n) = (2k) (3l) 1 1 1() 3 n n n 2021/6/1617 4) 若若6

16、n，则，则 (n) 1 3 n 设设 n = 2k3ln1， 1 6,n 则则 (n) = (2k) (3l) (n1) 1 3 n 1 1 2 3() 3 kl n 1 1 2 3 3 kl n 2021/6/1618 5) 若若n 1与与n 1都是素数，都是素数，n 4，则，则 (n) 1 3 n 因为因为n 4，且，且n 1与与n 1都是奇素数，都是奇素数， 所以所以n是偶数，且是偶数，且n 1 3. 所以所以n 1与与n 1都不等于都不等于3， 所以所以3 n， 由结论由结论4， 也不能被也不能被3 3整除，整除， 因此因此6 n。 即可得到结论即可得到结论5 5。 若若6 n，则，则 (n) 1 3 n