2次の漸化式:隣接する3項の最大公約数(2022年東京大学文系数学第3問)

今年の東大では文系数学でも2次の2項間漸化式に関する整数問題が出題されました。こちらは隣接する3項の最大公約数がテーマです。


 

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

(1)$a_{2022}$を$3$で割った余りを求めよ。

(2)$a_{2022}$、$a_{2023}$、$a_{2024}$の最大公約数を求めよ。

(2022年東京大学 文科第3問)

 

 考え方

先日紹介した理系数学の問題と似ていますが、漸化式の形が少し違います。(1)は余りの周期性に着目して解答しますが、東大数学では頻出の発想なので解けた受験生は多かったと思います。(2)は(1)の結果を利用することになりますが、まずは$n$に$2021$などの具体的な値を代入して公約数の候補を絞り込みましょう。


解答例

 

(1)

以下、合同式の法を$\bmod 3$ とする。$$a_1 \equiv \underline{1}$$ $$a_2 \equiv 1^2+\underline{1} \cdot (\underline{1}+2) \equiv \underline{1}$$ $$a_3 \equiv 1^2+2 \cdot (2+2) \equiv 0$$ $$a_4 \equiv 0^2+0 \cdot (0+2) \equiv 0$$ $$a_5 \equiv 0^2+1 \cdot (1+2) \equiv 0$$ $$a_6 \equiv 0^2+2 \cdot (2+2) \equiv 2$$ $$a_7 \equiv 2^2+0 \cdot (0+2) \equiv \underline{1}$$ $$a_8 \equiv 1^2+\underline{1} \cdot (\underline{1}+2) \equiv \underline{1}$$ $$\quad \vdots$$以上より、数列$\{a_n\}$を$3$で割った余りは周期$6$で循環し、$$1,\,1,\,0,\,0,\,0,\,2$$の繰り返しとなる。$2022$は$6$の倍数であるから$$a_{2022} \equiv a_{6} \equiv 2$$となり、$a_{2022}$を$3$で割った余りは$$\color{red}{2}$$と求められる。

 

 

(2)

$$\begin{aligned}
a_{2023}=a_{2022}^{2}+2022 \cdot 2024 \\
a_{2024}=a_{2023}^{2}+2023 \cdot 2025
\end{aligned}$$より、$a_{2023}$と$a_{2022}$の最大公約数は $2022 \cdot 2024$ を割り切り、$a_{2024}$と$a_{2023}$の最大公約数は $2023 \cdot 2025$ を割り切る。ここで、$$\begin{aligned}
&2022=2 \cdot 3 \cdot 337 \\
&2023=7 \cdot 17^{2} \\
&2024=2^{3} \cdot 11 \cdot 23 \\
&2025=3^{4} \cdot 5^{2}
\end{aligned}$$と素因数分解すると、積$2022 \cdot 2024$と$2023 \cdot 2025$の最大公約数は$3$であることが分かる。これより、$a_{2022}$、$a_{2023}$、$a_{2024}$の最大公約数は$3$の約数に限られるが、(1)の結論より$a_{2022}$は$3$の倍数ではないので、求める最大公約数は$$\color{red}{1}$$である。

 


 

昨年の整数問題よりはシンプルな設定で、登場する文字の数も少ないので解きやすかったのではないかと思います。3つの整数の最大公約数を求める際は、いずれか2組の最大公約数を求めてから、さらにその2数の最大公約数を求める、という手順を踏むのが定石です。$2022$は$2 \cdot 3 \cdot 337$と素因数分解できますが、$337$が少し大きめの素数なので注意。年号が絡む整数問題はしばしば出題されます(今年も多くの大学で$2022$という数字が登場しています)。直前で$2022$の素因数を確認していた人はラッキーでしたね。

また、求める最大公約数の素因数$p$を仮定すれば、$2022$~$2025$を素因数分解しなくても解答可能です。$2022$と$2024$、$2023$と$2025$のそれぞれの組の少なくとも一方は$p$の倍数であることが必要ですが、最大でも$2022$と$2025$の差である$3$より大きな素因数は公約数になり得ないことが言えます。ここから、3項の最大公約数は$3$の約数に限られることが分かります。これはユークリッドの互除法の理屈が分かっていれば思い付くことのできる解法でしょう。

最後の詰めでは(1)のヒントが上手い具合に効いてきます。理系数学に出題する場合は誘導設問を付けずに(2)単体の出題でも良いかもしれません。理系数学の問題も演習問題としてちょうど良いレベルなのでさらっておくと良いでしょう。

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

3項の最大公約数は高々$3$なので、(1)の考察から分かるように、$a_{n}$、$a_{n+1}$、$a_{n+2}$の最大公約数が$3$となるのは $n=6k+2$($k$は非負整数)と表せる場合に限ります。したがって、$a_{2024}$、$a_{2025}$、$a_{2026}$であれば、最大公約数は$3$となります。

コメントを残す

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