高一竞赛数论专题 5.素因数分解
算术基本定理：设整数a?1,那么a?p1p2ps.其中pj是素数,在不计次序下唯一.把a?p1p2???npn, p1?p2?ps.中相
同的素数合并,则得到标准素因数分解式a?p11p22
正因数个数定理：设?(n)?素数,则?(n)?
正因数和定理：设?(n)?s?pn,?1,?2,,?n?0.
?1?2nn?p表示大于1的整数的所有正因数的个数,若11p2?d|n?sps,其中pj是
?(1??).
ii?1s?d表示大于1的整数n的所有正因数之和,若n?pd|n1?1?2p2?sps,其中pj是素
pi?i?1?1数,则?(n)??.
p?1i?1i
1.设a,b是非零的整数,证明：(a,b)[a,b]?ab.
2.设n是正整数,证明：n!的素因数分解式为n!?
?pp?n?(p,n)?n?,其中p是素数,?(p,n)???j?.
j?1?p??
3.求2017!的十进制表示式中末尾的零的个数.
4.设n为正整数.证明：若n的所有正因数之和为2的整数次幂,则这些正因数的个数也为2的整数次幂.
5.设整数n?3,不超过n的素数共有k个.设A为集合{2,3,一个数不是另一个数的倍数.证明存在集合{2,3,数的倍数,且B包含A.
,n}的子集,A的元素个数小于k,且A中任意
,n}的k元子集B,使得B中任意一个数也不是另一个
高一竞赛数论专题 5.素因数分解解答
算术基本定理：设整数a?1,那么a?p1p2ps.其中pj是素数,在不计次序下唯一.把a?p1p2???npn, p1?p2?ps.中相
同的素数合并,则得到标准素因数分解式a?p11p22
正因数个数定理：设?(n)?素数,则?(n)?
正因数和定理：设?(n)?s?pn,?1,?2,,?n?0.
?1表示大于1的整数n的所有正因数的个数,若n?pd|n1?1?2p2?sps,其中pj是
?(1??).
ii?1s?d表示大于1的整数n的所有正因数之和,若n?pd|n1?1?2p2?sps,其中pj是素
pi?i?1?1. 数,则?(n)??pi?1i?1
1.设a,b是非零的整数,证明：(a,b)[a,b]?ab.
证明：设素因数分解式a?p11p22则(a,b)?p1min{?1,?1}min{?2,?2}p2???n?2pn,b?p1?1p2?npn p1?p2??pn,?i,?i?0.
max{?n,?n}pn.
min{?n,?n}max{?2,?2}pn,[a,b]?p1max{?1,?1}p2min{?2,?2}?max{?2,?2}(a,b)[a,b]?p1min{?1,?1}?max{?1,?1}p2min{?n,?n}?max{?n,?n}pn
?1??1?2??2?p1p2?n??n?1?2pn?p1p2?n?2pn?p1?1p2?npn?ab.
2.设n是正整数,证明：n!的素因数分解式为n!?
证明：一方面若素数p|n!,则p|k,1?k?n.另一方面,任一素数p?n,必有p|n!. 所以n!?p11p22下面去确定?j.
设?(p,n)为整数n!的素因数p的次方. 因为必有整数k满足p?n?pkk?1?pp?n?(p,n)?n?,其中p是素数,?(p,n)???j?.
j?1?p?????sps, 2? p1?p2??pn?n,?1,?2,,?s?0.
?n?k?n?,所以??j????j?.
j?1?p?j?1?p??设cj表示1,2,?n?,n中能被pj整除的数的个数,则cj??j?.
?p??n??n?,n中恰能被pj整除的数的个数.则dj?cj?cj?1??j???j?1?.
?p??p?dj 表示1,2,
显然当j?k时,dj?0.及?(p,n)?1?d1?2?d2?于是?(p,n)?1?d1?2?d2??k?dk.
?k?(ck?ck?1)
?k?dk?1?(c1?c2)?2?(c2?c3)?kkc1?c2?所以n!?
?ck?ck?1?c1?c2??n???n??ck??ck???j????j?.
j?1j?1?p?j?1?p??p?p?n(p,n).
3.求2017!的十进制表示式中末尾的零的个数.
解：这就是要求正整数k使得10||2017!.
因为10?2?5,实际上是求2的最大方次与5的最大方次的最小值. 显然2的最大方次大于5的最大方次. 所以就是求5的最大方次?(5,2017).
k
相关推荐：
loading