【整数問題】nは自然数。３つの整数　n^3+2、n^4+2、n^6+2の最大公約数A_nを求めよ。（2022・京都大学）

未分類

2022.02.28 2022.02.25

今回は、「整数問題（２０２２・京都大学）」の解説をします。

この記事を読むと

整数問題（２０２２・京都大学）の解答
整数問題（２０２２・京都大学）の実験
合同式を用いて、あまりに着目して場合分けする方法

を理解することができます。

この記事は「わか」執筆しています。

私「わか」（https://twitter.com/wakkachan2019）は、国立大学数学科を卒業後、数学教育に10年以上関わっています。

問題：整数問題（2022・京都大学）
実験
解答
補足：合同式とは
まとめ：整数問題（2022・京都大学）

問題：整数問題（2022・京都大学）

問題

$n$ を自然数とする。３つの整数

$$n^2+2 , n^4+2 , n^6+2$$

の最大公約数 $A_n$ を求めよ。

（2002・京都大学）

実験

まず具体的な数字を代入して、実験をします。

実験

具体的な数字を代入して、最大公約数を求める

\begin{array}{|c|c|c|} \hline &1&2&3&4&5&6\\\hline n^2+2&3&6&11&18&27&38 \\ \hline n^4+2 &3&18&83&258&25^2+2&36^2+2\\\hline n^6+2&3&66&731&4098&25^3+2&36^3+2\\\hline A_n&3&6&1&6&3&2\\ \hline \end{array}

またmod3を考えると

\begin{array}{|c|c|c|} \hline n &1&2&3&4&5&6\\\hline n^2+2\pmod3&0&0&2&0&0&2 \\ \hline n^4+2 \pmod3 &0&0&2&0&0&2\\\hline n^6+2\pmod3&0&0&2&0&0&2\\ \hline \end{array}

mod2を考えると

\begin{array}{|c|c|c|} \hline n &1&2&3&4&5&6\\\hline n^2+2\pmod2&0&1&0&1&0&1 \\ \hline n^4+2 \pmod2 &0&1&0&1&0&1\\\hline n^6+2\pmod2&0&1&0&1&0&1\\ \hline \end{array}

mod6を考えるとうまくいきそうという見当を付ける。

整数問題の大切なアプローチのひとつ

倍数やあまりで分類する

を使います。

解答

$n^4+2$ を $n^2+2$ で割ると６余る　ユークリッド互除法利用　

$$n^4+2=(n^2+2)(n^2-2)+6$$

より、$n^4+2$ と $n^2+2$ の最大公約数は

$n^2+2$ と６の最大公約数と等しい

$n^6+2$ を $n^2+2$ で割ると-６余る　ユークリッド互除法利用　

$$n^6+2=(n^2+2)(n^4-2n^2+2)-6$$

より、$n^6+2$ と $n^2+2$ の最大公約数は

$n^2+2$ と６の最大公約数と等しい

$A_n$ は６の約数「１、２、３、６」のいずれかが候補となる

$n^2+2$ を６で割った余りを考えれば良いので

以下 $\pmod6$ を考える

① $n\equiv0\pmod6$ のとき

$$n^2+2\equiv2\pmod6$$

$$n^4+2\equiv2\pmod6$$

$$n^6+2\equiv2\pmod6$$

したがって、$A_n=2$

② $n\equiv\pm1\pmod6$ のとき

$$n^2+2\equiv3\pmod6$$

$$n^4+2\equiv3\pmod6$$

$$n^6+2\equiv3\pmod6$$

したがって、$A_n=3$

③ $n\equiv\pm2\pmod6$ のとき

$$n^2+2\equiv6\equiv0\pmod6$$

$$n^4+2\equiv18\equiv0\pmod6$$

$$n^6+2\equiv66\equiv0\pmod6$$

したがって、$A_n=6$

④ $n\equiv3\pmod6$ のとき

$$n^2+2\equiv11\pmod6$$

$$n^4+2\equiv83\pmod6$$

$$n^6+2\equiv73\pmod6$$

したがって、$A_n=1$

①、②、③、④より

\begin{eqnarray} A_n = \begin{cases} 2 & ( n \equiv 0\mod6 ) \\ 3 & ( n \equiv \pm1\mod6 ) \\6 & ( n \equiv \pm2\mod6 ) \\1 & ( n \equiv \pm3\mod6 ) \end{cases} \end{eqnarray}