n⁵−n は30の倍数

方針

解答

⓪ 発想 — どう考え始めるか。 $30=2\cdot 3\cdot 5$。だから $n^5-n$ が $2,3,5$ のそれぞれで割り切れることを示せばよい($2,3,5$ は互いに素)。

まず因数分解。$n^5-n=n(n^4-1)=n(n^2-1)(n^2+1)=(n-1)n(n+1)(n^2+1)$。

$(n-1)n(n+1)$ は連続する $3$ 整数の積だから、$2$ でも $3$ でも割り切れる。$5$ の倍数は、$n$ を $5$ で割った余りで分類する(またはフェルマーの小定理 $n^5\equiv n(\mathrm{mod}5)$)。

① 因数分解する。

$$n^5-n=n(n^4-1)=n(n^2-1)(n^2+1)=(n-1)n(n+1)(n^2+1)$$

② $2$ と $3$ の倍数。 $(n-1)n(n+1)$ は連続する $3$ 整数の積だから、$2$ の倍数かつ $3$ の倍数(すなわち $6$ の倍数)。よって $n^5-n$ も $2,3$ の倍数。

③ $5$ の倍数。 $n$ を $5$ で割った余りで分類する。

• 余り $0$:$n$ が $5$ の倍数。
• 余り $\pm 1$:$n^2\equiv 1$ なので $n^2-1\equiv 0$、因数 $(n^2-1)$ が $5$ の倍数。
• 余り $\pm 2$:$n^2\equiv 4$ なので $n^2+1\equiv 0$、因数 $(n^2+1)$ が $5$ の倍数。

どの場合も $n^5-n$ は $5$ の倍数。

④ まとめる。 $2,3,5$ はどの $2$ つも互いに素だから、$n^5-n$ は $2\cdot 3\cdot 5=30$ の倍数。(証明終)

まとめ:$30$ の倍数は「$2,3,5$ の倍数を別々に」。因数分解で連続 $3$ 整数を出せば $2,3$ は自動。$5$ は余り分類で、$n^2-1$ か $n^2+1$ のどちらかが必ず $5$ で割れる($n^2\equiv 0,1,4(\mathrm{mod}5)$)ことを使う。

発展 — 一歩先へ。 フェルマーの小定理 $n^p\equiv n(\mathrm{mod}p)$ から、$n^5-n$ は $2,3,5$(と、フェルマーが効く $p$)の倍数。一般に $n^k-n$ が $m$ の倍数になる最大の $m$ は、$p-1\mid k-1$ となる素数 $p$ の積。$n^5-n$ なら $p-1\mid 4$ の素数 $2,3,5$ で $m=30$、$n^7-n$ なら $p-1\mid 6$ の $2,3,7$ で $m=42$。

別解

別解 — フェルマーの小定理で $5$ の倍数を一撃(得意な人向けの高い視点)。 $2,3$ の倍数は連続 $3$ 整数の積 $(n-1)n(n+1)$ から。$5$ の倍数を、余りの場合分けでなくフェルマーの小定理で示す。

フェルマーの小定理: $5$ が素数だから、すべての整数 $n$ で $n^5\equiv n(\mathrm{mod}5)$。すなわち $n^5-n\equiv 0(\mathrm{mod}5)$、$n^5-n$ は $5$ の倍数。

$2$ の倍数: $(n-1)n$ に連続 $2$ 整数があるから偶数。$3$ の倍数: $(n-1)n(n+1)$ に連続 $3$ 整数があるから。$5$ の倍数: 上のフェルマー。

$2,3,5$ は互いに素だから、これらすべての倍数 $=30$ の倍数。

$5$ の倍数を「$n$ を $5$ で割った余り $0,1,2,3,4$ で場合分け」する本解に対し、フェルマーの小定理 $n^p\equiv n(\mathrm{mod}p)$ を使えば場合分けなしで一発。$n^5-n$ が $30$ の倍数なのは、$2,3,5$ という「小さい素数すべて」でフェルマーが効くからで、$n^7-n$ なら $42=2\cdot 3\cdot 7$ の倍数になる。