数论讲义：4.欧拉定理及应用.docx
4.欧拉函数与Mobius函数欧拉函数。（九）是一个定义在正整数集上的函数,9（加）的值等于1,2,根-1中与相互素的数的个数.也等 于模2的一个简系的元素个数.1,Mobius 函数()定义为 () = < (-1,0,n = l二82.2，素数口 <A <.<亿其他即有大于 1的平方因数1 若（肛，加2 ） = L王跑遍模叫的简系，马跑遍模加2的简系.证明：加2% +犯跑遍模町加2的简系.=M(1)(1)(1).Pl Pl Ps法 2(p(n) = £4d J = ny- = n £ y- = n(+-)dn ddip?”覆成，U dlpiPz Ps dk=l PiPi?Pik=(1)(1)(1)Pl Pl Ps5,设武)表示正整数的所有正因数的个数,9(0表示模的一个简系的元素个数证明：(p(n)r(n) > 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-, < < ps，所以 9() "(1)(1),(!) N "(1 )(1 ),(1)=Pi 0 Ps 2222工(几)=(1 +)(1 +)(1 + as) > 2s.Yl所以 °()c()> -2s=n.6 .证明：对任意的正整数加都有九 dm证明：方法1当 2 = 1时显然成立当相> 1时设正整数m的素因数分解式m = p2其中素数pa 2< p, % > 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,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（）=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冗沁丁)计算得恰好就是与互素的，的个数.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)(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),从而 2"21 s,s 2 2皿.但 S = (1)(1) H(Id) (Id)2 P2 Pk 2% Pk= - + 2(-/-225<2"2矛盾.于是假设不成立，所以()= 0.由引理知道4 二九回到原题,s = £ 3)+1 = V必42tL.下面我们证明 <(2K=1,2,利 dn d i=i di1<S = Y 3，)+ l机2 ,所以4 «2m.这就证明了，= 1时结论成立. z=i 44假设m>i> 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.这就证明满足要求的至多有有限多个.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 << P"j21.证明："(")=n(l - -)(1 - -) (1-).Pi Pi Ps.设武）表示正整数”的所有正因数的个数,0（）表示模的一个简系的元素个数证明：（pn）T（ri） > n.5 .证明：对任意的正整数加都有2。（"）=帆 dmn1 d 2 -"i6 .设是正整数,证明： 。= Zn（l-立e d ）. y=i dn d k=l7 .给定整数9.证明：至多存在有限个正整数，同时满足下列条件：() = ；川奴孔)+。(初高一竞赛数论专题6.欧拉函数与Mobius函数解答欧拉函数°（机）是一个定义在正整数集上的函数，9（加）的值等于1,2,，根-1中与相互素的数的个数.也等 于模相的一个简系的元素个数.1, = 1Mobius函数4（）定义为（）= < （一1），n= "仍5,素数< P2 << Ps0,其他即有大于 1的平方因数若0nl，%）= 1, X1跑遍模叫的简系，马跑遍模m2的简系.证明：加2%+叫工2跑遍模加1加2的简系.证明：我们知道王跑遍模的完系，则王跑过叫个数,马跑遍模加2的完系，则/跑过加2个数，于是m2x + myx2跑过叫根2个数.假设加+三加2吊'+m1域（mod加匹2）淇中x；，k是模叫的完系中的数,乂,芯'是模根2的完系中的数.于是与工 三机2k（mod肛），肛乂 三叫x；（mod根2）.因为（叫，加2 ） = L 所以 X：三 xf（mod 犯）,戈2 -月（mod m2）.所以 x = x：, xr2 =,这表明加2% +班跑遍模町22的完系.若（ ,犯）=（%，加2）= 1，则由（町，加2）= 1得（加2% ,犯）=（町，加2）= 1，于是（，巧X +miX2,mi）=（加2% + 班12,加2）=1.所以（加2% +m1x2,mlm2） = 1.反之，若（7%玉+肛/，町根2）= 1 则（W2% +4%2,叫）=L（根2% +叫工2,7%）=L于是（生玉，班）=L （班/，加2）= 1所以（斗，加1）= 1，（工2,机2）= L这就证明了所要的结论.1 .若（班,加2）= 1，证明：。（班加2）= 9（叫）9（以2）,证明：因为（肛,根2）= 1，七跑遍模叫的简系，/跑遍模m2的简系.则用2% +肛/跑遍模叫m2的简系.所以模叫也的简系个数。（班机2）等于也玉+叫工2跑过的个数，否跑过的个数为模叫的简系个数夕（班）, 工2跑过的个数为模m2的简系个数9（机2）.于是也玉+犯跑过的个数为9（叫）9（根2）BP。(叫帆2)=。(血)。(加2).2 .设及是正整数，证明：£ 3) =，.(2)证明：9(0 = E 4(d)；=工心)d.(3)证明：Z(d)= Fdndnd 川 Clj2|n证明(1)当及=1时Z(d) = 4(1) = 1 .结论成立. dn当> 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的素因数分解式 =pp"pf，其中素数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
