算数のお時間
今日は珍しく Facebook の TL から。
たぶんお子さんの夏休みの宿題かな。 対象は中学2年生らしい。 問題はこんな感じ。
3の累乗の計算の結果は，
$3^{100}$ を計算した数の一の位の数を答えなさい。
例を眺めて1の位が 3, 9, 7, 1, 3, 9, … と4つの値で循環してることに気づけば， $3^{100} = 3^{(4\cdot25)}$ なので，1の位が1になることは直感的に分かる。 中学生の回答としてはこれでOK？ でも，もう少し数学っぽく記述してみたいよね。
合同式を使って書く
計算結果の1の位に注目するということは，10で割った余りを求めることと同じである。 つまり問題は
を解くことと同じである。 3の100乗は
であり，このうち $3^4$ に注目すると，問題文より
なので
と書ける。
数学的帰納法を使って書く
この問題を更に一般化してみよう。 つまり $0$ 以上の任意の整数 $k$ に対して
| $n$ | $3^n \bmod {10}$ |
|---|---|
| $4k$ | $1$ |
| $4k+1$ | $3$ |
| $4k+2$ | $9$ |
| $4k+3$ | $7$ |
が成り立つことを示せればいい。
まず $k=0$ のときは問題文より
| $n$ | $3^n \bmod {10}$ |
|---|---|
| $0$ | $1$ |
| $1$ | $3$ |
| $2$ | $9$ |
| $3$ | $7$ |
となることは明らか。
ある $k$ で上が成立すると仮定した場合， $k+1$ のときも成立することを示す。 まず $3^{4(k+1)}$ について
となり $3^{4(k+1)} \equiv 1 \pmod{10}$ も成り立つことが分かる。 続けて
と残りのケースも成り立つことに分かる（直前の合同式の結果を用いて計算している点に注目）。 これにより $0$ 以上の任意の整数 $k$ に対して
| $n$ | $3^n \bmod {10}$ |
|---|---|
| $4k$ | $1$ |
| $4k+1$ | $3$ |
| $4k+2$ | $9$ |
| $4k+3$ | $7$ |
が成り立つと言える。 以上より $3^{100} = 3^{4\cdot25} \equiv 1 \pmod{10}$ と計算できる。
オイラーの定理を使って書く
他に面白い解き方がないかなぁ，と Kagi Assistant に訊いてみたら，オイラーの定理を使った解法を教えてもらった。
オイラーの定理とは，互いに素（最大公約数が $1$ のみ）な整数 $a$ と $n$ に対して
が成り立つというもの1。 ここで $\varphi(n)$ はオイラーの totient 関数と呼ばれるもので，$1$ から $n$ までの整数のうち $n$ と互いに素なものの個数を表す。
$3$ と $10$ は互いに素で，かつ $\varphi(10) = \varphi(2)\varphi(5) = 4$ なので，オイラーの定理より
が保証されているということらしい。 あとは前節までの記述に従って
と書ける。
オイラーの定理は思いつかんかったわ。
中学生はどうやって書く？
オイラーの定理は中学生は習ってないよね，たぶん。 合同式や数学的帰納法は習ってるっけ？ まぁ，いいか。 習ってないなら，これを夏休みの自由研究にしてしまえ（笑）
参考
- 数学ガールの秘密ノート／整数で遊ぼう
- 結城 浩 (著)
- SBクリエイティブ 2013-12-17 (Release 2014-07-24)
- Kindle版
- B00L0PDMJ0 (ASIN)
- 評価
[Comment] 小中学生にお薦め。小学生高学年くらいならギリで理解可能と思われ。
- 数学ガール／フェルマーの最終定理
- 結城 浩 (著)
- SBクリエイティブ 2008-07-29 (Release 2014-03-12)
- Kindle版
- B00I8AT1CM (ASIN)
- 評価
[Comment] 「フェルマーの最終定理」というサブタイトルをみたとき「なんちう大風呂敷を広げるねん」と思ったものだが，実際に読んでみるとぐいぐい引き込まれる。ひっさびさに頭を使ったような気がする。