为什么把一个数与它的因子比较?
6 的真因子是 1,2,3,它们的和恰好是 6。28 也有这个性质:1+2+4+7+14=28。我们自然会问:能否找出所有这样的数?与其每次单独列出真因子,不如把数本身也加进去,定义因子和函数 σ(n)=d∣n∑d。所求条件便成为 σ(n)=2n,这更适合利用素因子分解。接下来的目标,是把这个关于加法的等式变成对素因子的限制,再证明这些限制确实足够。
我们假定读者熟悉唯一素因子分解,下面也会解释 σ 的积性。
因子和与一个构造
正整数 n 的真因子是不同于 n 的正因子。若真因子之和分别等于、小于或大于 n,就称 n 为完全数、亏数或盈数。等价地,将 σ(n) 与 2n 比较。例如 1 的真因子集合为空,空和为 0,所以 1 是亏数。
概念视角代数
完全数即因子倒数之和为二
把 n 的每个因子 d 与 n/d 配对,得到
nσ(n)=d∣n∑nd=d∣n∑d1.所以 n 是完全数当且仅当 d∣n∑1/d=2;例如对 6,1+21+31+61=2。用这个形式看,n 的真倍数 N 保留每个 d∣n 的倒数 1/d,并多出 1/N,所以和严格增大。因此完全数或盈数的每个真倍数都是盈数;例如 σ(12)=28>24。
若 n=i∏piai,每个因子都由各素数的指数从 0 到 ai 独立选取而唯一确定。展开相应的乘积便得到
σ(n)=i∏(1+pi+⋯+piai)=i∏pi−1piai+1−1.
这也证明了:若 gcd(a,b)=1,则 σ(ab)=σ(a)σ(b),因为两边选择的素数幂互不重叠。互质条件不可省略:例如 σ(4)=7,但 σ(2)2=9。
考虑 18=2⋅32。素数幂因子互质,所以
σ(18)=(1+2)(1+3+9)=3⋅13=39>36=2⋅18.真因子之和为 39−18=21,故 18 是盈数。事实上,其真因子是 1,2,3,6,9,和确为 21。再看 16=24:σ(16)=1+2+4+8+16=31<32,故 16 是亏数。从因子和中减去数本身,可以看清为什么应与 2n 而非 n 比较。
候选公式是怎样得到的?
2 的幂离目标只差一点:当 k≥1 时,
σ(2k)=2k+1−1=2⋅2k−1.
所以它的真因子之和恰好比自身少 1。若再乘一个奇素数 p,每个因子的构造就多了一个选择:是否乘上 p。由于 p 与 2k 互质,因子和与原数的比值为
2kpσ(2kp)=(2−2k1)(1+p1).
要使这个比值等于 2,就必须有
(2k+1−1)(p+1)=2k+1p,p=2k+1−1.
因此,只要先在“2 的幂乘一个奇素数的一次幂”这种形状中寻找,常见的公式就已经被等式确定了。接下来还有两件事:证明奇因子为素数时这些候选数确实可行,以及证明偶完全数不可能含有更复杂的奇数部分。这正是下面定理的两个方向。此处的计算只是说明公式为何自然,还没有证明可以把所有可能的数限制成这种形状。
定理 4.2.3
(欧几里得(Euclid)的构造)
设整数 r≥2。若 q=2r−1 是素数,则 N=2r−1q 是完全数。
事实上 q 是奇数,因此 N 的两个因子互质。于是
σ(N)=(1+2+⋯+2r−1)(1+q)=(2r−1)2r=2N.这里既用到互质,也用到 q 是素数:若 q 是合数,则不能写 σ(q)=1+q。
反例模式
构造需要奇因子是素数
很容易把定理读成一条公式:凡 r≥2,2r−1(2r−1) 都是完全数。第一个合数情形已经推翻这个说法。取 r=4,候选数为 N=8⋅15=120=23⋅3⋅5,而
σ(120)=(1+2+4+8)(1+3)(1+5)=15⋅24=360=3⋅120.因子和是该数的三倍而不是两倍,所以 120 是盈数。15 的额外因子 3 和 5 正是 σ(q)=1+q 这一步看不见的部分。修正后的命题保留“2r−1 是素数”这个假设;下一小节证明,合数值总会使候选数成为盈数。
例题 4.2.4
(由梅森(Mersenne)素数构造完全数)
取 r=5,q=31 是素数,所以 N=16⋅31=496。无须逐一列出十个因子,直接算 σ(496)=(1+2+4+8+16)(1+31)=31⋅32=992=2N。因此真因子之和为 496。
为了看清乘积究竟计算了哪些因子,可以把它们排成两行:
1,2,4,8,16;31,62,124,248,496.第一行的奇数部分是 1,第二行的奇数部分是 31。由于 31 是素数,不会有第三种可能的奇数部分。求真因子时,只需删去最后的 496。剩下第一行的和为 31,第二行的和为 31(1+2+4+8)=465,合起来恰好是 496。
这个描述适用于每个素数 q=2r−1。第一行是 2j,其中 0≤j≤r−1;第二行是同一指数范围内的 q2j。由于 q>1,第一行的每项都是真因子;只有第二行的最后一项是原数自身。因此真因子之和为
q+qj=0∑r−22j=q+q(2r−1−1)=2r−1q.这就是直接从因子列表理解构造证明,也说明了素数假设用在哪里:若奇因子是合数,它的非平凡真因子会产生额外的行,两行的描述就漏掉了这些因子。
形如 2r−1 的数称为梅森数;其中的素数称为梅森素数。
若 2r−1 是素数,则 r 必须是素数。因为若 r=ab 且 a,b>1,则
2r−1=(2a−1)(1+2a+⋯+2a(b−1)).
两因子都大于 1,所以 2a−1 是真因子。这会在指数为合数时直接给出分解,却不是对剩余指数的素性判定。反过来不成立:11 是素数,但 211−1=2047=23⋅89。因此仅检查指数不够。
奇因子是合数时会怎样?
事实上,如果梅森数是合数,候选数就会成为盈数。仍令 q=2r−1、N=2r−1q,其中 r≥2。无论 q 是否为素数,2 的幂所贡献的几何和都是 q。若 q 是合数,它就有一个严格介于 1 与 q 之间的因子,故 σ(q)>q+1。于是
σ(N)=qσ(q)>q(q+1)=2N.
失败的原因很明确:q 的额外因子使总和超过了构造所允许的大小。即使不知道这些额外因子的完整列表,也足以得到这个严格不等式。
取 r=6,候选数是 N=32⋅63=2016。由于 63=32⋅7,
σ(N)=63(1+3+9)(1+7)=63⋅104=6552.目标应为 2N=4032;等价地,实际的真因子之和为 6552−2016=4536>2016。63 所贡献的因子和是 104,而素数情形的计算要求它只有 1+63=64。这解释了为什么把一个合数代入公式并不能得到完全数。
为什么每个偶完全数都来自这个构造?
定理 4.2.7
(欧几里得–欧拉(Euler)定理)
一个正偶整数是完全数,当且仅当它可写为 2r−1(2r−1),其中整数 r≥2 且 2r−1 是素数。
上面的构造证明了一个方向。逆向证明不预先限制奇素因子的个数或指数,而是利用完整的因子和,证明奇数部分只能是一个素数。
先分离 2 的幂。 把偶完全数写成 N=2km,其中 k≥1 且 m 为奇数。这里 k=v2(N) 是 2 的确切指数:不断除以 2,直到剩余因子为奇数。这样 2k 与 m 必然互质,才能对这两个因子使用积性。令 q=2k+1−1,则 q≥3。由 σ(N)=2N,
qσ(m)=2k+1m=(q+1)m.迫使一个因子进入奇数部分。 由于 q 与 q+1 互质,欧几里得引理给出 q∣m。这里使用引理并不要求 q 本身是素数。也可以直接把等式改写为 m=q(σ(m)−m),看出整除关系。写 m=qt,其中 t≥1。代回得
σ(m)=(q+1)t=qt+t=m+t.因子和还容得下什么? 等式 σ(m)=m+t 意味着 m 的全部真因子之和必须等于 t。但是 t∣m,而 q>1 保证 t<m,所以 t 自己已经是真因子。若 t>1,另一个不同的真因子 1 就会使总和至少为 t+1,超过允许的值。等价地,1,t,m 是三个不同正因子,它们的和已经是 1+t+m>σ(m)。所有因子都为正数,因此再加入其他因子也无法消除矛盾。
因此 t=1,即 m=q。上式变为 σ(q)=q+1。由于 q>1,它至少有因子 1 和 q;若 q 是合数,就还有别的正因子,使和更大。所以 q 是素数。取 r=k+1 即完成逆向证明。特别地,证明也已经排除了 m=1:它已迫使 m 是 q≥3 的倍数。
证明透视
哪一步用了哪个假设
逆向证明用到三个事实,各在一处使用。第一,正是确切指数 k=v2(N) 使 2k 与 m 互质,才可以写 σ(N)=σ(2k)σ(m)。若分解不是确切的,等式就会出错:把 28 写成 2⋅14,会得到 σ(2)σ(14)=3⋅24=72,但 σ(28)=56。第二,整除 q∣m 只来自 gcd(q,q+1)=1;此时对 q 是否为素数仍一无所知。
关键的一步是因子和的“预算”论证。写成 m=qt 后,等式 σ(m)=m+t 把 m 全部真因子之和固定为 t,而因为 q>1,t 本身已是真因子。因子都是正数,所以当 t>1 时,额外的因子 1 便带来严格不等式。一旦 t=1,同一预算变成 σ(q)=q+1,迫使 q 为素数。因此素数性是证明的结果而不是假设,论证也无须对 m 的奇素因子作任何分情况讨论便告完成。
证明没有预先假定奇因子是素数,而是先推出几何和 q 整除它,再证明不能存在额外因子。这个定理分类的是偶完全数;它既没有证明存在奇完全数,也没有证明奇完全数不存在。这是另一问题。
假设正在研究的偶完全数满足 v2(N)=3,即 8∣N 但 16∤N。证明迫使其奇因子为 24−1=15,又迫使 15 为素数。但 15=3⋅5,矛盾。因此不存在恰含三个因子 2 的偶完全数。这并不能排除所有被 8 整除的数;指数必须恰好为三。
为什么这个对应是一一的?
对梅森素数 q=2r−1,构造给出偶完全数
N=2r−1q=2q+1q.
反向操作很具体:取 N 的奇数部分,也就是除去整除 N 的最大 2 的幂。由于 q 是奇数,所得恰为 q。也可以用 v2(N)=r−1 恢复指数 r。因此不同的梅森素数不可能得到同一个 N。逆向定理又说明每个偶完全数都有这样的原像,所以对应既是单射也是满射。
例如 28=22⋅7 的奇数部分是 7=23−1,故它来自 q=7 和 r=3,不存在第二个指数选择。只有已知偶数是完全数时才能这样恢复:例如 24 的奇数部分是 3,但与 3 对应的完全数是 6,不是 24。
常见误区
指数为素数是梅森数为素数的必要条件,却不是充分条件。反过来,一个梅森数是合数,只能排除与该指数对应的偶完全数,本身不能排除其他指数或奇完全数。此外,σ 的值在不互质的参数上不能随意相乘,这样可能会重复计数;应改用素数幂公式。定理在梅森素数与偶完全数之间建立一一对应,但没有证明它们有无穷多个。
写出 m=qt 后,也许会想把 σ(m) 换成 σ(q)σ(t)。但没有任何一步证明 q 与 t 互质。例如取 q=t=3,则 σ(9)=13,而 σ(3)σ(3)=16。这个例子只是说明错误的乘法,并不是在提出一个完全数候选。逆向证明避开了这一问题:它只用到 t 整除 m,以及取出若干正因子所得到的和不超过总因子和。每当改变分解方式,都应重新检查所用定理的假设。
练习
计算因子和,判断 15 和 120 是亏数、完全数还是盈数。
解答 · 答案
σ(15)=(1+3)(1+5)=24<30,故 15 是亏数;σ(120)=(1+2+4+8)(1+3)(1+5)=360>240,故 120 是盈数。
用定理求 r=7 对应的偶完全数,并验证所需的素性。
解答 · 答案
27−1=127。合数必有不超过其平方根的素因子:把它写成两个大于 1 的因子之积,较小因子不超过平方根,而且这个因子又有素因子。这里 127<12,故只需检查素数 2,3,5,7,11。由奇偶性、各位数字和及末位可排除前三者;另外 127=7⋅18+1=11⋅11+6。因此 127 是素数,答案为 26⋅127=8128。
解答 · 答案
此时 k=11,逆向结论要求 q=212−1=4095 为素数。但 4095=3⋅1365,因此不存在这样的偶完全数。
有人说 r=11 是素数,故 211−1 也是素数。指出错误并给出分解。
解答 · 答案
正确的推论方向是:2r−1 为素数,才可推出 r 为素数。逆命题不成立,因为 2047=23⋅89。
求出所有小于 1000 的偶完全数。说明为什么只需检查少数几个指数;仅列出几个例子不能证明答案完整。
解答 · 答案
每个偶完全数都可写成 N=2r−1(2r−1),其中 r≥2。由于 2r−1≥2r−1,所以 N≥22r−2。若 r≥6,此下界至少为 1024,已经超过范围。因此只需检查 r=2,3,4,5,所得奇因子依次为 3,7,15,31。第一、第二、第四个是素数:对于 31,因其平方根小于 6,只需检查素数 2,3,5;更小的情形可直接判断。15 是合数。所以完整列表为 6,28,496。逆向定理结合大小界保证没有遗漏,而正向构造保证列出的三个数确实完全。
有人说,由于 24−1=15 是合数,不存在被 8 整除的偶完全数。说明错误并给出反例。
解答 · 答案
合数 15 只排除 v2(N)=3,并不排除所有 v2(N)≥3 的情形。完全数 496=24⋅31 被 8 整除,且 v2(496)=4。它的奇因子是另一个梅森数 25−1=31。说 8∣N,并不等于说 8 是整除 N 的最大 2 的幂。