证明多项式恒等式$(x+1)^n \equiv x^n +1 \mod n$当且仅当n为素数

咱们一步步拆解这个问题，先搞定素数方向的证明，再解决合数的情况：

一、当n是素数时，恒等式成立 #

根据二项式定理，$(x+1)^n$ 可以展开为：
$$(x+1)^n = \sum_{k=0}^n \binom{n}{k}x^k$$
当n是素数时，对于中间项（也就是$1\leq k\leq n-1$），组合数 $\binom{n}{k} = \frac{n!}{k!(n-k)!}$。分子里包含素数n作为因子，但分母的$k!$和$(n-k)!$都小于n，无法整除n（因为n是素数，小于n的数都和n互质），所以整个组合数必然是n的倍数，也就是 $\binom{n}{k} \equiv 0 \mod n$。

这样展开式里就只剩下k=0和k=n的项，也就是$1 + x^n$，因此：
$$(x+1)^n \equiv x^n +1 \mod n$$
这部分的证明就完成了。

二、当n不是素数时，恒等式不成立 #

如果n是合数，我们分两种情况讨论，核心思路是找到某个x使得等式不成立，或者证明展开式中存在非零modn的系数：

情况1：n是素数的幂（比如$n=p^m$，m≥2，p是素数） #

举个例子，n=4（$2^{2$）：取x=1，左边$(1+1)}4=16$，16 mod4=0；右边$1^4+1=2$，2 mod4=2，显然0≠2，等式不成立。

更一般地，考虑组合数 $\binom{n}{p} = \binom{p^m}{p}$，计算这个组合数的话：
$$\binom{p^m}{p} = \frac{p^m(pm-1)(p^m-2)...(pm-p+1)}{p!}$$
分子里有$p^{m$这个因子，分母$p!$里只有一个p因子，所以化简后这个组合数等于$p}{m-1}$乘以一个不被p整除的整数。因为m≥2，$p^{{m-1}$是p的倍数，但不是$p}m$的倍数，所以 $\binom{p^m}{p} \not\equiv 0 \mod p^{m$。这意味着展开式中$x}p$的系数不为0 modn，多项式$(x+1)^n -x^n -1$不是零多项式，必然存在某个x让等式不成立。

情况2：n是多个不同素数的乘积（比如n=pq，p、q是不同素数） #

还是举例子，n=6（2×3）：取x=2，左边$(2+1)^6=729$，729 mod6=3；右边$2^6+1=65$，65 mod6=5，3≠5，等式不成立。

从通用角度看，设p是n的一个素因子，n=p×k（k≥2且k与p互质），组合数$\binom{n}{p}$同样不被n整除：
$$\binom{n}{p} = \frac{n(n-1)...(n-p+1)}{p!} = \frac{p×k×(p×k-1)...(p×k-p+1)}{p!}$$
分子里只有一个p因子（后面的p-1个数都不被p整除），分母里也只有一个p因子，化简后得到的数是k乘以一个整数，而k与p互质，所以这个组合数是k的倍数，但不是p×k=n的倍数，即 $\binom{n}{p} \not\equiv0 modn$。同样说明展开式存在非零系数，恒等式无法成立。

综上，当且仅当n是素数时，多项式恒等式$(x+1)^n \equiv x^n +1 \mod n$成立。

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