升幂引理

**第1步:利用乘性归结到 $n=p$ 的情形。** 写 $n = p^{v_p(n)} \cdot m$,其中 $p \nmid m$。将下面证明的 $n=p$ 情形反复应用于 $a^m, b^m$(代替 $a,b$),可得 $v_p(a^n-b^n) = v_p((a^m)^{p^{v_p(n)}} - (b^m)^{p^{v_p(n)}}) = v_p(a^m-b^m) + v_p(n)$,故只需证明当 $p \nmid m$ 时 $v_p(a^m - b^m) = v_p(a-b)$,以及证明基础步骤 $v_p(a^p-b^p) = v_p(a-b)+1$。

第2步:用因式分解证明基础步骤。 分解 $a^p - b^p = (a-b)(a^{p-1}+a^{p-2}b+\cdots+b^{p-1})$。需证第二个因子 $S = \sum_{j=0}^{p-1} a^{p-1-j}b^j$ 满足 $v_p(S) = 1$。

**第3步:证明 $p \mid S$。** 由 $p \mid a-b$ 得 $a \equiv b \pmod p$,故每一项 $a^{p-1-j}b^j \equiv b^{p-1-j}b^j = b^{p-1} \pmod p$。将全部 $p$ 项相加,$S \equiv p\cdot b^{p-1} \equiv 0 \pmod p$(利用 $p \nmid b$),故 $p \mid S$。

**第4步:证明 $p^2 \nmid S$。** 写 $a = b + pt$($t$ 为整数,因 $p\mid a-b$ 而可行)。展开每一项 $a^{p-1-j}b^j = (b+pt)^{p-1-j}b^j \equiv b^{p-1-j}b^j + (p-1-j)pt\, b^{p-2-j}b^j \pmod{p^2}$(二项式展开,舍去 $p^2$ 及以上的项)。对 $j=0,\dots,p-1$ 求和:首项之和如前为 $p\,b^{p-1}$,修正项之和为 $pt\,b^{p-2}\sum_{j=0}^{p-1}(p-1-j) = pt\,b^{p-2}\cdot\frac{p(p-1)}{2}$,可被 $p^2$ 整除(因 $p$ 为奇数,$\frac{p-1}{2}$ 为整数,故此修正项为 $p^2\cdot(\text{integer})$,即 $\equiv 0 \pmod{p^2}$)。于是 $S \equiv p\,b^{p-1} \pmod{p^2}$,又因 $p \nmid b$,$p\,b^{p-1}$ 能被 $p$ 整除但不能被 $p^2$ 整除,得 $v_p(S)=1$。

第5步:合并。 由第2–4步,$v_p(a^p-b^p) = v_p(a-b) + v_p(S) = v_p(a-b)+1$。结合第1步的归约(以及当 $p\nmid m$ 时 $v_p(a^m-b^m)=v_p(a-b)$ 这一事实,此时 $S \equiv m\,b^{m-1} \not\equiv 0 \pmod p$,可同法证明),对 $v_p(n)$ 归纳即得对所有正整数 $n$ 有 $v_p(a^n-b^n) = v_p(a-b)+v_p(n)$。