【整数問題】a_1=1 , a_n+1=a_n^2+1のとき a_2022と(a_8091)^2の最大公約数を求めよ(2022・東京大学・理科)

整数

今回は、「整数問題(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\) を考える

(1)解説

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}\) を考える

(2)解説

\(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}\)を考える

(3)解説

(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}\)が5の倍数かチェック

(1)より2022は3の倍数なので、\(a_{2022}\) は 5の倍数

\(a_{2022}\)が25の倍数かチェック

\begin{array}{|c|c|c|} \hline n & 1 & 2&3&4&5&6&\cdots \\ \hline a_n\pmod{25} &1&2&5&1&2&5&\cdots \\ \hline \end{array}

25で割ったあまりは、1,2,5 と繰り返すので、\(a_{2022}\)は25の倍数ではない

\(a_{2022}\) と 25 の最大公約数は 5

したがって

\((a_{8091})^2\) と \(a_{2022}\) の最大公約数は 5

補足:合同式

合同式は「あまりに注目した等式」です。

整数問題では強力な武器になります。以下の記事を参考にしてください。

整数問題(2022・東京大学・文科)を以下の記事で解説しています。

まとめ:整数問題(2022・東京大学・理科)

「整数問題(2022・東京大学)」の解説まとめは以下の通りです。

  • 「あまり」に注目する(合同式利用)
  • 周期性に気づくことが大切
  • 互助法を利用して、最大公約数を求める

「整数問題(2022・東京大学)」の解説まとめは以上でおわります。

少しでも勉強の参考になれば幸いです。それではまた。

コメント

タイトルとURLをコピーしました