非線形漸化式と公約数 – 2022年東大 数学 第2問

　2022年東大 数学 第2問は非線形漸化式の問題です。一般に非線形漸化式は一般項を求めるのが困難なので、必然的に難易度が上がります。問題文は以下のとおりで、東大2次試験からの引用です。

　非線形漸化式の問題ですが整数列の約数に関する問題なので、剰余類を使えば案外何とかなるかもしれません。本問のように小問がたくさんある場合は最初の方は解きやすいことが多いので、取りこぼさないようにしましょう。なお、本稿の内容は東大が発表したものではありません。

2022年東大 数学 第2問 小問1の解法

　まず実際に計算して傾向を見ましょう。

\begin{aligned}
a_1 = & 1 \\
a_2 =  & 2 \\
a_3 =  & 5 \\
a_4 = & 26 
\end{aligned}

a₅ 以降は計算が面倒くさくなったので確認していませんが、確かに a₃ は5の倍数です。

　5で割り切れるかどうかが問題なので、5を法とする剰余類を考えます。すると

\begin{aligned}
a_1 \equiv & 1 &  (  \mod 5 )\\
a_2 \equiv  & 2 &  (  \mod 5 ) \\
a_3 \equiv  & 0 &  (  \mod 5 ) \\
a_4  \equiv & 1 &  (  \mod 5 )
\end{aligned}

　これは案外

\begin{aligned}
a_{3m-2} \equiv & 1 &  (  \mod 5 )\\
a_{3m-1} \equiv  & 2 &  (  \mod 5 ) \\
a_{3m} \equiv  & 0 &  (  \mod 5 ) \\
 & &(m = 1,2,\cdots)
\end{aligned}

が成り立ちそうです。そこで a_3m ≡ 0 (mod 5) を数学的帰納法で証明します。

　 m = 1 のときは上で確認したとおり成り立ちます。

　m = k (k ≧ 1) のときに成り立つと仮定するとき、

\begin{aligned}
a_{3k+1}  &= a_{3k}^2 +1 \equiv  1  (  \mod 5 )\\
a_{3k+2 }  & =a_{3k+1}^2 +1  \equiv 1+1 \equiv 2  (  \mod 5 ) \\
a_{3k+3} & =a_{3k+2}^2 +1 \equiv  4+1 \equiv0   (  \mod 5 ) \\

\end{aligned}

であり、 m = k+1 のときに a_3m ≡ 0 (mod 5) が成り立つので、m ≧ 1のとき a_3m ≡ 0 (mod 5) であることが証明できました。

2022年東大 数学 第2問 小問2の解法

　まず n > k ならば a_n > a_k であり、逆もまた正しいので、a_n​ が a_k​ の倍数（2倍以上）ならば n > k が成り立ちます。

　 a_n が a_k で割り切れるかどうかを問題にしているので、今度は a_k を法とする剰余類を考えてみましょう。

\begin{aligned}
a_{k+1}  &= a_{k}^2 +1 \equiv  1  (  \mod a_k )\\
a_{k+2 }  & =a_{k+1}^2 +1  \equiv 1+1 \equiv 2  (  \mod a_k ) \\
a_{k+3} & =a_{k+2}^2 +1 \equiv  4+1 \equiv5   (  \mod a_k ) \\

\end{aligned}

ですが、これは明らかに

\begin{aligned}
a_{k+m} \equiv a_m (\mod a_k )\\
(m=1,2, \cdots)
\end{aligned}
\cdots (1)

が成り立ちそうです。これを数学的帰納法で証明します。

　m = 1 のときは明らかに成り立ちます。

　m = j (j ≧ 1) のときに成り立つと仮定するとき、ある自然数 l が存在して

a_{k+j} = la_k +a_j

が成り立ちます。このとき

\begin{aligned}
a_{k+j+1} =  &a_{k+j}^2 +1 \\
 = & (la_k +a_j)^2 +1 \\
 = & l^2 a_k^2 + 2la_ka_j + a_j ^2  +1 \\
 = & (l^2 a_k + 2la_j )a_k + a_{j+1} \\
 \equiv & a_{j+1} ( \mod a_k)
\end{aligned}

が成り立つので、 a_k+m ≡ a_m (mod a_k) であることが証明できました。

　よって、1 ≦ m < k ならば 0 < a_m < a_k なのでa_m は a_k で絶対に割り切れません。すなわち

a_{k+m} \not\equiv 0 ( \mod a_k)

です。

　また、 m = k ならば

\begin{aligned}
a_{2k} \equiv a_k \equiv 0  (\mod a_k ) \\

\end{aligned}

です。 m =2k ならば

\begin{aligned}
a_{3k} \equiv a_{2k} \equiv 0  (\mod a_k ) \\

\end{aligned}

です。以下、帰納的に

\begin{aligned}
a_{dk}  \equiv 0  (\mod a_k ) \\
(d = 1,2, \cdots)

\end{aligned}

が成り立ちます。

　したがって n が k で割り切れない、すなわち n = dk + m (d=1,2,…, 1 ≦ m ≦ k-1 ) ならば

\begin{aligned}
a_{dk+m} \equiv a_{m}   \not\equiv 0 (\mod a_k ) \\

\end{aligned}

であり、n が k で割り切れる、すなわち n = dk (d=1,2,…) ならば

\begin{aligned}
a_{dk}   \equiv 0 (\mod a_k ) \\

\end{aligned}

が成り立ちます。

　ゆえにa_n​ が a_k​ の倍数となる、すなわち a_n ≡ 0 ( mod a_k ) であるための必要十分条件は n が k で割り切れることです。

2022年東大 数学 第2問 小問3の解法

　a₂₀₂₂​ と (a₈₀₉₁​)² の最大公約数を求ろとか、実際の数字を計算できないのに何無茶言ってんだよ、とも思いますが、ここで2022と8091が3の倍数であることに気が付きましょう。すると小問1の結果が応用できて、a₂₀₂₂​ も a₈₀₉₁ も5の倍数です。少なくとも5は公倍数であることがわかりました。

　小問2の結果も応用できないか、考えてみます。残念ながら8091は2022の倍数ではありませんが、 8091 ≡ 3 (mod 2022) なので、小問2を解くときに得られた式(2)により、

a₈₀₉₁ ≡ a₃ (mod 2022)

が成り立ちます。

　a₃ = 5 なので

a₈₀₉₁ ≡ 5 (mod 2022)

です。よって

(a₈₀₉₁)² ≡ 25 (mod 2022)

なので、ある自然数 n が存在して

(a₈₀₉₁)² = na₂₀₂₂ + 25

です。したがって a₂₀₂₂​ と (a₈₀₉₁​)² の最大公約数 c は25の約数であることがわかります。実際、ある自然数 p,q が存在して

a₂₀₂₂ = pc
a₈₀₉₁​ = qc

が成り立つので、

(a₈₀₉₁)² – na₂₀₂₂ = q²c² – npc = (q²c – np) c = 25

ですが、q²c – np は整数でしかも正の値なので（もし負なら c も負になってしまう）、 c が25の約数であることがわかります。

　5 が a₂₀₂₂​ と a₈₀₉₁ の公約数であることがわかっているので、c = 1 ということはありません。 c は5か25のいずれかです。もし a₂₀₂₂​ ≡ 0 (mod 25) なら c = 25 ですが、 a₂₀₂₂​ の値を実際に計算することはまず無理なので、なんとも言えません。

　ところが、ここで a₄ = 26 ≡ 1 (mod 25) であることに気がつけると、

\begin{aligned}
a_{3m-2} \equiv & 1 &  (  \mod 25 )\\
a_{3m-1} \equiv  & 2 &  (  \mod 25 ) \\
a_{3m} \equiv  & 5 &  (  \mod 25 ) \\
 & &(m = 1,2,\cdots)
\end{aligned}

ではないだろうかとの予想が立てられます。こいつに気がつければ、あとは小問1のときと同様に a_3m ≡ 5 (mod 25) であることを数学的帰納法で証明するだけです。

　 m = 1 のときは上で確認したとおり成り立ちます。

　m = k (k ≧ 1) のときに成り立つと仮定するとき、

\begin{aligned}
a_{3k+1}  &= a_{3k}^2 +1 \equiv  25 + 1 \equiv 1  (  \mod 25 )\\
a_{3k+2 }  & =a_{3k+1}^2 +1  \equiv 1+1 \equiv 2  (  \mod 25 ) \\
a_{3k+3} & =a_{3k+2}^2 +1 \equiv  4+1 \equiv 5   (  \mod 25 ) \\

\end{aligned}

であり、 m = k+1 のときに a_3m ≡ 5 (mod 25) が成り立つので、m ≧ 1のとき a_3m ≡ 5 (mod 25) であることが証明できました。

　ゆえに a₂₀₂₂​ ≡ 5 (mod 25) であり、 a₂₀₂₂​ は25で割り切れないので最大公約数は5です。

解法のポイント

「何かの倍数」「最大公約数」など、約数に絡む問題が出たら、まずは剰余類で何とかならないか、試してみましょう。

　剰余類を適用する際のキモは何を法にするかですが、大抵は割り切れる数（小問1の5）や公約数の候補（小問3の25）を採用すればピタッとハマります。

　また、公約数を求める問題では小問2の

(a₈₀₉₁)² – na₂₀₂₂ = (q²c – np) c = 25

のような式を導出すれば、最大公約数 c は25の約数であることが直ちに求められます。このやり方は覚えておきましょう。