正整数的正因数个数：初等数论

引例 在一间房子里有编号为1～100的100盏电灯，每盏配有一个开关，开始灯全灭着，现有100个人依次进屋，第k个人把编号是k的倍数的灯的开关各拉一次，这样操作完之后，哪些编号的灯亮着？

解决这个问题，须讨论各灯编号的因数个数的奇偶性.

如何求一个正整数的正因数的个数呢？

设n为正整数，n的正因数最小为1，最大为n，因此n的正因数个数有限，为了叙述方便，我们把正整数n的正因数个数记作d（n).

例如：d（1)=1，d（3)=2，d（8)=4，d（12)=6.

从理论上讲，求d（n)只要把n的正因数全部找出来数一数即可，但实际上这往往行不通，如求d（540)就很麻烦.所以，我们应该找到一个可行的算法.下面以求d（540)为例，寻找规律和算法.

其中，α可取0，1，2三个数之一；β可取0，1，2，3四个数之一；γ可取0，1两个数之一.

α，β，γ各选定一个允许值，构成一个组合，代入n即可得到540的一个正因数，这样的搭配组合共有3×4×2=24个，这说明540的正因数个数是24.故d（540)=24.

一般地，我们有如下定理.

β1可取0至α1这α1＋1个数之一，共有α1＋1种取法；

β2可取0至α2这α2＋1个数之一，共有α2＋1种取法；

……

βm可取0至αm这αm＋1个数之一，共有αm＋1种取法.

故β1，β2，…，βm选定一种取法，构成一个组合，就确定一个正因数.

这样的组合的个数为（α1＋1)（α2＋1)…（αm＋1)，故

例1 求d（12000).

解 因为12000=25×3×53，所以d（12000)=（5＋1)（1＋1)（3＋1)=48.

例2 设n=pαqβ（p，q为互异质数，α≥1，β≥1)，若n2有15个正因数，问n7有多少个正因数？

解 ∵n2=p2αq2β，∴d（n2)=（2α＋1)（2β＋1)=15=3×5.不妨设β≥α，则2α＋1=3，2β＋1=5，∴α=1，β=2.

∴n=pq2⇒n7=p7q14，d（n7)=（7＋1)（14＋1)=8×15=120.

故n7共有120个正因数.

例3 有一个小于2000的四位数，它恰有14个正因数，其中有一个质因数末位数字是1，求这个四位数（1984年上海初中竞赛题).(www.xing528.com)

解 设n为所求，则d（n)=14×1=7×2.

若d（n)=14×1，则n=p13，而1113＞2000，故此时无解.

若d（n)=7×2，则n=p6q，其中p，q为不同质数.

∵116×2＞2000，26×11=704不是四位数，∴该组不可取.

∵26×31=1984，26×34＞2000，36×11=8019，∴只有1984合题意.故这个四位数是1984.

定理2 正整数n为完全平方数⇔d（n)为奇数.

证明 必要性.

故d（n)=（2α1＋1)（2α2＋1)…（2αm＋1).

∵2α1＋1，2α2＋1，…，2αm＋1均为奇数，

∴d（n)=（2α1＋1)（2α2＋1)…（2αm＋1)为奇数.

充分性.

∵d（n)为奇数，∴α1＋1，α2＋1，…，αm＋1均为奇数，

∴α1，α2，…，αm均为偶数.

设α1=2β1，α2=2β2，…，αm=2βm，则

故n为完全平方数.

该定理可用来分析解决本节的引例：一盏灯的开关被拉几次取决于其编号数的正因数的个数，这盏灯是否亮取决于其开关被拉次数的奇偶性.当一盏灯的编号数的正因数个数是奇数时，它就亮；否则，它就灭.由定理2可知，亮灯的编号数必为完全平方数，即第12，22，32，…，102号灯亮，其余都灭.

当然，该定理的价值远不止于此，它主要用来判定一个数是否是完全平方数，进而解决其他问题，如求完全平方数的正因数倒数之和.

定理3 正整数n的所有不同正因数之积等于nd（n)/2.

证明 设n的所有不同正因数为n1，n2，…，nd（n).

即正整数n的所有不同正因数之积等于nd（n)/2.