スポンサーリンク

整数問題|ユークリッドの互除法・最大公約数[入試問題演習]

数学(大学入試問題)

問題

\(n\) を自然数とする.

(1) \(2n^2+1\) と \(10\) は互いに素であることを示せ.

(2) \(2n^2+1\) と \(2n^2+10n+11\) の最大公約数として考えられる数を求めよ.

(1)考え方・解答

「\(2n^2+1\) と \(2\) が互いに素」かつ

「\(2n^2+1\) と \(5\) が互いに素」

であることを示せばよい.

※以下の解答では合同式を利用します。

整数問題を武器にする上で、合同式は必須アイテム!

合同式に不安がある人は

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

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

で基本をおさらい!

また、入試問題でぜひ演習を!

2021 岡山大学・文理共通【整数問題】合同式・余り

2021 東京海洋大学|背理法・倍数証明・合同式の利用

2021 兵庫県立大学【整数】平方数には合同式(mod)を使え!

2021 京都大学(文系:第4問) 整数問題

解答

\(n\) は自然数であるから、\(2n^2+1\) は奇数

よって、\(2n^2+1\) と \(2\) は互いに素・・・① となる.

 

次に、法を \(5\) として、

\(n≡0 , \pm1 , \pm 2\)

\(n^2≡0 , 1 , 4\) より

\(2n^2+1≡ 1 , 3 , 4\) となる.

よって、\(2n^2+1\) と \(5\) は互いに素・・・② となる.

①、②より、\(2n^2+1\) と \(10\) は互いに素である.

(2)考え方・解答

ユークリッド互除法

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

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

つまり、\(a=bq+r\) のとき

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

 

(2) 整数 \(A\)、\(B\) に対し、それぞれの最大公約数を \(( A , B )\) と表す.

ただし、\(A=B=0\) の場合はのぞく

 

\((2n^2+10n+11=1\times(2n^2+1)+10(n+1)\) なので

ユークリッド互除法より

\((2n^2+1 , 2n^2+10n+11)=( 2n^2+1 , 10(n+1) )\)

(1)の結果から、\(2n^2+1\) と \(10\) は互いに素であるから、

\((2n^2+1 , 2n^2+10n+11)=( 2n^2+1 , n+1 )\)

 

\(2n^2+1=(2n-2)(n+1)+3\) なので

ユークリッド互除法より

\((2n^2+1 , 2n^2+10n+11)=( 3 , n+1 )\)

 

したがって、

\(n+1\) が \(3\) の倍数のとき、最大公約数は \(3\)

\(n+1\) が \(3\) の倍数でないのとき、最大公約数は \(1\)

 

よって、\(1\) または \(3\)

 

コメント

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