§1.7正整数的正约数个数与总和
一、正整数的正约数个数
我们先看一个有趣的问题:在一间房子里有编号为1~100的100盏电灯,每盏都配有一个开关,开始灯全灭着.现在有100个人依次进入房间,第k 个人把编号是的k 倍数的灯的开关各拉一次,这样操作完之后,哪些编号的灯亮着?
解决这个问题,需要讨论各盏灯编号的约数个数的奇偶性.如何求一个正整数的约数的个数呢?下面我们讨论这个问题.
设为n 正整数,的n 正约数最小为1,最大为,n 因此的n 正约数的个数有限. 为了叙述更方便，我们把正整数的n 正约数个数记作()d n . 例如, (1)1d =,(2)2d =,(5)5d =,(8)4d =,(12)6d =.
从理论上讲,求d(n)只要把n 的正约数全部找出来数一数就可以了,但这种方法并不适合求数值较大的数的正约数的个数,例如(360)d ,(450000)d .下面我们以求d(360)为例,介绍可行的方法.
由于3602332=⨯⨯5,其正约数比形如323n 2γ
=⨯⨯5,其中α可取0~3四个数之一,β可取0~2三个数之一, γ可取0,1两个数之一. α,β,γ各选定一个允许值,构成一个组合,代入n 即可得到360的正约数个数是24,故(360)43224d =⨯⨯=.
同理由144=432
2⨯,可知(144)(41)(21)15d =++=. 定理1 设正整数n 的标准分解式为1212n p p α
α
=…m m p α
,则 12()(1)(1)d n =α+α+…(1)m α+. 证明: n 的正约数必形如1212k p p α
α
=…m
m
p α,其中1β可取0至1α中任意一个,共有
11α+种取法; 2β可取0至2α中任意一个, 共有21α+种取法;…;m β可取0至m α中任意
一个,共有1m α+种取法,那么
12()(1)(1)d n =α+α+…(1)m α+. 例1 求(300000)d .
解: 因为5
5
30000025 =⨯3⨯,所以
(300000)(51)(11)(51)72d =+++=.
例2 若n p q α
β
=,其中p ,q 为不同质数, α≥1, β≥1.且2
n 有15个正约数,求
7()d n .
解: 由2
22n p q α
β
5=,得
2()(2)(21)1535d n =α+1β+==⨯. 不失一般性.设β≥α,则
2α+1=3, 2β+1=5, 解得α=1, β=2,故2
n pq =,则7
714
n p q =,所以 7
()(71)(141)815120d n =++=⨯=.
例3 有一个小于2000 的四位数,它恰有14个正约数,其中有一个制约数的末尾 数字是1,求这个四位数. （1984年上海初中赛题） 解: 设n 为所求,则()14172d n =⨯=⨯.
若()141d n =⨯,则13
n p =,而13
112000> ,故此时无解.
若()72d n =⨯,则6
n p q =,其中p , q 为不同质数.
为质数p , q 选取适当的值,使其满足p , q 之一的末位数是1,且
0002000n 1 << .易知只有当2p =,31q =时, 62311984n =⨯=符合题意.
定理2 正整数n 为完全平方数的充要条件是()d n 为奇数. 证明: 必要性
设1212(n p p α
α
= (2)
)m m
p α (其中1212p p αα…m m p α的标准分解式),
则
1212n p p α
α
=…m
m
p α,
故12()(2)(21)d n =α+1α+…(21)m α+. 因为12α+1,221α+,21m α+均为奇数,
所以12()(2)(21)d n =α+1α+…(21)m α+.为奇数. 充分性 设1212n p p α
α
=…m
m
p α为n 的标准分解式,则
12()()(1)d n =α+1α+…(1)m α+.
因为()d n 为奇数,所以1α+1,21α+,… ,1m α+均为奇数,从而1α,2α,…,m α均为偶数.设11α=2β,22α=2β,…,m m α=2β,则 1
21
2n p p 2α2α=…1212(m m p p p 2αββ=…2)m m p β,
所以n 为完全平方数.
该定理可以用来分析解决本节开头提出的“拉灯”问题:各盏灯的开关被拉几次取决于其编号的正约数的个数,而灯是否被拉亮取决于其开关被拉次数的奇偶性（奇数则被拉亮）.由定理2可知,亮灯的编号必为完全平方数,即第21,22,2
3,… ,2
10号的灯亮着.
当然,该定理的价值远不止于此,它主要用来判断一个数是否是完全平方数,进而解决其它有关问题.
例4 求证:正整数n
证明: 设n 的所有正约数为1n ,2n ,…,()d n n .因为k n n |,所以存在k m ,使
(1,2,k n m k ==…())d n ,,从而k m n |,即k m 是n 的正约数，所以k m 是1n ,2n ,… ,()d n n 之
一(1())k d n ≤≤.故1m ,2m ,…,()d n m 是1n ,2n ,…,()d n n 重新排序的一个结果,所以
12n n …()12d n n m m =…()12
d n n n
m n n =
…()d n n n =()
12()
...d n d n n n n n ,
则12(n n (2)
()
())d n d n n n
=,所以12n n
…()d n n =
即正整数n
由例4自然联想,正整数n 的所有正约数之和等于多少呢? 二、正整数n 的所有正约数之和
正整数n 的所有正约数之和记作()S n ,下面我们按n 含有的质约数的个数来讨论.
1.当n 只含一个质约数时
例如,9的正约数有1,3,2
3,其和为
32
31
(9)13331
S -=++=-;
32的正约数有23451,2,2,2,2,2,其和为
