スポンサーリンク

2022京都大学・理・第3問[整数問題] n^2+2,n^4+2,n^6+2の最大公約数

数学(大学入試問題)

2022京都大学・第3問(理)

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

\(3\) つの整数 \(n^2+2\)、\(n^4+2\)、\(n^6+2\) の最大公約数 \(A_{n}\) を求めよ.

考え方

ユークリッド互除法

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

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

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

最大公約数についての問題ですから、まずはユークリッド互除法を検討しましょう!

ユークリッド互除法から

\(n^4+2=(n^2+2)(n^2-2)+6\) より、

\(n^4+2\) と \(n^2+2\) の最大公約数は、

\(n^2+2\) と \(6\) の最大公約数に等しい.

同様に、

\(n^6+2=(n^2+2)(n^4-2n^2+4)-6\) より、

\(n^6+2\) と \(n^2+2\) の最大公約数は、

\(n^2+2\) と \(6\) の最大公約数に等しい.

つまり、

\(3\) つの整数 \(n^2+2\)、\(n^4+2\)、\(n^6+2\) の最大公約数 \(A_{n}\) は、

\(n^2+2\) と \(6\) の最大公約数を求めればよい.

整数問題の極意は実験

このブログでは耳にタコができるぐらい言い続けているポイントです!

整数問題の極意は実験!

方針がつかめない場合については、とにかく実験しましょう!

具体的に実験することで、規則や法則をみつけ、答えを予想しましょう!

本問では、\(n^2+2\) と \(6\) の最大公約数を考えればよいので、

\(n = 1 , 2 , 3 , \cdots\) と具体的に代入して実験してみると、

このとき、「 \(3 , 6 , 1 , 6 , 3 , 2\) 」を繰り返しそう??

周期 \(6\) で繰り返しそうであると予想することが出来る.

解答

\(n^4+2=(n^2+2)(n^2-2)+6\) 、

\(n^6+2=(n^2+2)(n^4-2n^2+4)-6\) より、

ユークリッド互除法から

\(3\) つの整数 \(n^2+2\)、\(n^4+2\)、\(n^6+2\) の最大公約数は

\(n^2+2\) と \(6\) の最大公約数に等しい.

以下では、mod 6 として考える

 

(ア) \(n≡\pm1\) のとき

\(n^2+2≡3\)

よって、\(A_{n}=3\)

\(n^2+2≡3\) ( mod 6 ) とは、

\(n^2+2\) を \(6\) で割った余りが \(3\)

つまり、\(n^2+2=6m+3=3(2m+1)\) と表せるので、

\(n^2+2\) と \(6\) の最大公約数 \(A_{n}=3\) と分かる.

(イ) \(n≡\pm2\) のとき

\(n^2+2≡6≡0\)

よって、\(A_{n}=6\)

 

(ウ) \(n≡3\) のとき

\(n^2+2≡11≡5\)

よって、\(A_{n}=1\)

 

(エ) \(n≡0\) のとき

\(n^2+2≡2\)

よって、\(A_{n}=2\)

 

したがって、\(k\) を \(0\) 以上の整数として

\(A_{n}=\begin{cases}2  ( n=6k )\\3  ( n=6k+1 , 6k+5 )\\6  ( n=6k+2 , 6k+4 )\\1 ( n=6k+3 ) \end{cases}\)

コメント

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