《数论讲义：4.欧拉定理及应用.docx》由会员分享，可在线阅读，更多相关《数论讲义：4.欧拉定理及应用.docx（12页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、4.欧拉函数与Mobius函数欧拉函数。（九）是一个定义在正整数集上的函数,9（加）的值等于1,2,根-1中与相互素的数的个数.也等 于模2的一个简系的元素个数.1,Mobius 函数()定义为 () = (-1,0,n = l二82.2，素数口 A . n.证明：当 =1时，显然成立.当 1时，设正整数的素因数分解式n = pfp/pf，其中素数pa P2 p，, % 2 1.则(pg = h(1- -)(1-). r(H)= (l + 1)(l + aJ-.(l + a)Pl Pl Ps因为2 P p-, 2s.Yl所以 ()c() -2s=n.6 .证明：对任意的正整数加都有九 dm证明
2、：方法1当 2 = 1时显然成立当相 1时设正整数m的素因数分解式m = p2其中素数pa 2 0.d|m,所以 d = P Pz-aca a? asax a2 4于是 Z9(d) =受(p(p? p牛p。)= . (p(p。)(p(p?)(p(p)dni优= Pz =0 4V =0。、=0 夕2 =0 凤=0axa2%= Xe(P?)Ze(P，),Xe(P?)0i=。Pi =Bs=asas注意到 (P(P?)= X (P, - P ) = P：，.A=A=act2as所以 Z。3) = X 0(P?) 叭p2 叭Pss)= P?珑2 = m.dmS、=002=0Ps=0方法2我们把正整数l,
3、2,.sm.按与m的最大公约数分类.即与m有相同的最大公约数的作为一类.这样,俄的正约数d与这样的分类正整数之间建立了一个一一对应关系.记此=j|（j,也） = d,l首先每一个加的正约数都对应一个其次不同的加的正约数对应不同的所以这些分类Md就是1,2,，加的一个划分.因为（，m） = d,所以/ =须于是（q,） = l .因为相，所以ddmm这样满足上式的q就是模竺的简系，所以q的个数为9（）. dd这就是说满足Md的元素个数为9（）.所以m=Z 吟. ddm d注意到 Z。（）= E9（d） 所以 W（d）= m dm dmdmni d 2 兀 jkt7 .设是正整数,证明： o（）=
4、zn（i-立尸）. j=l dnd k=l2 万力d 2Rki d证明：令3=e.则61 =（/. k=lk=dd 2%/一若（力几）=i，则（j, d）=i，则%。i .于是（邑y = o.从而z?丁二o. k=k=i d 2兀语所以 na-61）=l dn d k=i2一d 2乃W d若则存在d| .使得d|/.于是此时邑=。丁 =1 .所以丁 =Z（%）k =d. k=k=1 d 2町方 n（l-/e ）= 0. dn k=1 d 2 兀 jKi d 2 兀南也就是说若。/）=i时，n（iSe）=i.若。/）i时,n（iEe -）=0 dn d gdn d k=ln1 d2冗沁丁)计算得
5、恰好就是与互素的，的个数.y=l dnd k=l故夕=ZH(i-；2Le d), y=l dn d k=l8.给定整数9,证明：至多存在有限个正整数，同时满足下列条件：(1)5) = ； (2) n |(pn) + a(n).证明：设9() + (7()=碎S N：因为=Z 3)所以 s=2 产 dn dd” d注意到(d) -1,o, 1,所以 4(d) +1 0,1,2.设4 & 4是的所有正约数中满足3)。-1的那些.先证明引理()=0.引理的证明(反证法)假设()。0,即无平方因子.则 =PPzPk，P Pz Pk.于是 0()+ b()= (Pi1)(21)(/ 一1) +(P +1
6、)(2+1).(0+1)= Pl2 /.因为7()=2 =。9,所以女2 4.若是奇数，所以Pi，Pz，Pk都是奇素数，于是 2k | (pl)(P2 T)3 T) + (Pi + 于0 +1)他 + 于从而 2。s, s I 2k.但 S = (1)(1)- -(1) + (1 H)(1 H),(1 H) 1 + ()A 2,矛盾.A Pi Pk Px Pi Pk 3若是偶数，所以Pi =2, P2，,p左都是奇素数,于是 21 | (p1)(P2 -1)(以1) + (Pl + l)(P2 +1)(Pk +1),从而 221 s,s 2 2皿.但 S = (1)(1) H(Id) (Id)
7、2 P2 Pk 2% Pk= - + 2(-/-22522矛盾.于是假设不成立，所以()= 0.由引理知道4 二九回到原题,s = 3)+1 = V必42tL.下面我们证明 (2K=1,2,利 dn d i=i di1i 1,且对 1 J 2,均有dj (2m)2.V(4)+ l4(/) +1 2mM &口 M4)+iS-Y J为正有理数，通分约分后分母至多为4.1，分子至少为1,7=1 dj所以)j=djdd? , dj、从而T 2于是4 2四2 . 4 4 (2机产42、(W-.这就证明了 4 4 (2加)2二i = L 2,m.特别地n = dm (2加产(2afl.这就证明满足要求的至
8、多有有限多个.2 .若（班，机2）= 1，证明：。（叫加2）=。（班）。（根2）3 .设是正整数，证明：V 4（4）=m.证明：9（） = Z3）2 = E4）证明：E（d）= 2（） 宗 dn a dn a4 .已知正整数的素因数分解式 =pf 表p),其中素数P 2 n.5 .证明：对任意的正整数加都有2。（）=帆 dmn1 d 2 -i6 .设是正整数,证明： 。= Zn（l-立e d ）. y=i dn d k=l7 .给定整数9.证明：至多存在有限个正整数，同时满足下列条件：() = ；川奴孔)+。(初高一竞赛数论专题6.欧拉函数与Mobius函数解答欧拉函数（机）是一个定义在正整数
9、集上的函数，9（加）的值等于1,2,，根-1中与相互素的数的个数.也等 于模相的一个简系的元素个数.1, = 1Mobius函数4（）定义为（）= （一1），n= 仍5,素数 P2 1时，设n的素因数分解式几=pf p”.忒:% 1.= 工 (d) = 1 + C； (-1)1 + C；(_l)2 + .+ C(T) = (l-l)s = 0 .结论成立.dnMpiP? 9()= Z1=ZZ()=z (d这 l) = (4(d)l) = Z4(d)/. k=k= d|(女,)d(k,n)k=l dnk= dn a(k,n)=idknn显然以(d)-二 (一).所以得证. dd(3)当 =1时，显然成立.当=Pl2 ,Ps，素数 Pl Pl Ps，E(d) = l, /?()= (I)，)=1 ,所以结论成立. d2n当 =m2q,q为不含平方因数的整数，若d2 n,则dm.则= Z()=仇)=仇结论成立， dr ndm所以Z()d2n.已知正整数n的素因数分解式 =pppf，其中素数pa P2 Ps,a? L证 明： ()(1)(1),(!).P Pl Ps法 1 证明:0()=法 pf P22 )=法 pf )(P(P( ) 夕(P：s )=(pi)a 门(21)M T) = p? P22- pF(1-)(1-)-(1-)P Pl Ps