成都七中高一竞赛数论专题 6.欧拉函数与M?bius函数
欧拉函数?(m)是一个定义在正整数集上的函数,?(m)的值等于1,2,于模m的一个简系的元素个数.
,m?1中与m互素的数的个数.也等
?1, n?1 ?M?bius函数?(n)定义为?(n)??(?1)s, n?p1p2ps,素数p1?p2??ps
?0, 其他即n有大于1的平方因数 ?
1.若(m1,m2)?1,x1跑遍模m1的简系, x2跑遍模m2的简系.证明：m2x1?m1x2跑遍模m1m2的简系.
2.若(m1,m2)?1,证明：?(m1m2)??(m1)?(m2).
3.设n是正整数, (1)证明：
4.已知正整数n的素因数分解式n?p11p22证明：?(n)?n(1?
???sps,其中素数p1?p2?nn?1?2?(n)??(d)??()d.?(d)??(n). (2)证明： (3)证明：?(d)?.??????dd2n??d|nd|nd|nd|n?ps,?i?1.
11)(1?)p1p2(1?1). ps5.设?(n)表示正整数n的所有正因数的个数,?(n)表示模n的一个简系的元素个数证明：?(n)?(n)?n.
6.证明：对任意的正整数m都有
??(d)?m.
d|m1d2?djki). 7.设n是正整数,证明：?(n)???(1??edk?1j?1d|nn
8.给定整数a?9.证明：至多存在有限个正整数n,同时满足下列条件：(1)?(n)?a；(2)n|?(n)??(n).
高一竞赛数论专题 6.欧拉函数与M?bius函数解答
欧拉函数?(m)是一个定义在正整数集上的函数,?(m)的值等于1,2,于模m的一个简系的元素个数.
,m?1中与m互素的数的个数.也等
?1, n?1 ?M?bius函数?(n)定义为?(n)??(?1)s, n?p1p2ps,素数p1?p2??ps
?0, 其他即n有大于1的平方因数 ?
1.若(m1,m2)?1,x1跑遍模m1的简系, x2跑遍模m2的简系.证明：m2x1?m1x2跑遍模m1m2的简系.
证明：我们知道x1跑遍模m1的完系,则x1跑过m1个数,x2跑遍模m2的完系,则x2跑过m2个数, 于是m2x1?m1x2跑过m1m2个数.
??m1x???????????假设m2x12?m2x1?m1x2(modm1m2),其中x1,x1是模m1的完系中的数,x2,x2是模m2的完系中的??m2x1??(modm1),m1x2??m1x2??(modm2). 数.于是m2x1??x1??(modm1),x2??x2??(modm2).所以x1??x1??,x2??x2??. 因为(m1,m2)?1,所以x1这表明m2x1?m1x2跑遍模m1m2的完系.
若(x1,m1)?(x2,m2)?1,则由(m1,m2)?1得(m2x1,m1)?(m1x2,m2)?1, 于是(m2x1?m1x2,m1)?(m2x1?m1x2,m2)?1. 所以(m2x1?m1x2,m1m2)?1.
反之,若(m2x1?m1x2,m1m2)?1.则(m2x1?m1x2,m1)?1,(m2x1?m1x2,m2)?1. 于是(m2x1,m1)?1,(m1x2,m2)?1.所以(x1,m1)?1,(x2,m2)?1. 这就证明了所要的结论.
2.若(m1,m2)?1,证明：?(m1m2)??(m1)?(m2).
证明：因为(m1,m2)?1,x1跑遍模m1的简系, x2跑遍模m2的简系.则m2x1?m1x2跑遍模m1m2的简系. 所以模m1m2的简系个数?(m1m2)等于m2x1?m1x2跑过的个数,x1跑过的个数为模m1的简系个数?(m1),
x2跑过的个数为模m2的简系个数?(m2).于是m2x1?m1x2跑过的个数为?(m1)?(m2).
即?(m1m2)??(m1)?(m2).
3.设n是正整数, (1)证明：
证明(1)当n?1时
nn?1?2?(n)??(d)??()d.?(d)??(n). (2)证明： (3)证明：?(d)?.??????dd2n??d|nd|nd|nd|n??(d)??(1)?1.结论成立.
d|n当n?1时,设n的素因数分解式n?p11p22???sps,?i?1.
??(d)??d|nd|p1p2n1?(d)?1?Cs(?1)1?Cs2(?1)2?psn?Css(?1)s?(1?1)s?0.结论成立.
n (2)?(n)? k?1(k,n)?1?1??k?1d|(k,n)??(d)?n(?(d)1)?(?(d)1)??(d). ?????dd|(k,n)k?1d|nk?1d|nd|kn显然?(d)
nn??()d.所以得证. dd(3)当n?1时,显然成立. 当n?p1p22ps,素数p1?p2??ps,??(d)?1,?2(n)?((?1)s)2?1.所以结论成立.
d2|n当n?mq,q为不含平方因数的整数,若d|n,则d|m. 则
2??(d)???(d)?0,?d|n22(n)?0,结论成立.
d|m所以
2?(d)??(n). ?d2|n4.已知正整数n的素因数分解式n?p11p22证明：?(n)?n(1?
法1证明：?(n)??(p11p22?????sps,其中素数p1?p2??ps,?i?1.
11)(1?)p1p2(1?1). ps?s?1?2ps)??(p1)?(p2)??(ps)s
?sps(1??1?1?2?1?p1(p1?1)p2(p2?1)?s?1?1?2ps(ps?1)?p1p211)(1?)p1p2(1?1) ps?n(1?11)(1?)p1p2(1?1). psn法2 ?(n)???(d)?n??d12d|nd|p1p?2?n(1?11)(1?)p1p2(1??(d)sp?sd?nd|p1p2??(d)psd?n(1??k?1s(?1)k)pi1pi2pik
1) ps5.设?(n)表示正整数n的所有正因数的个数,?(n)表示模n的一个简系的元素个数证明：?(n)?(n)?n.
证明：当n?1时,显然成立.
当n?1时,设正整数n的素因数分解式n?p11p22则?(n)?n(1????sps,其中素数p1?p2??ps,?i?1.
11)(1?)p1p2(1?1).?(n)?(1??1)(1??2)ps(1??s).
111)?n(1?)(1?)ps221n(1?)?s.
22因为2?p1?p2??ps,所以?(n)?n(1?(1??s)?2s.
11)(1?)p1p2(1??(n)?(1??1)(1??2)所以?(n)?(n)?ns?2?n. s26.证明：对任意的正整数m都有
??(d)?m.
d|m证明：方法1 当m?1时显然成立
当m?1时设正整数m的素因数分解式m?p11p22?2d|m,所以d?p1?1p2???sps,其中素数p1?p2??ps,?i?0.
ps?s,,?i??i.
?s?1于是
?1??(d)????????(pd|m1?02?0s?0?1?21p2?2ps)????s?1?2?1?0?2?0?(p?)?(p?)??11?s22?(ps?)
ss?0???(p1)??(p2)?1?2?1?0?2?0?2?(p?). ??sss?0?s注意到
?(p??i?0?si?i)??(pi?i?pi?i?1)?pi?i.
?i?0?s所以
??(d)????(p)???(p1?1?1?22?2)d|m1?02?0?(p?)?p?p???ss?s1122?sps?m.
s?0方法2 我们把正整数1,2,,m.按与m的最大公约数分类.即与m有相同的最大公约数的作为一类.
这样,m的正约数d与这样的分类正整数之间建立了一个一一对应关系. 记Md?{j|(j,m)?d,1?j?m}.
首先每一个m的正约数都对应一个Md,其次不同的m的正约数对应不同的Md. 所以这些分类Md就是1,2,,m的一个划分.
mm)?1.因为1?j?m,所以1?q?. dd因为(j,m)?d,所以j?dq,于是(q,这样满足上式的q就是模
mm的简系,所以q的个数为?(). dd这就是说满足Md的元素个数为?(mm).所以m???().
ddd|m注意到
??()???(d).所以??(d)?m.
d|md|md|mmd1d2?djki). 7.设n是正整数,证明：?(n)???(1??edk?1j?1d|nn
证明：令?j?e
若(j,n)?1,则(j,d)?1,则?j?1.于是
2?jid.则?ek?1d2?jkid??(?j)k.
k?1d?(?k?1dj)?0.从而?ekk?1d2?jkid?0.
1d2?djki)?1. 所以?(1??edk?1d|n若(j,n)?1,则存在d|n.使得d|j.于是此时?j?e2?jid?1.所以?ek?1d2?jkid??(?j)k?d.
k?1d1d2?djki(1??e)?0. ?dk?1d|n1d2?djki1d2?djki)?1.若(j,n)?1时,?(1??e)?0. 也就是说若(j,n)?1时, ?(1??edk?1dk?1d|nd|n1d2?djki(1??e)计算得恰好就是与n互素的j的个数. ??dj?1d|nk?1n1d2?djki). 故?(n)???(1??edk?1j?1d|nn
8.给定整数a?9.证明：至多存在有限个正整数n,同时满足下列条件：(1)?(n)?a；(2)n|?(n)??(n).
证明：设?(n)??(n)?ns,s?N. 因为?(n)?*??(d),?(n)??d??.所以s??d|nd|nd|nd|nndnd?(d)?1d.
注意到?(d)?{?1,0,1},所以?(d)?1?{0,1,2}. 设d1?d2??dm是n的所有正约数中满足?(d)??1的那些.
先证明引理 ?(n)?0.
引理的证明(反证法) 假设?(n)?0,即n无平方因子.则n?p1p2于是?(n)??(n)?(p1?1)(p2?1)因为?(n)?2?a?9,所以k?4. 若n是奇数,所以p1,p2,于是2|(p1?1)(p2?1)但s?(1?kpk,p1?p2?(pk?1)?p1p2?pk. pks.
(pk?1)?(p1?1)(p2?1)k,pk都是奇素数, (pk?1)?(p1?1)(p2?1)(1?111)?(1?)(1?)pkp1p2(pk?1),从而2k|s,s?2k. (1?14)?1?()k?2k,矛盾. pk311)(1?)p1p2若n是偶数,所以p1?2,p2,于是2但s?k?1,pk都是奇素数, (pk?1)?(p1?1)(p2?1)(1?|(p1?1)(p2?1)(1?(pk?1),从而2k?2|s,s?2k?2.
11(1?)2p2131)?(1?)pk2p21134616)???()k?2??2()k?2?2k?2,矛盾. pk223525于是假设不成立,所以?(n)?0. 由引理知道dm?n. 回到原题,s??d|n?(d)?1d??i?1m?(di)?1di.下面我们证明di?(2m)2,i?1,2,i?1,m.
1?s??i?1m?(di)?1di?m2,所以d1?2m.这就证明了i?1时结论成立. d12j?1假设m?i?1,且对1?j?i,均有dj?(2m).
s??j?1i?1?(dj)?1dj??j?im?(dj)?12mdj?di.
s??j?1i?1?(dj)?1dj为正有理数,通分约分后分母至多为d1d2di?1,分子至少为1,
所以s??j?1i?1?(dj)?1dj?1d1d2di?1.
01从而
2m1?,于是di?2md1d2did1d2di?1i?1di?1?(2m)1?2?2??2i?2?(2m)2.
i?1这就证明了di?(2m)2,i?1,2,特别地n?dm?(2m)2m?1a?1,m.
?(2a)2.
这就证明满足要求的n至多有有限多个.
相关推荐：
loading