四川省成都市第七中学高一年级竞赛数学数论专题讲义：5.素因数分解

注意到2017?5. 所以?(5,2017)??5?2017??2017??2017??2017???2???3???4??403?80?16?3?502. ??5??5??5??5?所以2017!的十进制表示式中末尾的零的个数为502个.

4.设n为正整数.证明：若n的所有正因数之和为2的整数次幂,则这些正因数的个数也为2的整数次幂.

证明：设n?p11p22???sps, p1?p2?s?ps,?1,?2,i2i,?s?0,pi为素数.

则n的所有正因数之和?(n)??d??(1?p?pd|ni?1??pi?i).

若?(n)为2的整数次幂,则?(n)的因数fi?1?pi?p?显然pi?2,?i是奇数.

23若?i?1, 则fi?(1?pi)?(pi?pi)2ipi?i?1?1也是2的整数次幂. ?pi?pi?1?i?(pi?i?1?pi?i)?(1?pi)(1?pi2?pi4??pi?i?1不含大于1的奇数因数.

?pi?i?1).

24由于fi的素因数只有2,所以1?pi?pi?于是

?i?1

2

2i是奇数.

2?所以1?p?p?2i4i4i?pi8i?i?1?(1?p)?(p?p)?2?2i4i6i?i?12?(pi?2?pi2??i?12)

?i?12?(1?p)(1?p?p?2pi?2)?(1?pi2)(1?pi4?pi8?8pi?i?3).

从而fi?(1?pi)(1?pi)(1?pi?pi?24pi?i?3).

22于是1?pi,1?pi都是2的整数次幂,显然1?pi?1?pi,于是1?pi|1?pi.

2因为1?pi?(1?pi)(pi?1)?2,1?pi|(1?pi)(pi?1).所以1?pi|2.于是pi?1矛盾.

因此?i?1,i?1,2,,s).

ssn的正因数的个数?(n)??1??(1??i)??(1?1)?2s.

d|ni?1i?1故n的正因数的个数也是2的整数次幂.

5.设整数n?3,不超过n的素数共有k个.设A为集合{2,3,一个数不是另一个数的倍数.证明存在集合{2,3,,n}的子集,A的元素个数小于k,且A中任意

,n}的k元子集B,使得B中任意一个数也不是另一个

数的倍数,且B包含A.

证明：引理：若|A|?k,则可在{2,3,,n}\\A中找到一个数b,其不整除集合A中任意一个数,也不被集合

A中任意一个数整除.

若引理得证,进而将数b添入集合A中,并重复这一过程,直到将A扩充成一个k元子集B,则集合B满足要求.

下面证明引理,对大于1的整数m,设m的标准素因数分解为m?p11p22定义f(m)?max{p11,p22,由于|A|?k,则N?使得p????s,ps}.

???sps.

?f(a)不同的素因子个数小于k,又不超过n的素数共有k个,因此,存在素数p?n,a?AN.于是p??1f(a).

设p?n?p,则p??A(若不然,将有f(p?)?p?,于是p|N,与pN矛盾).

?对任意a?A,若a|p,则f(a)?a为p的方幂.于是p|N,与p?N矛盾.因此ap?.

??若p|a,因为pN,所以pf(a),故f(a)?q,q为不同于p的素数,且q?p?p.

从而a?pq?pp?p???????1?n,矛盾.因此p?a.

从而,不属于A的元素p不整除集合A中任意一个数,也不被集合A中任意一个数整除.

法2 将不超过n的所有k个素数从下到大记为p1,p2,对i?1,2,,pk.

,k,取正整数?i满足pi?i?n?pi?i?1,对这个?i,取正整数?i满足?ipi?i?n?(1??i)pi?i,

其中,?i,?i均唯一确定的,且?i?pi.

令Di?{pi|s??i,s?N},Mi?{tpii|t??i,t?N}. 则Di为pii在{2,3,考虑k个集合Ai?Di从而A1,A2,?s*?*,n}中的约数全体,Mi为pi?i在{2,3,,n}中的倍数全体.

Mi(i?1,2,,k},注意到集合Ai中的每个数均以pi为最大素因子,

,Ak为{2,3,,n}的两两不相交的k个子集.

,k},使得A当|A|?k时,必存在某个i?{1,2,Ai??,即pi?i不整除集合A中任意一个数,也不被集合

A中任意一个数整除.

将pii添入集合A.重复这一过程,直到将A扩充成一个k元子集B,则集合B满足要求.

?