2022東京大学・文・第3問【整数問題】3で割った余り、最大公約数

考え方

整数問題の極意は実験

方針が見えない問題においては、まずは具体的な値で実験を行いましょう！

実験 ⇒ 規則・法則を見つける ⇒ 答えの予想

を行うことで、解法の方針が見えてきます。

合同式の利用

『 \(3\) で割った余り 』について考えるので、『 mod 3 』について考えましょう！

実験を行うにしても、ただただ計算をすると数が大きくなって大変です。

合同式を利用することで、煩雑な計算が簡素化され、解答もスッキリします！

※合同式に不安がある方は、下記の記事で合同式について基本的な事柄を確認しています。

合同式とは？合同式の基本性質を理解し、使えるようにする

合同式（基本編）基本的な問題で合同式を使う練習

合同式は整数問題を扱う上で必須アイテムになります。しっかりと使いこなせるようにしておきましょう！

ユークリッド互除法

最大公約数について問われたら、まずはユークリッド互除法を検討したいですね！

(１)具体的に実験から方針を考える

以下すべて、mod 3 として考える．

・\(a_{1}≡1\)

・\(a_{2}≡a^2_{1}+1\times 3≡1\)

・\(a_{3}≡a^2_{2}+2\times 4≡0\)

・\(a_{4}≡a^2_{3}+3\times 5≡0\)

・\(a_{5}≡a^2_{4}+4\times 6≡0\)

・\(a_{6}≡a^2_{5}+5\times 7≡2\)

・\(a_{7}≡a^2_{6}+6\times 8≡1\)

・\(a_{8}≡a^2_{7}+7\times 9≡1\)

つまり、

解答

(１)

以下すべて、mod 3 として考える．

すべての自然数 \(m\) に対して、

\(a_{6m-5}≡1\)、\(a_{6m-4}≡1\)、\(a_{6m-3}≡0\)、\(a_{6m-2}≡0\)、\(a_{6m-1}≡0\)、\(a_{6m}≡2\) となることを、数学的帰納法を用いて証明する．

(ⅰ)　\(m=1\) のとき

• \(a_{1}≡1\)
• \(a_{2}≡a^2_{1}+1\times 3≡1\)
• \(a_{3}≡a^2_{2}+2\times 4≡0\)
• \(a_{4}≡a^2_{3}+3\times 5≡0\)
• \(a_{5}≡a^2_{4}+4\times 6≡0\)
• \(a_{6}≡a^2_{5}+5\times 7≡2\)

となり成立する．

(ⅱ)　\(m=k\) のとき

\(a_{6k-5}≡1\)、\(a_{6k-4}≡1\)、\(a_{6k-3}≡0\)、\(a_{6k-2}≡0\)、\(a_{6k-1}≡0\)、\(a_{6k}≡2\) が成り立つと仮定する．

・\(a_{6k+1}≡a^2_{6k}+6k(6k+2)≡2^2+0\times2≡1\)

・\(a_{6k+2}≡a^2_{6k+1}+(6k+1)(6k+3)≡1^2+1\times0≡1\)

・\(a_{6k+3}≡a^2_{6k+2}+(6k+2)(6k+4)≡1^2+2\times1≡0\)

・\(a_{6k+4}≡a^2_{6k+3}+(6k+3)(6k+5)≡0^2+0\times2≡0\)

・\(a_{6k+5}≡a^2_{6k+4}+(6k+4)(6k+6)≡0^2+1\times0≡0\)

・\(a_{6k+6}≡a^2_{6k+5}+(6k+5)(6k+7)≡0^2+2\times1≡2\)

となり、それぞれ \(m=k+1\) においても成立する．

(ⅰ)、(ⅱ)から、すべての自然数において

\(a_{6m-5}≡1\)、\(a_{6m-4}≡1\)、\(a_{6m-3}≡0\)、\(a_{6m-2}≡0\)、\(a_{6m-1}≡0\)、\(a_{6m}≡2\) が成り立つ．

したがって、\(a_{2022}=a_{6\times337}≡2\)

(２)

\(a_{n+1}=a^2_{n}+n(n+2)\) より、

ユークリッド互除法から、

\(a_{n}\) と \(a_{n+1}\) の最大公約数は、\(a_{n}\) と \(n(n+2)\) の最大公約数に等しい．

よって、

\(a_{2022}\) と \(a_{2023}\) の最大公約数は、\(a_{2022}\) と \(2022\times2024\) の最大公約数に等しく、

\(a_{2023}\) と \(a_{2024}\) の最大公約数は、\(a_{2023}\) と \(2023\times2025\) の最大公約数に等しい．

ここで、

\(2022\times2024=2^4\times 3\times 11 \times23 \times337\)、

\(2023\times2025=3^4\times 5^2\times 7\times 17^2\)

この \(2\) 数は、 \(3\) 以外に共通する素因数を持たないため、

求める最大公約数も、\(3\) 以外に素因数を持たない．