トップ› 京都大学› 2022年› 理系第3問

京都大学 2022年理系第3問解説

方針・初手

複数の文字式（多項式）で表された整数の最大公約数を求める問題では、ユークリッドの互除法の原理 $\gcd(A, B) = \gcd(A, B - AQ)$ を用いて、式の次数を下げるのが定石です。最も次数の低い $n^2+2$ で他の $2$ つの式を割ることで、「定数」を作り出し、最大公約数の候補を絞り込みます。

解法1

$X = n^2+2, Y = n^4+2, Z = n^6+2$ とおく。 $A_n$ はこれら $3$ つの整数の最大公約数であるから、$A_n$ は $X$ と $Y$ の公約数でもある。 $Y$ を $X$ で割ると、

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

すなわち、

$$ Y - X(n^2-2) = 6 $$

が成り立つ。 $A_n$ は $X$ と $Y$ をともに割り切る自然数であるため、上式より $6$ も割り切らなければならない。よって、$A_n$ は $6$ の正の約数であり、$A_n \in \{1, 2, 3, 6\}$ に絞られる。

また、ユークリッドの互除法の性質から $\gcd(X, Y) = \gcd(n^2+2, 6)$ である。さらに $Z$ を $X$ で割ると、

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

となり、$Z - X(n^4 - 2n^2 + 4) = -6$ であるため、$\gcd(n^2+2, 6)$ は $Z$ も割り切る。したがって、$A_n = \gcd(X, Y, Z) = \gcd(n^2+2, 6)$ となる。

ここで、$n^2+2$ が $2$ の倍数か、$3$ の倍数かを調べる。

(i) $2$ で割った余りについて

$n \equiv 0 \pmod 2$ のとき、$n^2+2 \equiv 0^2+2 \equiv 0 \pmod 2$

$n \equiv 1 \pmod 2$ のとき、$n^2+2 \equiv 1^2+2 \equiv 1 \pmod 2$

よって、$n$ が偶数のときのみ $n^2+2$ は $2$ の倍数となる。

(ii) $3$ で割った余りについて

$n \equiv 0 \pmod 3$ のとき、$n^2+2 \equiv 0^2+2 \equiv 2 \pmod 3$

$n \equiv 1 \pmod 3$ のとき、$n^2+2 \equiv 1^2+2 \equiv 0 \pmod 3$

$n \equiv 2 \pmod 3$ のとき、$n^2+2 \equiv 2^2+2 \equiv 0 \pmod 3$

よって、$n$ が $3$ の倍数でないときのみ $n^2+2$ は $3$ の倍数となる。

以上 (i), (ii) より、$n$ を $6$ で割った余りで分類する。（$k$ を非負整数とする）

$n = 6k$ のとき $n$ は偶数かつ $3$ の倍数であるから、$n^2+2$ は $2$ の倍数だが $3$ の倍数ではない。よって、$A_n = 2$
$n = 6k \pm 1$ のとき $n$ は奇数かつ $3$ の倍数ではないから、$n^2+2$ は $3$ の倍数だが $2$ の倍数ではない。よって、$A_n = 3$
$n = 6k \pm 2$ のとき $n$ は偶数かつ $3$ の倍数ではないから、$n^2+2$ は $2$ の倍数かつ $3$ の倍数（すなわち $6$ の倍数）である。よって、$A_n = 6$
$n = 6k+3$ のとき $n$ は奇数かつ $3$ の倍数であるから、$n^2+2$ は $2$ の倍数でも $3$ の倍数でもない。よって、$A_n = 1$

解説

整数の最大公約数を求める問題における典型的な解法「ユークリッドの互除法の多項式への応用」です。多項式の割り算を行い、「余りが定数（文字 $n$ を含まない数）」になるように式変形することで、最大公約数の候補をその定数の約数に限定できることが最大のポイントです。本問では $n^4+2$ を $n^2+2$ で割って余り $6$ を導出できれば、あとは合同式を用いて $2$ と $3$ の倍数判定に帰着させるだけで完答できます。