[math]2022年京都大学理系数学問題3

Table of Contents

問題

$n$を自然数とする。$3$つの整数$n^2+2, n^4+2, n^6+2$の最大公約数$A_n$を求めよ。

方針

$n^6$は急速に大きくなるので、実験もしにくい。Euclidの互除法を用いて考える。

解答

$n^4+2$を$n^2+2$で割ると、$$n^4+2 = (n^2+2)(n^2-2)+6$$となるから、Eulcidの互除法から$n^4+2$と$n^2+2$の最大公約数は$n^2+2$と$6$の最大公約数に等しい。したがって、$n^2+2, n^4+2, n^6+2$を$6$で割った余りを考える。以下$6$を法とする。$$\begin{eqnarray}n \equiv 0 & \to & n^2+2 \equiv 2\\ & & n^4+2 \equiv 2\\ & & n^6+2 \equiv 2 \\ n \equiv 1 & \to & n^2+2 \equiv 3 \\ & & n^4+2\equiv 3 \\ & & n^6 + 2\equiv 3 \\ n\equiv 2 & \to & n^2+2 \equiv 0 \\ & & n^4+2 \equiv 0 \\ && n^6 +2 \equiv 0 \\ n \equiv 3 & \to & n^2+2 \equiv 5 \\ & & n^4 + 2 \equiv 5 \\ & & n^6+2 \equiv 5 \\ n\equiv 4(\equiv -2) & \to & n^2+2 \equiv 0 \\ & & n^4+2 \equiv 0 \\ & & n^6 + 2 \equiv 0 \\ n\equiv 5(\equiv -1) & \to & n^2+2 \equiv 3 \\ & & n^4+2\equiv 3 \\ & & n^6+2 \equiv 3\end{eqnarray}$$となる。以上から、$n\equiv 0$のときは$A_n = 2$、$n\equiv 1$のときは$A_n = 3$、$n\equiv 2$のときは$A_n = 6$、$n\equiv 3$のときは$A_n = 1$、$n\equiv 4$のときは$A_n = 6$、$n\equiv 5$のときは$A_n = 3$となる。

解説

合同式を用いると記述は便利になる。整式の割り算について、一度復習しておく。例えば$n^4+2$を$n^2+2$で割った商と余りを考える。下図のように、係数だけを書いていく。

$1. $ まず$n^4+2$と$n^2+2$を係数だけ書く。
$2. $ $n^4+2$の$n^4$の係数は$1$だから、$n^2$の係数$1$を見て、頭に$1$を書く。
$3. $ $1\times (n^2+2)$の係数を下に書く。
$4. $ 上の段と下の段で引き算を行う。
$5. $ 引き算を行った段の最初の係数$-2$をみて、上に$-2$を書く。
$6. $ $-2\times (n^2+2)$の係数をさらに下に書く。
$7. $ 余りの$6$は$n^2+2$よりも次数が小さいので、割り算はこれで終了である。

以上より、商は$n^2-2$、余りが$6$であることがわかる。