求证：n>1时，σ(n)≡1 mod n当且仅当n为素数

咱们先把要证的核心命题明确下来：

设n>1，σ(n)表示n的所有正约数之和，求证：σ(n)≡1 (mod n) 当且仅当 n是素数。

我之前琢磨这个问题好久没头绪，后来发现一个定理能帮上大忙，先把这个定理摆出来，再一步步拆解证明。

分方向证明 #

充分性：素数 ⇒ σ(n)≡1 mod n #

这部分其实很直观：如果n是素数，那它的正约数只有1和n本身，所以σ(n)=1+n。那σ(n)-1 =n，显然n能整除σ(n)-1，也就是σ(n)≡1 (mod n)，这部分没啥难度。

必要性：σ(n)≡1 mod n ⇒ n是素数 #

这部分是难点，咱们用反证法结合那个关键定理来推导：
首先先给出那个有用的定理：

当k>1时，方程σ(n)=n+k仅有有限个解，特别地，当n≥k²时该方程无解。

假设n是合数，但满足σ(n)≡1 (mod n)。根据同余的定义，存在整数q≥0，使得σ(n)=n*q +1。
因为n是合数且n>1，它至少有三个正约数：1、d、n（其中1<d<n），所以σ(n)=1+d+n+...≥1+2+n=n+3>n+1，因此q必然≥2（如果q=1，σ(n)=n+1，那n的约数只能是1和n，n就是素数，和假设矛盾）。

令k=σ(n)-n，代入σ(n)=n*q+1可得：
k = (n*q +1) -n = (q-1)*n +1
因为q≥2、n>1，所以k≥n+1>1，满足定理中k>1的条件。

现在看方程σ(n)=n+k，结合定理的结论：当n≥k²时方程无解。但我们的k≥n+1，所以k²≥(n+1)²=n²+2n+1>n（毕竟n>1），也就是n<k²，这时候定理没直接说无解，但我们可以从σ(n)的定义找矛盾：

σ(n)是n的所有约数之和，所以σ(n)≤1+2+...+n = n(n+1)/2。代入σ(n)=n*q+1可得：
n*q +1 ≤ n(n+1)/2
整理一下：q ≤ (n+1)/2 - 1/n，因为n>1，所以(n+1)/2 -1/n < (n+1)/2，即q≤⌊(n+1)/2⌋。

但另一方面，σ(n)=n*q+1≥1+n+d（d是n的真因子，d<n），代入得：
n*q +1 ≥1 +n +d
消去两边的1，整理得：(q-1)*n ≥d
因为d是n的真因子，所以d<n，因此：
(q-1)*n <n
两边除以n（n>1，正数）得：q-1 <1，即q<2。

这就和之前得出的q≥2矛盾了！说明我们的假设“n是合数”不成立，因此n必须是素数。

内容的提问来源于stack exchange，提问作者user532929