問題
\(n \in \mathbb{N}\)の時、\(4^n-1\)は３で割り切れることを示せ。
コメント
ある数から１を引いた問題。１を引いたり足したりすることで、素因数分解の状況ががらりと変わる。
２０項まで計算してみると、
\( 4^{1} -1= 3 = 3 * 1\)
\( 4^{2} -1= 15 = 3 * 5\)
\( 4^{3} -1= 63 = 3 * 21\)
\( 4^{4} -1= 255 = 3 * 85\)
\( 4^{5} -1= 1023 = 3 * 341\)
\( 4^{6} -1= 4095 = 3 * 1365\)
\( 4^{7} -1= 16383 = 3 * 5461\)
\( 4^{8} -1= 65535 = 3 * 21845\)
\( 4^{9} -1= 262143 = 3 * 87381\)
\( 4^{10} -1= 1048575 = 3 * 349525\)
\( 4^{11} -1= 4194303 = 3 * 1398101\)
\( 4^{12} -1= 16777215 = 3 * 5592405\)
\( 4^{13} -1= 67108863 = 3 * 22369621\)
\( 4^{14} -1= 268435455 = 3 * 89478485\)
\( 4^{15} -1= 1073741823 = 3 * 357913941\)
\( 4^{16} -1= 4294967295 = 3 * 1431655765\)
\( 4^{17} -1= 17179869183 = 3 * 5726623061\)
\( 4^{18} -1= 68719476735 = 3 * 22906492245\)
\( 4^{19} -1= 274877906943 = 3 * 91625968981\)
\( 4^{20} -1= 1099511627775 = 3 * 366503875925\)
となり３で割り切れていることが確認できる。
指数関数なので、あっという間に数値が大きくなってしまい、なかなか検証が難しく、指数関数はなにかと扱いにくい。
単純な問題だが、数の構造を調べるためには手頃な問題だろう。
解答１
因数分解する。
\(4^n-1=(2^n+1)(2^n-1)\)
\(2^n\)は、３で割り切れないから\(m\)を自然数として、\(3m+1\)か\(3m-1\)と表すことができる。
(1) \(2^n = 3m+1\)の場合
\(4^n-1=(2^n+1)(2^n-1)=(3m+2)(3m)\)から３で割り切れる。
(2) \(2^n = 3m-1\)の場合
\(4^n-1=(2^n+1)(2^n-1)=(3m)(3m-2)\)から３で割り切れる。
以上より、いずれの場合も３で割り切れる。■
コメント
因数分解の式から、
\( 4^{1} -1= (3*1) * 1 \)
\( 4^{2} -1= 5 * (3*1) \)
\( 4^{3} -1= (3*3) * 7 \)
\( 4^{4} -1= 17 * (3*5) \)
\( 4^{5} -1= (3*11) * 31 \)
\( 4^{6} -1= 65 * (3*21) \)
\( 4^{7} -1= (3*43) * 127 \)
\( 4^{8} -1= 257 * (3*85) \)
\( 4^{9} -1= (3*171) * 511 \)
\( 4^{10} -1= 1025 * (3*341) \)
と分解されていることがわかる。
解答２
数学的帰納法で証明する。
ｎ=1のときは、\(4^n-1=4-1=3\)で成立している。
n=kのとき成立していると仮定すると、\(4^k-1=3m\)となる自然数\(m\)が存在する。
n=k+1のときは、
\(4^{k+1}-1=4 \cdot 4^k-1=4 \cdot (3m+1) -1 = 12m+3=3(4m+1)\)
となって3で割り切れる。■
コメント
解答３
3を法として考える。
\(4^n-1 ≡ 1^n-1 =0 \) \(( mod \, 3)\) ■
コメント
いろいろな解き方があるということ。
