スポンサーリンク

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

数学(大学入試問題)

【2022東京大学・文・第3問】

\(a_{1}=4\)、\(a_{n+1}=a^2_{n}+n(n+2)\) ( \(n=1, 2, 3 ,\cdots\))

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

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

考え方

整数問題の極意は実験

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

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

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

 

合同式の利用

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

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

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

 

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

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

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

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

ユークリッド互除法

【ユークリッドの互除法】

\(2\) つの自然数 \(a\) 、\(b\) において、\(a\) を \(b\) で割ったときの商を \(q\)、余りを \(r\) とすると

\(a\) と \(b\) の最大公約数は、\(b\) と \(r\) の最大公約数に等しい

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

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

以下すべて、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\)

☞ 「 \(1 , 1 , 0 , 0 , 0 , 2\) 」 を繰り返す??

\(6\) つの周期性を持ちそうであると予想できる!

つまり、

すべての自然数 \(m\) において、

  • \(a_{6m-5}≡1\)
  • \(a_{6m-4}≡1\)
  • \(a_{6m-3}≡0\)
  • \(a_{6m-2}≡0\)
  • \(a_{6m-1}≡0\)
  • \(a_{6m}≡2\)     となることを示せばよい!

※数学的帰納法を用いて証明する.

解答

(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\)

(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\) 以外に素因数を持たない.

現時点で考えられる答えの候補は、\(1\) または \(3\) ということ
(1)の結果より、\(a_{2022}≡2\) であるため、\(a_{2022}\) は \(3\) の倍数ではない.
ゆえに、求める最大公約数は \(1\) 

 

コメント

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