指数持ち上げ補題

**ステップ1:乗法性により $n=p$ の場合に帰着させる。** $n = p^{v_p(n)} \cdot m$($p \nmid m$)と書く。$a,b$ の代わりに $a^m, b^m$ に対して $n=p$ の場合(以下で証明)を繰り返し適用すると、$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})$ と分解する。第2因数 $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$ を示す。** 整数 $t$ を用いて $a = b + pt$ と書く($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)$ が得られる。