問題
任意の整数\( n \)に対し, \( n^9 – n^3 \)は\( 9 \)で割り切れることを示せ。
発想
まずは実験してもよいが, \( 9 \)乗が大変そうである。因数分解ができるのでまずは因数分解を行う。
\( 9 \)で割り切れることを示すので, \( 9 \)の剰余系か, \( 3 \)の剰余系で何とかなるはず。よって方針としては, \( 3 \)の剰余系で示せそうならそれで, 難しそうなら時間はかかるが\( 9 \)の剰余系の場合分けでごり押す。
下書き
\begin{eqnarray}
n^9 – n^3 &=& n^3(n^6 – 1) = n^3(n^3 + 1)(n^3 – 1) \cdots ①\\
&=& n^3(n+1)(n^2-n+1)(n-1)(n^2+n+1) \cdots ②
\end{eqnarray}
3の剰余系で頑張る
\( \bmod \)を使うと, \( \bmod 3 \)では\( 9 \)で割り切ることを示せないので, \( n = 3k, 3k+1, 3k+2 \)(\( k \)は整数)の方式でやる。
\( n = 3k \)のときは, \( n^3 \)の部分が\( 27k^3 \)となるので, 確かに\( 9 \)の倍数。
\( n = 3k+1 \)のときは, まず\( n-1 \)の部分が\( 3k \)となるので, \( 3 \)の倍数。
あとひとつ, \( 3 \)の倍数の部分を探せばよいが, \( (n^2-n+1) \)と\( (n^2+n+1) \)を計算すると, \( (n^2+n+1) \)の方が\( 3(3k^2 + 3k + 1) \)となるので, \( 3 \)の倍数。
よって, \( 9 \)の倍数。
\( n = 3k+2 \)のときは, まず\( n+1 \)の部分が\( 3(k+1) \)となるので, \( 3 \)の倍数。
あとひとつ, \( 3 \)の倍数の部分を探せばよいが, まだ使ってない\( (n^2-n+1) \)が\( 3 \)の倍数になるだろうからそちらから計算すると, \( 3(3k^2 + 3k + 1) \)となるので, \( 3 \)の倍数。
よって, \( 9 \)の倍数。
以上で示せた。
よく見ると, \( n^9 – n^3 = n^3(n+1)(n^2-n+1)(n-1)(n^2+n+1) \)②まで因数分解せずとも, \( n^9 – n^3 = n^3(n^3 + 1)(n^3 – 1) \)①までの因数分解で良さそう。
また解答例では, \( n = 3k \pm 1 \)とまとめて書いてみた。
9の剰余系でごり押し
\( \mod 9 \)を使って, \( 9 \)個の場合分けで示す。場合分けが多くなるが, 確実に完答できるやり方なので, この考え方も大切。
(i) \( n \equiv 0 \pmod 9 \)のとき
\( n^9 – n^3 \equiv 0^9 – 0^9 = 0 \pmod 9 \)
(ii) \( n \equiv 1 \pmod 9 \)のとき
\( n^9 – n^3 \equiv 1^9 – 1^9 = 0 \pmod 9 \)
(iii) \( n \equiv 2 \pmod 9 \)のとき
\( n^3 \equiv 8 \equiv -1 \pmod 9 \)より,
\( n^9 – n^3 \equiv (n^3)^3 – (-1) \equiv (-1)^3 + 1 = 0 \pmod 9 \)
(iv) \( n \equiv 3 \pmod 9 \)のとき
\( n^2 \equiv 9 \equiv 0 \pmod 9 \)より,
\( n^9 – n^3 \equiv (n^2)^4 \cdot n – n^2 \cdot n \equiv 0 – 0 = 0 \pmod 9 \)
(v) \( n \equiv 4 \pmod 9 \)のとき
\( n^3 \equiv 64 \equiv 1 \pmod 9 \)より,
\( n^9 – n^3 \equiv (n^3)^3 – 1 \equiv 1 – 1 = 0 \pmod 9 \)
(vi) \( n \equiv 5 \pmod 9 \)のとき
\( n^3 \equiv 125 \equiv -1 \pmod 9 \)より,
\( n^9 – n^3 \equiv (n^3)^3 – (-1) \equiv (-1)^3 + 1 = 0 \pmod 9 \)
(vii) \( n \equiv 6 \pmod 9 \)のとき
\( n^2 \equiv 36 \equiv 0 \pmod 9 \)より,
\( n^9 – n^3 \equiv (n^2)^4 \cdot n – n^2 \cdot n \equiv 0 – 0 = 0 \pmod 9 \)
(viii) \( n \equiv 7 \pmod 9 \)のとき
\( n^3 \equiv 343 \equiv 1 \pmod 9 \)より,
\( n^9 – n^3 \equiv (n^3)^3 – 1 \equiv 1 – 1 = 0 \pmod 9 \)
(ix) \( n \equiv 8 \pmod 9 \)のとき
\( n^2 \equiv 64 \equiv 1 \pmod 9 \)より,
\( n^9 – n^3 \equiv (n^2)^4 \cdot n – n^2 \cdot n \equiv n – n = 0 \pmod 9 \)
これでもOK。
因数分解を有効活用
\( n^3(n+1)(n^2-n+1)(n-1)(n^2+n+1) \)
と因数分解した時点で, 連続\( 3 \)整数に目が行った人はえらい。
\( \color{red}{(n-1)n(n+1)} \cdot n^2(n^2-n+1)(n^2+n+1) \)
の前半部分は連続\( 3 \)整数の積の形になっているので, 必ず\( 6 \)の倍数。よって, 後半部分がまた別に\( 3 \)の倍数であることを示せば, 全体で\( 9 \)の倍数(\( 18 \)の倍数)であることが示せる。
後半部分を整理すると, \( n^2(n^4+n^2+1) \)となり, これが\( 3 \)の倍数を示せばよいので, 適当に\( n \equiv 0, \pm 1 \pmod 3 \)で場合分けをすれば一瞬で示せる。
解答例1(3の剰余系)
\( n^9 – n^3 = n^3(n^3 + 1)(n^3 – 1) \)
以下, \( k \)は整数とし, (ii)では複合同順とする。
(i) \( n = 3k \)のとき, \( n^3 = 9 \cdot 3k^3 \)より, \( n^3 \)の部分が\( 9 \)の倍数となる。
(ii) \( n = 3k \pm 1 \)のとき, \( n^3 \mp 1 = 9 (3k^3 \pm 3k^2 + k) \)より, \( n^3 \mp 1 \)の部分が\( 9 \)の倍数となる。
以上より, 任意の整数\( n \)に対し, \( n^9 – n^3 \)は\( 9 \)で割り切れる。
解答例2(連続3整数の積に着目)
\( n^9 – n^3 = (n-1)n(n+1) \cdot n^2(n^4+n^2+1) \)
であり, \( (n-1)n(n+1) \)は連続\( 3 \)整数の積だから\( 6 \)の倍数である。
次に, \( n^2(n^4+n^2+1) \)について,
(i) \( n \equiv 0 \pmod 3 \)のとき, \( n^2(n^4+n^2+1) \equiv 0 \pmod 3 \)
(ii) \( n \equiv \pm 1 \pmod 3 \)のとき, \( n^2(n^4+n^2+1) \equiv 3 \equiv 0 \pmod 3 \)
以上より, 任意の整数\( n \)に対し, \( (n-1)n(n+1) \)と\( n^2(n^4+n^2+1) \)がともに\( 3 \)の倍数だから, \( n^9 – n^3 \)は\( 9 \)で割り切れる。
振り返り
どのやり方でもよいので, \( 15 \)分程度で完答してほしい問題。
コメント