今回は、「整数問題(2022・東京大学・理科)」について解説します。
この記事を読むと、
- 整数問題(2022・東京大学・理科)の解法
- 合同式を使った解法
について理解できます。
この記事は「わか」が執筆しています。
私「わか」(https://twitter.com/wakkachan2019)は、国立大学数学科を卒業後、数学教育に10年以上関わっています。
問題:整数問題(2022・東京大学・理科)
数式 \({a_n}\) を次のように定める。
$$a_1=1 , a_{n+1}=a_n^2+1 (n=1,2,3,\cdots)$$
(1) 正の整数 \(n\) が \(3\)の倍数のとき、 \(a_n\) は \(5\)の倍数となることを示せ。
(2) \( k , n \) を正の整数とする。\(a_n\) が \(a_k\) の倍数となるための必要十分条件を\( k , n \) を用いて表せ。
(3) \(a_{2022}\) と \(a_{8091}\) の最大公約数を求めよ。
(2022・東京大)
解説:整数問題(2022・東京大学・理科)
とりあえず実験
$$a_1=1$$
$$a_2=1^2+1=2$$
$$a_3=2^2+1=5$$
$$a_4=4^2+1=26$$
$$a_5=26^2+1=677$$
$$a_6=677^2+1=458300$$
すぐに数が大きくなってしまうので、具体的に計算するのは大変です、、、。
(1)解説:\(\pmod5\) を考える
5の倍数であることを示すので mod5 を考える
$$a_1\equiv1\pmod5$$
$$a_2\equiv1^2+1\equiv2\pmod5$$
$$a_3\equiv2^2+1\equiv5\equiv0\pmod5$$
$$a_4\equiv0^2+1\equiv1\pmod5$$
$$a_5\equiv1^2+1\equiv2\pmod5$$
$$a_6\equiv2^2+1\equiv5\equiv0\pmod5$$
\begin{array}{|c|c|c|} \hline n & 1 & 2&3&4&5&6&\cdots \\ \hline a_n\pmod5 &1&2&0&1&2&0&\cdots \\ \hline \end{array}
\(a_n\) は、5で割ったあまりが 1,2,0 と繰り返すので
nが3の倍数のとき、\(a_n\) は5の倍数
(2)解説:\(\pmod{a_k}\) を考える
\(a_n=a_k\) のとき、1倍で倍数になっている
数列\({a_n}\) は単調増加であり \(a_1=1\) より
最初に\(a_n\) が \(a_k\) の倍数となるのは \(n=k\) のとき
\(n\)を\(k+1,k+2,k+3,\cdots\)と増やしたとき、倍数になる時を考える
次に \(a_n\) が \(a_k\) の倍数となるときを考える
\(mod{a_k}\) を考えて
$$a_{k+1}\equiv a_{k}^2+1\equiv0^2+1\equiv1\pmod{a_k}$$
$$a_{k+2}\equiv a_{k+1}^2+1\equiv1^2+1\equiv2\pmod{a_k}$$
$$a_{k+3}\equiv a_{k+2}^2+1\equiv2^2+1\equiv5\pmod{a_k}$$
\(\cdots\)
\begin{array}{|c|c|c|} \hline n & 1 & 2&3&\cdots&k-1&k&k+1&k+2&k+3&\cdots&k+k=2k&2k+1&2k+2&\cdots \\\hline a_n &1&2&5&\cdots&a_{k-1}&a_k&a_{k+1}&a_{k+2}&a_{k+3}&\cdots&a_{k+k}=a_{2k}&a_{2k+1}&a_{2k+2}&\cdots\\ \hline a_n\pmod{a_k} &1&2&5&\cdots&a_{k-1}&0&1&2&5&\cdots&a_k\equiv0&1&2&\cdots \\ \hline \end{array}
\(a_n\) は \(a_k\) で割ったあまりが
\(\underbrace{1,2,5,\cdots ,a_{k-1},0}_{k個},\underbrace{1,2,5\cdots,0}_{k個},\cdots\) と繰り返す
したがって
「\(a_n\) が \(a_k\) の倍数」となるための必要十分条件は「 n は k の倍数」
(3)解説:\(\pmod{2022}\)を考える
(2)より
$$a_{8088}\equiv a_{2022\times4}\equiv 0\pmod {a_{2022}}$$
$$a_{8089}\equiv a_{8088}^2+1\equiv 1\pmod {a_{2022}}$$
$$a_{8090}\equiv a_{8089}^2+1\equiv 2\pmod {a_{2022}}$$
$$a_{8091}\equiv a_{8090}^2+1\equiv 5\pmod {a_{2022}}$$
\(a_{8091}\equiv5\pmod{a_{2022}}\)を使う
\((a_{8091})^2\equiv25\pmod{a_{2022}}\)
$$(a_{8091})^2=a_{2022}\times X+25 (X:整数)$$
ユークリッド互除法を使う
\((a_{8091})^2\) と \(a_{2022}\) の最大公約数は
\(a_{2022}\) と 25 の最大公約数と一致する
解の候補は 1 , 5 , 25
\(a_{2022}\) と 25 の最大公約数は 5
したがって
\((a_{8091})^2\) と \(a_{2022}\) の最大公約数は 5
補足:合同式
合同式は「あまりに注目した等式」です。
整数問題では強力な武器になります。以下の記事を参考にしてください。
整数問題(2022・東京大学・文科)を以下の記事で解説しています。
まとめ:整数問題(2022・東京大学・理科)
「整数問題(2022・東京大学)」の解説まとめは以下の通りです。
- 「あまり」に注目する(合同式利用)
- 周期性に気づくことが大切
- 互助法を利用して、最大公約数を求める
「整数問題(2022・東京大学)」の解説まとめは以上でおわります。
少しでも勉強の参考になれば幸いです。それではまた。
コメント