オリンピック数論

ルジャンドルの公式は、階乗や二項係数のちょうどの素数冪による整除性を計算する標準的な道具であり、クンマーの定理と組み合わせると、与えられた素数で割り切れる二項係数を正確に説明する。

**ステップ1:$v_p(n!)$ を各因数にわたる和として書く。** 定義により $n! = 1\cdot 2\cdots n$ なので、$v_p(n!) = \sum_{k=1}^{n} v_p(k)$、すなわち $1$ から $n$ までのすべての整数の $p$進付値の和である。

**ステップ2:各 $v_p(k)$ を数え上げとして書き換える。** 各 $k$ について、$v_p(k) = \sum_{i=1}^{\infty} [p^i \mid k]$(アイバーソン記法、真なら $1$、偽なら $0$)である、なぜなら $k$ がちょうど $v_p(k)$ 個の $i$ の値(すなわち $i=1,\dots,v_p(k)$)について $p^i$ で割り切れるからである。

ステップ3:和の順序を入れ替える。 代入すると $v_p(n!) = \sum_{k=1}^n \sum_{i=1}^{\infty} [p^i \mid k] = \sum_{i=1}^{\infty} \sum_{k=1}^n [p^i \mid k]$、(有限なので正当な)二重和を入れ替える。

**ステップ4:$p^i$ の倍数を直接数える。** 内側の和 $\sum_{k=1}^n [p^i \mid k]$ は $1$ から $n$ までの整数のうち $p^i$ の倍数がいくつあるかを数え、それはちょうど $\left\lfloor \frac{n}{p^i} \right\rfloor$ である(倍数は $p^i, 2p^i, \dots, \lfloor n/p^i\rfloor \cdot p^i$)。

ステップ5:結論。 代入し戻すと $v_p(n!) = \sum_{i=1}^{\infty} \left\lfloor \frac{n}{p^i} \right\rfloor$ となり、$p^i > n$ となれば $\lfloor n/p^i \rfloor = 0$ なので有限であり、証明が完了する。

LTEは高次のべきの差の整除性という難しい問題を、付値に関する単純な算術に変える。これは、$a^n-b^n$ のような式を割り切る素数の最大冪を求めたり、そのような式がある素数冪で決して(あるいは常に)割り切れないことを証明したりするオリンピック問題を解く最も速い方法の一つである。

**ステップ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)$ が得られる。