トップ› 北海道大学› 2019年› 理系第2問

北海道大学 2019年理系第2問解説

方針・初手

$a_n = n(n+1)$、$a_{n+3} = (n+3)(n+4)$ はともに連続する2つの整数の積である。連続する2整数の積は必ず偶数になるという基本的な性質を利用する。 (2)以降は、最大公約数 $d_n$ がある数 $k$ の倍数であると仮定し、整数の剰余や合同式を用いて矛盾を導く（背理法）方針が有効である。また、多項式の差や商を考えて $n$ を消去し、$d_n$ の候補を絞り込むユークリッドの互除法的なアプローチも強力な別解となる。

解法1

(1)

$n$ と $n+1$ は連続する2つの自然数であるから、いずれか一方は偶数である。したがって、その積 $a_n = n(n+1)$ は偶数である。

同様に、$n+3$ と $n+4$ も連続する2つの自然数であるから、その積 $a_{n+3} = (n+3)(n+4)$ も偶数である。

$a_n$ と $a_{n+3}$ がともに偶数（2の倍数）であるから、その最大公約数 $d_n$ も2の倍数となる。よって、$d_n$ は偶数である。

(2)

$d_n$ が 8 で割り切れると仮定して矛盾を導く。 $d_n$ が 8 の倍数であるとき、$d_n$ は $a_n$ と $a_{n+3}$ の公約数であるから、$a_n$ と $a_{n+3}$ はともに 8 の倍数となる。 $n$ の偶奇で場合分けをする。

(i) $n$ が偶数のとき

$n+1$ は奇数である。$a_n = n(n+1)$ が 8 の倍数となるためには、$n$ が 8 の倍数でなければならない。 $n = 8k$（$k$ は自然数）とおくと、 $$ a_{n+3} = (8k+3)(8k+4) = 4(8k+3)(2k+1) $$ ここで、$8k+3$ と $2k+1$ はともに奇数であるから、それらの積も奇数となる。したがって、$a_{n+3}$ は 4 の倍数ではあるが、8 の倍数ではない。これは $a_{n+3}$ が 8 の倍数であることに矛盾する。

(ii) $n$ が奇数のとき

$n$ は奇数であるから、$a_n = n(n+1)$ が 8 の倍数となるためには、$n+1$ が 8 の倍数でなければならない。 $n+1 = 8k$（$k$ は自然数）とおくと、$n = 8k-1$ となり、 $$ a_{n+3} = (8k+2)(8k+3) = 2(4k+1)(8k+3) $$ ここで、$4k+1$ と $8k+3$ はともに奇数であるから、それらの積も奇数となる。したがって、$a_{n+3}$ は 2 の倍数ではあるが、4 の倍数ではなく、まして 8 の倍数ではない。これは矛盾である。

以上より、$a_n$ と $a_{n+3}$ がともに 8 の倍数となることはない。よって、$d_n$ は 8 で割り切れない。

(3)

$p$ を 5 以上の素数とする。$d_n$ が $p$ で割り切れると仮定する。このとき、$a_n$ と $a_{n+3}$ はともに $p$ の倍数となる。合同式を用いて、法を $p$ として考える。 $a_n \equiv 0 \pmod p$ より、 $$ n(n+1) \equiv 0 \pmod p $$ $p$ は素数であるから、$n \equiv 0 \pmod p$ または $n+1 \equiv 0 \pmod p$（すなわち $n \equiv -1 \pmod p$）が成り立つ。

(i) $n \equiv 0 \pmod p$ のとき

$a_{n+3}$ について考えると、 $$ a_{n+3} = (n+3)(n+4) \equiv 3 \cdot 4 = 12 \pmod p $$ $a_{n+3} \equiv 0 \pmod p$ であるから、$12 \equiv 0 \pmod p$ となる。これは $p$ が 12 の約数であることを意味するが、12 の素因数は 2 と 3 のみであり、$p \geqq 5$ に矛盾する。

(ii) $n \equiv -1 \pmod p$ のとき

$a_{n+3}$ について考えると、 $$ a_{n+3} = (n+3)(n+4) \equiv (-1+3)(-1+4) = 2 \cdot 3 = 6 \pmod p $$ $a_{n+3} \equiv 0 \pmod p$ であるから、$6 \equiv 0 \pmod p$ となる。これは $p$ が 6 の約数であることを意味するが、6 の素因数は 2 と 3 のみであり、$p \geqq 5$ に矛盾する。

以上より、$a_n$ と $a_{n+3}$ がともに $p$ の倍数となることはない。よって、$d_n$ は 5 以上の素数 $p$ で割り切れない。

(4)

(1)から(3)の議論により、$d_n$ が持ち得る素因数は 2 と 3 のみであることがわかる。また、(2)より $d_n$ は 8 の倍数ではないため、素因数 2 は最大でも $2^2 = 4$ までしか含まれない。すなわち、$d_n = 2^x \cdot 3^y$（$x \in \{1, 2\}$, $y$ は 0 以上の整数）と表せる。

ここで、$d_n$ が 9（$3^2$）で割り切れるか調べるために、$a_n$ と $a_{n+3}$ がともに 9 の倍数になると仮定する。合同式を用いて法を 9 とすると、$n(n+1) \equiv 0 \pmod 9$ となる。 $n$ と $n+1$ は互いに素であるから、どちらか一方が 9 の倍数でなければならない。

(i) $n \equiv 0 \pmod 9$ のとき

$$ a_{n+3} = (n+3)(n+4) \equiv 3 \cdot 4 = 12 \equiv 3 \pmod 9 $$ よって $a_{n+3} \equiv 0 \pmod 9$ に矛盾する。

(ii) $n+1 \equiv 0 \pmod 9$ のとき

$n \equiv -1 \pmod 9$ より、 $$ a_{n+3} = (n+3)(n+4) \equiv 2 \cdot 3 = 6 \pmod 9 $$ よって $a_{n+3} \equiv 0 \pmod 9$ に矛盾する。

したがって、$d_n$ は 9 で割り切れないので、$y \leqq 1$ である。以上より、$x \leqq 2$ かつ $y \leqq 1$ であるから、 $$ d_n = 2^x \cdot 3^y \leqq 2^2 \cdot 3^1 = 12 $$ となり、$d_n \leqq 12$ が示された。

次に $d_n = 12$ となる $n$ を探す。 $n=1, 2, 3, \dots$ と順に $a_n$ と $a_{n+3}$ を計算して調べる。 $a_n = n(n+1)$ が 12 の倍数になる必要がある。 $n=3$ のとき $a_3 = 12$。このとき $a_6 = 6 \cdot 7 = 42$ となり、$\gcd(12, 42) = 6 \neq 12$。 $n=8$ のとき $a_8 = 8 \cdot 9 = 72$。このとき $a_{11} = 11 \cdot 12 = 132$ となり、 $$ \gcd(72, 132) = \gcd(12 \cdot 6, 12 \cdot 11) = 12 \cdot \gcd(6, 11) = 12 \cdot 1 = 12 $$ よって、$d_n = 12$ となるような $n$ の1つとして $n=8$ が挙げられる。

解法2

(4)の別解（ユークリッドの互除法を用いた直接的な証明）

$d_n$ は $a_n = n(n+1)$ と $a_{n+3} = (n+3)(n+4)$ の最大公約数であるから、この2つの整数の任意の線形結合（整数係数の和や差）も $d_n$ を約数にもつ。 $$ a_{n+3} = n^2 + 7n + 12 $$ $$ a_n = n^2 + n $$ この2式の差をとると、 $$ a_{n+3} - a_n = 6n + 12 = 6(n+2) $$ $d_n$ は $a_n$ と $6(n+2)$ の公約数である。ここで、$a_n$ を $n+2$ でくくる形に変形すると、 $$ a_n = n^2 + n = (n+2)(n-1) + 2 $$ $d_n$ は $a_n$ を割り切り、また $6(n+2)$ も割り切るため、次のようにつくった整数 $M$ も割り切らなければならない。 $$ M = 6a_n - (n-1) \cdot 6(n+2) $$ この式を計算すると、 $$ \begin{aligned} M &= 6(n^2+n) - 6(n^2+n-2) \\ &= 12 \end{aligned} $$ $d_n$ は $M=12$ の約数であることがわかる。 $d_n$ は自然数であるから、12 の正の約数である。したがって、直ちに $d_n \leqq 12$ が導かれる。

（$n$ を求める部分は解法1と同様）

解説

(1)から(3)までは、互いに素な条件や素因数に着目して倍数・約数を扱う整数問題の典型的な論証の練習である。「$A$ が $p$ で割り切れる」という条件を剰余（合同式）で処理すると見通しよく記述できる。

(4)において解法2で示したように、多項式の割り算（ユークリッドの互除法の原理）を利用して「変数を消去し、定数だけを残す」という発想は、入試数学の整数問題において極めて頻出かつ強力な手筋である。最大公約数 $d = \gcd(A, B)$ は、$A$ と $B-kA$ の最大公約数と一致するという性質を活用することで、本問の(1)から(4)までを統合的に見通すことができる。