2次漸化式に関する整数問題(2022年東京大学理系数学第2問)

今年も2次試験のシーズンがやってきました。今年の東大理系数学では2次の漸化式に関する整数問題が出題されました。因みに、2次の漸化式は英語で “quadratic recurrence (equation)” などと呼ばれます。


 

数列 $\left\{a_{n}\right\}$ を次のように定める。$$a_{1}=1, \quad a_{n+1}=a_{n}^{2}+1 \quad(n=1,2,3, \cdots \cdots)$$

(1)正の整数$n$が$3$の倍数のとき, $a_{n}$は$5$の倍数となることを示せ。

(2)$k$, $n$を正の整数とする。$a_{n}$が$a_{k}$の倍数となるための必要十分条件を$k$, $n$を用いて表せ。

(3)$a_{2022}$と$\left(a_{8091}\right)^{2}$の最大公約数を求めよ。

(2022年東京大学 理類第2問)

 

 考え方

漸化式を題材とする整数問題は2017年以来5年ぶりです。さすがに二項係数は関連問題が2年続いたのでお休みのようですね。本問は誘導が丁寧なのでぜひ完答したい問題でした。

いきなり(2)を出題すると歯が立たない受験生が続出すると踏んだのか、(1)の誘導を付けることでかなり親切な問題になっています。今年のセットの中では最も取っ付きやすい問題だと言えるでしょう。(3)は難しそうに見えますが、(2)のヒントが大いに効いてきます。$a_{8088}$が$a_{2022}$で割り切れることに気が付けば、あとは難しくありません。


解答例

 

(1)

以下、合同式の法を$\bmod 5$ とする。$$a_1 \equiv \underline{1}$$ $$a_2 \equiv 1^2+1=2$$ $$a_3 \equiv 2^2+1 \equiv 0$$ $$a_4 \equiv 0^2+1 \equiv \underline{1}$$ $$\quad \vdots$$以上より、数列$\{a_n\}$を$5$で割った余りは周期$3$で循環する。これより、$a_n \equiv 0\pmod 5$ となるのは$n$が$3$の倍数のときであり、またそのときに限る。よって示された。

 

 

(2)

正の整数$N$について $a_{N} \equiv 0 \pmod{a_{k}}$ が成り立つとすると、
$$\begin{aligned} a_{N+1} & \equiv 0+1 \pmod{a_{k}} \\ &=1\left(=a_{1}\right) \\ a_{N+2} & \equiv 1^{2}+1 \pmod{a_{k}} \\ &=2\left(=a_{2}\right) \\ a_{N+3} & \equiv 2^{2}+1 \pmod{a_{k}} \\ &=5\left(=a_{3}\right) \\ & \quad \vdots \end{aligned}$$となる。よって与漸化式を逐次用いることにより、$j\ (\leqq k)$ を正の整数として$$a_{N+j} \equiv a_j \pmod{a_{k}} \quad \cdots ①$$が導かれる。

 

ここで、$a_{j} \equiv 0 \pmod{a_{k}}$ となるのは $j=k$ の場合であること、および、$n$を$1$から増加させていったときに$a_n$が初めて$a_k$で割り切れるのが $n=k$ の時点であることに注意すると、$①$式より$n$が$k$の倍数であるとき常に$$a_{n} \equiv 0 \pmod{a_{k}}$$が成り立つ。

 

逆に、$a_{n} \equiv 0 \pmod{a_{k}}$ が成り立つ($a_{n}$が$a_{k}$の倍数となる)とき、$n=qk+r$($q,r \in \mathbb Z$, $0 < r \leqq k$)と置けば、$①$式において $N \to qk$、$j \to r$ と置き換えることにより$$(a_{n}=)\ a_{qk+r} \equiv a_{r} \equiv 0 \pmod{a_{k}} \quad \cdots ②$$を得る。$②$式を満たすような$r$は $0 < r \leqq k$ の範囲で $r=k$ のみであるが、これは$n$が$k$の倍数となることを意味する。

 

以上より、$a_{n}$が$a_{k}$の倍数となるための必要十分条件は、「$n$が$k$の倍数であること」である。

 

 

(3)

まず(2)の結論から、$a_{8088}$が$a_{2022}$で割り切れることが従う。これより、$$\begin{aligned} a_{8089} &=a_{8088}^{2}+1 \\ &\equiv 1 \pmod{a_{2022}} \\ a_{8090} &\equiv 1^{2}+1 \pmod{a_{2022}} \\ &= 2 \\ a_{8091} & \equiv 2^{2}+1 \pmod{a_{2022}} \\ &=5 \end{aligned}$$となるので、$$\left(a_{8091}\right)^{2} \equiv 25 \pmod{a_{2022}}$$を得る。これより、$a_{2022}$と$\left(a_{8091}\right)^{2}$の最大公約数は $25$、$5$、$1$ のいずれかに限られる。

 

ここで$2022$と$8091$がともに$3$の倍数であることに注目すると、(1)より $a_{2022}$と$a_{8091}$はともに$5$の倍数でなる。

 

また、$$\begin{aligned} a_{1} & \equiv \underline{1} \pmod{25} \\ a_{2} & \equiv 2 \pmod{25} \\ a_{3} & \equiv 5 \pmod{25} \\ a_{4} & \equiv 5^2+1 \equiv \underline{1} \pmod{25} \\ & \quad \vdots \end{aligned}$$となるから、数列$\{a_n\}$を$25$で割った余りは周期$3$で循環し、どの項も$25$で割り切れることはない。よって$a_{2022}$は$5$の倍数ではあるが$25$の倍数でないので、求める$a_{2022}$と$\left(a_{8091}\right)^{2}$の最大公約数は$$\color{red}{5}$$である。

 


 

昨年よりはヒントの使いどころが分かりやすい整数問題だったと思います。あまり時間を掛けないで解きたい問題でした。$a_{n}$が$a_{k}$の倍数となるための必要十分条件が「$n$が$k$の倍数であること」という現象は、他の数列でも成立することがあります。例えばフィボナッチ数列などはその代表的な例でしょう。また、(1)と(2)は数学的帰納法を用いて解答することもできます。

(2)で $0 < r \, \color{red}{\leqq k}$ と置いているのは $a_0$ を避けるためですが、$a_1=a_0^2+1$ から $a_0=0$ と定義してやれば素直に $0 \leqq r < k$ と置くこともできます。

因みに、この漸化式は「高さが$n$以下の二分木の総数」を与えることが知られており、オンライン整数列大辞典「OEIS」においてA003095として登録されています。また、この式はジュリア集合やマンデルブロ集合の生成式と共通しています。

今年も全体的に解析色の強いセットでした。特筆すべきは5年ぶりに帰ってきた確率分野からの出題でしょうか。本来であれば確率は東大数学では頻出の分野なのでしっかり対策しておくべきです。個人的に面白そうだと思ったのが第5問の立体図形の問題です。$z$軸周りの対称性を上手く考慮して計算量をどれだけ減らせるかが腕の見せ所と言えます。第3問、第4問はパッと見た感じ、解答が面倒そうです。

“2次漸化式に関する整数問題(2022年東京大学理系数学第2問)” への1件の返信

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です