数学A ユークリッドの互除法 問題 6 解説

方針・初手

$n^4+2$，$n^6+2$ を $n^2+2$ で割った余りを見る。共通に割り切る数は、まず $n^2+2$ を割り切るので、$n^2\equiv -2$ として他の2つを調べればよい。

解法1

$x=n^2$ とおく。このとき、求める最大公約数は

$$ A_n=\gcd(x+2,\ x^2+2,\ x^3+2) $$

である。

$x+2$ で割った余りを考えると、$x\equiv -2$ より

$$ x^2+2\equiv (-2)^2+2=6 \pmod{x+2} $$

また、

$$ x^3+2\equiv (-2)^3+2=-6 \pmod{x+2} $$

である。

したがって、$x+2,\ x^2+2,\ x^3+2$ をすべて割り切る整数は、$x+2$ と $6$ を割り切る整数に一致する。よって

$$ A_n=\gcd(x+2,6)=\gcd(n^2+2,6) $$

である。

あとは $n$ を $2$ および $3$ で割った余りで分類する。

まず、$2$ について見る。$n$ が偶数なら $n^2+2$ は偶数であり、$n$ が奇数なら $n^2+2$ は奇数である。

次に、$3$ について見る。平方数は $3$ で割って $0$ または $1$ にしかならない。よって

$$ n^2+2\equiv \begin{cases} 2 & \pmod{3} \quad (3\mid n),\\ 0 & \pmod{3} \quad (3\nmid n) \end{cases} $$

である。したがって、$n^2+2$ は $3\nmid n$ のときに限り $3$ で割り切れる。

以上より、$n$ を $6$ で割った余りで分類すると、

$$ A_n= \begin{cases} 6 & (n\equiv 2,4 \pmod{6}),\\ 3 & (n\equiv 1,5 \pmod{6}),\\ 2 & (n\equiv 0 \pmod{6}),\\ 1 & (n\equiv 3 \pmod{6}) \end{cases} $$

となる。

解説

この問題では、3つの数を直接素因数分解しようとすると処理が重くなる。共通因数を調べるときは、1つを基準にして他の数の余りを見るのが有効である。

特に $n^2+2$ を基準にすると、$n^2\equiv -2$ と置けるため、$n^4+2$ と $n^6+2$ の余りがそれぞれ $6$，$-6$ になる。これにより、問題は $\gcd(n^2+2,6)$ の計算に帰着する。

最後の分類では、$6=2\cdot 3$ であることから、$2$ で割れる条件と $3$ で割れる条件を別々に調べればよい。

答え

$$ A_n=\gcd(n^2+2,6) $$

すなわち、

$$ \boxed{ A_n= \begin{cases} 6 & (n\equiv 2,4 \pmod{6}),\\ 3 & (n\equiv 1,5 \pmod{6}),\\ 2 & (n\equiv 0 \pmod{6}),\\ 1 & (n\equiv 3 \pmod{6}) \end{cases} } $$