人教版B版高中数学选修4 6(B版)剩余系和欧拉函数课件.ppt

1、剩余系和欧拉函数剩余系和欧拉函数 一、基本概念一、基本概念定义定义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的所有的所有简化剩余类的个数，称简化剩余类的个

2、数，称(k)为为Euler函数。函数。容易验证：容易验证：(2)=1，(3)=2，(4)=2，(7)=6。注：注：(m)就是在就是在m的一个完全剩余系中与的一个完全剩余系中与m互素的互素的 整数的个数，且整数的个数，且 1().mm 定义定义3 对于正整数对于正整数m，从模，从模m的每个简化剩余类中的每个简化剩余类中 各取一个数各取一个数xi，构成一个集合，构成一个集合x1,x2,x(m)，称为模称为模m的一个简化剩余系（或简称为简化系）。的一个简化剩余系（或简称为简化系）。注：由于选取方式的任意性，模注：由于选取方式的任意性，模m的简化剩余系的简化剩余系有无穷多个。有无穷多个。例如，集合例如

3、，集合9,5,3,1是模是模8的简化剩余系；的简化剩余系；集合集合1,3,5,71,3,5,7也是模也是模8 8的简化剩余系的简化剩余系.集合集合1,3,5,71,3,5,7称为最小非负简化剩余系。称为最小非负简化剩余系。二、主要性质二、主要性质 定理定理1 整数集合整数集合A是模是模m的简化剩余系的充要条件是：的简化剩余系的充要条件是：A中含有中含有(m)个整数；个整数；A中的任何两个整数对模中的任何两个整数对模m不同余；不同余；A中的每个整数都与中的每个整数都与m互素。互素。说明：简化剩余系是某个完全剩余系中的部分元素说明：简化剩余系是某个完全剩余系中的部分元素构成的集合，故满足条件构成的

4、集合，故满足条件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中的任何两个不同的整数对模中的任何两个不同的整

5、数对模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)

6、=1，又设，又设1212()12(),mmXx xxYyyy与与分别是模分别是模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的简化剩余系是集合的简化剩余系

7、是集合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。因此。因

8、此A R。从而从而A=R。推论推论 设设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)。注：可以推广到多个两两互质数的情形。注：可以推广到多个两两互质数的情形。定理定理4 设设n是正整数，是正整数，p1,p2,pk是它

9、的全部素因数，是它的全部素因数，|121111()(1)(1)(1)1.()pnknnnpppp 则则证证 设设n的标准分解式是的标准分解式是 1ikiinp 由定理由定理3 3推论得到推论得到 1()()ikiinp 对任意的素数对任意的素数p，(p)等于数列等于数列1,2,p 中与中与p 互素的整数的个数，互素的整数的个数，11()1()pppppppp 因因此此，从而定理得证。从而定理得证。14()1,()THnnpnp 即即为为：为为 的的质质因因数数.注：由定理注：由定理4可知，可知，(n)=1的充要条件是的充要条件是n=1或或2。1kiinp 因因为为111111()111()()

10、()kkkkiiiiiiiinnpppp 考虑有重素因子和没有重素因子的情形。考虑有重素因子和没有重素因子的情形。三、应用举例三、应用举例注意：有重素因子时，上述不等式中等号不成立！注意：有重素因子时，上述不等式中等号不成立！例例1 设整数设整数n 2，证明：，证明：1(,)11().2i ni ninn 即在数列即在数列1,2,n中，与中，与n互素的整数之和是互素的整数之和是 1().2nn 证证 设在设在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

11、)，因此，集合因此，集合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)1().2nn 与集合与集合n a1,n a2,n a(n)是相同的，是相同的，例例2 设设n N，证明：，证明：1)若若n是奇数，则是奇数，则(4n)=2(n)；的充要条件是的充要条件是n=2k，k N；12)()2nn 的充要条件是的充要条件是n=2k3l，k,l N；13)()3nn 4)若若6 n，则，则(n)13n 5)若若n 1与与n 1都是素数，都是素数，n 4，则，则(n)13n 1)若若n

12、是奇数，则是奇数，则(4n)=2(n)；(4n)=(22n)=(22)(n)=2(n)TH414()1,()THnnpnp 为为 的的质质因因数数.的充要条件是的充要条件是n=2k，k N；12)()2nn 若若n=2k，1(2)TH4 212()kk 则则12k 12n 若若(n)=12n设设n=2kn1，12 n n12n 由由 (n)=(2kn1)=(2k)(n1)=2k 1(n1)1111()22knnn 111()2nnn 11()nn 所以所以n1=1，即，即n=2k；的充要条件是的充要条件是n=2k3l，k,l N；13)()3nn 111213 1233()()kln1(),3

13、nn 若若设设 n=2k3ln1，112,3nn n n11()(2 3)3klnnn由由1(2)(3)()kln 11()nn 所以所以n1=1，即，即n=2k3l；若若 n=2k3l，则则 (n)=(2k)(3l)111()3nnn 4)若若6 n，则，则(n)13n 设设 n=2k3ln1，16,n则则 (n)=(2k)(3l)(n1)13n 112 3()3kln 112 33kln 5)若若n 1与与n 1都是素数，都是素数，n 4，则，则(n)13n 因为因为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)13n 例例3 证明：若证明：若m,n N，则，则(mn)=(m,n)(m,n)；证：证：显然显然mn与与m,n有相同的素因数，有相同的素因数，设它们是设它们是pi（1 i k），则），则12111()111()()()kmnmnppp，12111(,),111()()()km nm nppp.由此两式及由此两式及mn=(m,n)m,n即可得证。即可得证。