人教版B版高中数学选修4-6(B版)剩余系和欧拉函数课件.ppt
20页
剩余系剩余系和和欧拉函数欧拉函数 一、基本概念一、基本概念定定义义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 , } 定定义义2 对对于正整数于正整数k，令函数，令函数 (k)的的值值等于模等于模k的所有的所有简简化剩余化剩余类类的个数，称的个数，称 (k)为为Euler函数容易容易验证验证：： (2) = 1，， (3) = 2，， (4) = 2，， (7) = 6注：注： (m)就是在就是在m的一个完全剩余系中与的一个完全剩余系中与m互素的互素的 整数的个数，且整数的个数，且 定定义义3 对对于正整数于正整数m，从模，从模m的每个的每个简简化剩余化剩余类类中中 各取一个数各取一个数xi，构成一个集合，构成一个集合{x1, x2, ,x (m)}，， 称称为为模模m的一个的一个简简化剩余系（或化剩余系（或简简称称为简为简化系）。
化系） 注：由于注：由于选选取方式的任意性，模取方式的任意性，模m的的简简化剩余系化剩余系有无穷多个有无穷多个例如，集合例如，集合{9, 5, 3, 1}是模是模8的的简简化剩余系；化剩余系； 集合集合{1, 3, 5, 7}{1, 3, 5, 7}也是模也是模8 8的简化剩余系的简化剩余系. . 集合集合{1, 3, 5, 7}{1, 3, 5, 7}称为最小非负简化剩余系称为最小非负简化剩余系 二、主要性质二、主要性质 定理定理1 整数集合整数集合A是模是模m的的简简化剩余系的充要条件是：化剩余系的充要条件是：①① A中含有中含有 (m)个整数；个整数；②② A中的任何两个整数中的任何两个整数对对模模m不同余；不同余；③③ A中的每个整数都与中的每个整数都与m互素说明：简化剩余系是某个完全剩余系中的部分元素说明：简化剩余系是某个完全剩余系中的部分元素构成的集合，故构成的集合，故满满足条件足条件2；； 由定由定义义1易知易知满满足条件足条件3；；由定义由定义3 3易知满足条件易知满足条件1 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)）），，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可知集合可知集合A是模是模m的一个的一个简简化系 注：在定理注：在定理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的简化剩余系的简化剩余系 定理定理3 设设m1, m2 N，，(m1, m2) = 1，又，又设设分分别别是模是模m1与与m2的的简简化剩余系，化剩余系， 则则 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 若若m1y m2x R，，则则(m1y m2x, 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，， 于是于是m2x m1y R因此A R 从而从而A = R 推推论论 设设m, n N，，(m, n) = 1，，则则 (mn) = (m) (n)证证 由定理由定理3知，若知，若x,y分分别别通通过过m , n的的简简化剩余系，化剩余系， 则则my nx通通过过mn的的简简化剩余系，化剩余系， 即有即有 my nx通通过过 (mn)个整数 另一方面，另一方面，x〔〔nx〕〕通通过过 (m)个整数，个整数， y〔〔my〕〕通通过过 (n)个整数个整数, 从而从而my nx通通过过 (m) (n)个整数。
个整数故有故有 (mn) = (m) (n)注：可以推广到多个两两互质数的情形注：可以推广到多个两两互质数的情形 定理定理4 设设n是正整数，是正整数，p1, p2, , pk是它的全部素因数，是它的全部素因数， 证证 设设n的的标标准分解式是准分解式是 由定理由定理3 3推论得到推论得到 对对任意的素数任意的素数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 (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 设设n N，，证证明：明：1) 若若n是奇数，是奇数，则则 (4n) = 2 (n)；；的充要条件是的充要条件是n = 2k，，k N；；的充要条件是的充要条件是n = 2k3l，，k, l N；；4) 若若6 n，，则则 (n) 5) 若若n 1与与n 1都是素数，都是素数，n > 4，，则则 (n) 1) 若若n是奇数，是奇数，则则 (4n) = 2 (n)；； (4n) = (22n)= (22) (n)= 2 (n)〔〔TH4〕〕 的充要条件是的充要条件是n = 2k，，k N；；若若n = 2k，， 若若 (n) = 设设n = 2kn1，， 由由 (n) = (2kn1) = (2k) (n1) =2k 1 (n1) 所以所以n1 = 1，即，即n = 2k；； 的充要条件是的充要条件是n = 2k3l，，k, l N；；设设 n = 2k3ln1，， 所以所以n1 = 1，即，即n = 2k3l；；若若 n = 2k3l，，则则 (n) = (2k) (3l) 4) 若若6 n，，则则 (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 n，，由由结论结论4，，也不能被也不能被3 3整除，整除，因此因此6 n。
即可得到结论即可得到结论5 5若若6 n，，则则 (n) 例例3 证证明：若明：若m, n N，，则则 (mn) = (m, n) ([m, n])；；证证：： 显显然然mn与与[m, n]有相同的素因数，有相同的素因数， 设设它它们们是是pi（（1 i k），），则则由此两式及由此两式及mn = (m, n)[m, n]即可得即可得证证。
