n を自然数とする。3 つの整数 n^2 + 2，n^4 + 2，n^6 + 2 の最大公約数 A_n を求めよ。
a = n^2 とおくと、3 つの数は a + 2、a^2 + 2、a^3 + 2 です。あとの 2 つを a + 2 で割ると、次の式になる。
a^2 + 2 = (a + 2)(a - 2) + 6
a^3 + 2 = (a + 2)(a^2 - 2a + 4) - 6
どちらの式も、a + 2 の倍数と 6 または -6 の和になっています。
A_n は a + 2 と a^2 + 2 を割り切るため、(a^2 + 2) - (a + 2)(a - 2) = 6 も割り切ります。A_n は a + 2 と 6 の公約数です。
逆に、a + 2 と 6 をともに割り切る数 d をとると、割り算の 2 つの式の右辺はどちらも d で割り切れ、a^2 + 2 と a^3 + 2 も d の倍数になる。d は 3 つの数の公約数です。
3 つの数の公約数と、a + 2 と 6 の公約数は同じものです。よって A_n は、n^2 + 2 と 6 の最大公約数に等しい。
n^2 + 2 の偶奇は n の偶奇と同じです。2 で割り切れるのは、n が偶数のとき。
n が 3 の倍数なら、n^2 + 2 を 3 で割った余りは 2 になる。n が 3 の倍数でなければ n = 3k \pm 1 と書けて、n^2 + 2 = 3(3k^2 \pm 2k + 1) は 3 で割り切れます。
6 = 2 \cdot 3 だから、A_n は n^2 + 2 が 2 と 3 のそれぞれで割り切れるかどうかで決まります。
2 つの結果を組み合わせると、n を 6 で割った余りによって次の 4 通りに分かれます。
余りが 0 のとき、n は偶数で 3 の倍数だから A_n = 2。
余りが 2 か 4 のとき、n は偶数で 3 の倍数でないため A_n = 6。
余りが 1 か 5 のとき、n は奇数で 3 の倍数でないため A_n = 3。
余りが 3 のとき、n は奇数で 3 の倍数だから A_n = 1。
n = 2 なら 3 つの数は 6、18、66 で、最大公約数は 6 です。n = 3 なら 11、83、731 で、最大公約数は 1 になります。