京大2022年度理系第3問

問題．

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

$n^2+2, n^4+2, n^6+2$ は因数分解できないので，互除法を使って考えることになります．

ユークリッドの互除法
$A$ を $B$ で割ったときの余りを $C$ とするとき， $A$ と $B$ の最大公約数は $B$ と $C$ の最大公約数に等しい

まず， $n^4+2, n^6+2$ を $n^2+2$ で割ったときの余りをそれぞれ求めると，

\begin{align*}
n^4+2 &= (n^4-4)+6\\
&= (n^2+2)(n^2-2)+6\\
n^6+2 &= (n^6+8)-6\\
&= (n^2+2)(n^4-2n^2+4)-6
\end{align*}

よって，最大公約数 $A_n$ は $n^2+2$ と $6$ の最大公約数に等しい．

さらに， $n^2+2$ を6で割ったときの余りを $R_n$ とすると， $A_n$ は $R_n$ と $6$ の最大公約数に等しい．

あとは， $n$ を6で割った余りで場合分けして調べていきます．

(i) $n=6m$ ( $m$ は整数)と書けるとき
\begin{align*}
n^2+2 &= (6m)^2+2\\
&= 6\cdot 6m+2
\end{align*}
より， $R_n=2$ であり， $A_n=2$ .

(ii) $n=6m\pm 1$ ( $m$ は整数)と書けるとき
\begin{align*}
n^2+2 &= (6m\pm 1)^2+2\\
&= 6(6m^2\pm 2m)+3
\end{align*}(複号同順)
より， $R_n=3$ であり， $A_n=3$ .

(iii) $n=6m\pm 2$ ( $m$ は整数)と書けるとき
\begin{align*}
n^2+2 &= (6m\pm 2)^2+2\\
&= 6(6m^2\pm 4m+1)
\end{align*}(複号同順)
より， $R_n=0$ であり， $A_n=6$ .

(iv) $n=6m+3$ ( $m$ は整数)と書けるとき
\begin{align*}
n^2+2 &= (6m+3)^2+2\\
&= 6(6m^2+6m+1)+5
\end{align*}
より， $R_n=5$ であり， $A_n=1$ .

したがって，(i)〜(iv)より，
$n$ を $6$ で割った余りが0のとき $A_n=2$
1,5のとき $A_n=3$
2,4のとき $A_n=6$
3のとき $A_n=1$

$n$ を6で割った余りが1, 5のとき，および2,4のときをまとめて計算していますが，これは場合分けをする前に具体的な $n$ の値 $n=1, 2, 3, 4, 5, 6$ の場合を計算してみることで，まとめて扱ってよいかどうかを判断できます．