n³−n が6の倍数(因数分解と整数)

方針

解答

⓪ 発想 — どう考え始めるか。 整数の倍数証明は、まず因数分解から。$n^3-n=n(n^2-1)=(n-1)n(n+1)$ — 連続する3つの整数の積だ。

連続3整数には、2の倍数が少なくとも1つ、3の倍数がちょうど1つ、必ず含まれる。

だから積は $2\times 3=6$ の倍数。「連続整数の積」に持ち込めた瞬間に、勝負がついている。

① 因数分解。 $n^3-n=n(n^2-1)=(n-1)n(n+1)$。これは連続する $3$ 整数 $n-1,n,n+1$ の積。

② $2$ の倍数を含む。 連続する $2$ 整数 $n,n+1$ のどちらかは偶数だから、積は $2$ の倍数。

③ $3$ の倍数を含む。 連続する $3$ 整数 $n-1,n,n+1$ のいずれか $1$ つは $3$ の倍数(整数を $3$ で割った余りは $0,1,2$ のどれかで、$3$ 連続すればすべて現れる)だから、積は $3$ の倍数。$2$ と $3$ は互いに素なので、積は $6$ の倍数。

まとめ $n^3-n=(n-1)n(n+1)$ は連続 $3$ 整数の積で、$2$ の倍数と $3$ の倍数を必ず含むから $6$ の倍数。因数分解と整数(連続整数)の融合。

発展 — 一歩先へ。 同じ設計図で $n^5-n=n(n-1)(n+1)(n^2+1)$ は30の倍数になる(2・3の倍数は本問と同じ、5の倍数は $n^2+1$ が $n\equiv \pm 2(\mathrm{mod}5)$ を拾う)。この「$n^p-n$ が $p$ の倍数」という現象の一般形がフェルマーの小定理で、整数の単元で再会する。連続整数の積は、その入り口に立つ最初の道具だ。

別解

差分をとって帰納法で(連続積をもう一度呼び出す)。 $f(n)=n^3-n$ の隣どうしの差を見る。

$$f(n+1)-f(n)=\left\{(n+1{)}^3-(n+1)\right\}-(n^3-n)=3n^2+3n=3n(n+1)$$

$n(n+1)$ は連続2整数の積で必ず偶数。だから差は $3\times (\text{偶数})=6$ の倍数だ。

$f(0)=0$ は6の倍数。差がつねに6の倍数なら、$f(1),f(2),\dots$ と順に6の倍数であることが遺伝する($n<0$ へは $f(-n)=-f(n)$ で折り返す)。

連続3整数(本解)は一撃の観察、差分+帰納法は「1歩ごとの増分が6の倍数」という動的な見方。$\mathrm{mod}6$ で $n=0,1,\dots ,5$ の6通りを全部代入する総当たりも、確実さでは負けない第3の道だ。