問題
\(n\) を自然数とする．
(1) \(2n^2+1\) と \(10\) は互いに素であることを示せ．
(2) \(2n^2+1\) と \(2n^2+10n+11\) の最大公約数として考えられる数を求めよ．
（１）考え方・解答
「\(2n^2+1\) と \(2\) が互いに素」かつ
「\(2n^2+1\) と \(5\) が互いに素」
であることを示せばよい．
※以下の解答では合同式を利用します。
整数問題を武器にする上で、合同式は必須アイテム！
合同式に不安がある人は
で基本をおさらい！
また、入試問題でぜひ演習を！
2021 兵庫県立大学【整数】平方数には合同式(mod)を使え！
解答
\(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\) つの自然数 \(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\)
コメント