【数IA整数の性質】最大公約数が素数で割り切れない場合(教科書の復習から国公立レベルに挑戦)(北海道大2019理系第2問)

$n$ を自然数とし，$a_n=n(n+1)$ とする。さらに，$a_n$ と $a_{n+3}$ の最大公約数を $d_n$ とする。（北海道大2019）

(1) $d_n$ は偶数であることを示せ。
(2) $d_n$ は 8 で割り切れないことを示せ。
(3) $p$ を 5 以上の素数とするとき，$d_n$ は $p$ で割り切れないことを示せ。
(4) $d_n\leqq12$ を示せ。また，$d_n=12$ となるような $n$ を 1 つ求めよ。

連続する 2 つの数の積は偶数になる

(1)から始めます。

まず，式は

$a_n=n(n+1)$
$a_{n+3}=(n+3)(n+4)$

と表すことができます。

$n(n+1)$ の $n$ に値を代入すると，$1\cdot2,\enspace 2\cdot3,\enspace 3\cdot4,\enspace \cdots$ となり，奇数と偶数のかけ算になります。$(n+3)(n+4)$ でも同様です。
奇数×偶数＝偶数だから，$a_n$ と $a_{n+3}$ はどちらも偶数です。

例えば，12 と 20 の最大公約数を考えてみます。最大公約数は 4 ですが，これを式にすると

$12=3\times4$
$20=5\times4$

となります。このとき，3 と 5 は互いに素の関係です。これを文字を使って表すと以下のようになります。

$a=a’g$，$b=b’g$

$g$ が最大公約数です。また，$a’$ と $b’$ は何でも良いわけではなく，互いに素でなければなりません。

12 と 20 は

$12=6\times2$
$20=10\times2$

と書くこともできますが，2 は約数の一つであって最大公約数ではありません。これは，6 と 10 はどちらも 2 で割ることができる（共通因数として 2 をもつ）ので，互いに素でないからです。

問題に戻ると，$a_n$ と $a_{n+3}$ は

$a_n=a’\cdot d_n$
$a_{n+3}=b’\cdot d_n$

と表すことができます。また，$a_n$ と $a_{n+3}$ はどちらも偶数だから，$a_n=2\times\cdots$ の形に書き換えることができます。

しかし，$a’$ と $b’$ を 2 の倍数にすることはできません（2 を共通因数にもつことになってしまう）。よって，$d_n$ が 2 の倍数だということになります。

隣り合う 2 つの数の積は偶数である。よって

$a_n=a’\cdot d_n=a’\cdot2g$
$a_{n+3}=b’\cdot d_n=b’\cdot2g$
（$a’$ と $b’$ は互いに素）

と表すことができるので，$d_n$ は偶数である。（証明終わり）

奇数と偶数にわけて考える

(2)に進みます。

整数の問題で手がかりが見つからないとき，とりあえず奇数と偶数で場合分けをしてみる，という方針を試してみるとうまくいくことがあります。

「$d_n$ は 8 で割り切れない」は言い換えれば「$d_n$ は 8 の倍数ではない」ということです。これをもとに，場合分けをしていきます。

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

$n=2m+1$ とおくと

$a_n=(2m+1)(2m+2)$
$=2(m+1)(2m+1)$

$m+1$ と $2m+1$ はともに奇数だから，$a_n$ は 8 で割り切れない。よって，$d_n$ は 8 で割り切れない。

$m+1$ と $2m+1$ はともに奇数です。奇数×奇数＝奇数だから，式を 8×・・・の形に直すことはできません。
反対に考えて，もし最大公約数が 8 の倍数であるとするなら
$a_n=a’\cdot8g$
という形で表すことができるはずであり，$a_n$ も 8 で割り切れることになるので，矛盾します。

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

$n=2m$ とおくと
$a_n=2m(2m+1)$

$m$ が 4 の倍数のとき $2m$ は 8 の倍数となり，$a_n$ は 8 で割り切れる（つまり，$d_n$ が 8 で割り切れる場合があり得る）。

$a_{n+3}=(2m+3)(2m+4)$
$=2(m+2)(2m+3)$

ここで，$m$ が 4 の倍数だとして，$m=4k$ とすると

$=2(4k+2)(8k+3)$
$=4(2k+1)(8k+3)$

$2k+1$ と $8k+3$ はともに奇数だから，$a_n$ は 8 で割り切れない。よって，$d_n$ は 8 で割り切れない。

(i)，(ii)より，$d_n$ は 8 で割り切れない。（証明終わり）

証明の中で明示はしていませんが，考え方としては背理法を用いています。つまり，式が 8 で割り切れると仮定すると矛盾することから，8 で割り切れないと結論づけているのです。

背理法を使って矛盾を説明する

(3)に進みます。

ここでも背理法を用いていきます。つまり，$d_n$ が $p$ で割り切れると仮定して，それが矛盾することを示すという流れです。

もともとの式は

$a_n=n(n+1)$
$a_{n+3}=(n+3)(n+4)$

でした。

$a_n$ と $a_{n+3}$ はともに最大公約数 $d_n$ の倍数として表すことができます。そして最大公約数がさらに $p$ で割り切れるなら，$a_n$ と $a_{n+3}$ は $p$ の倍数として表せることになります。 このとき，$a_n$ を考えると，$n\geqq2$ なら $n$ と $n+1$ は互いに素だから，$n$ と $n+1$ のどちらかが $p$ の倍数であると言えます。そこで，$k$ を整数として $p$ の倍数を $pk$ として考えていきます。

$a_n$ と $a_{n+3}$ がともに $p$ で割り切れると仮定して，$k$ を整数とすると (i) $n=pk$ のとき

$a_n=pk(pk+1)$
$a_{n+3}=(pk+3)(pk+4)$

$a_n$ は $p$ の倍数となりますが，$a_{n+3}$ の方をみると，$p$ は 5 以上の素数であり，3 と 4 と $p$ は互いに素だから，$p$ や $k$ がどんな値でも，$p$ をかっこの前に出して $p$ の倍数の形にすることはできません。

よって，$a_{n+3}$ は $p$ で割り切れない。

(ii) $n+1=pk$ のとき

$n=pk-1$ だから

$a_n=(pk-1)pk$

$a_{n+3}=(pk-1+3)(pk-1+4)$
$=(pk+2)(pk+3)$

$a_{n+3}$ は $p$ で割り切れない。

(iii) $n+3=pk$ のとき

$n=pk-3$ だから

$a_n=(pk-3)(pk-3+1)$
$=(pk-3)(pk-2)$

$a_{n+3}=(pk-3+3)(pk-3+4)$
$=pk(pk+1)$

$a_n$ は $p$ で割り切れない。

(iv) $n+4=pk$ のとき

$n=pk-4$ だから

$a_n=(pk-4)(pk-4+1)$
$=(pk-4)(pk-3)$

$a_{n+3}=(pk-4+3)(pk-4+4)$
$=(pk-1)pk$

$a_n$ は $p$ で割り切れない。

(i)～(iv)より，$a_n$ と $a_{n+3}$ がともに $p$ で割り切れるとすると矛盾する。したがって，$d_n$ は $p$ で割り切れない。（証明終わり）

因数を整理する

(4)に進みます。

これまでやってきたことを踏まえて，$d_n$ をかけ算の式として考えます。

まず，$d_n$ は 5 以上の素数で割り切れません。

そのため，$d_n$ を素因数分解して素数の積に直すとしたら，5 以上の素数を含まない，つまり 2 と 3 の積で表せるはずです。

$d_n=2^{s}\cdot3^{t}$

また，$dn$ は偶数だから，素数の積に直したとき，2 を 1 つ以上含むことになります。

しかし，$2^3=8$，$2^4=8\cdot2$，$2^5=8\cdot2^2,\cdots$ だから，2 が 3 つ以上あると，$d_n$ は 8 の倍数となってしまい (2)の条件と合いません。

つまり，2 は $\enspace 2^1,\enspace 2^2$ のいずれかです。

次に，3 について考えます。まず，$3^0$ つまり 3 を含まない場合は，$d_n=2^1\cdot3^0=2$ か $2^2\cdot3^0=4$ となり，(1)～(3)の条件を満たします。

$3^1$ の場合，組み合わせは $2^1\cdot3^1=6$ か $2^2\cdot3^1=12$ となり，(1)～(3)の条件を満たします。

$3^2$ の場合，組み合わせは $2^1\cdot3^2=18$ か $2^2\cdot3^2=36$ となり，(1)～(3)の条件を満たします。

しかし，問題文では $d_n\leqq12$ と言っているので，これは何かが矛盾するはずです。

$d_n$ が $3^2=9$ で割り切れると仮定すると，$a_n$，$a_{n+3}$ はともに 9 で割り切れる。

再び

$a_n=n(n+1)$
$a_{n+3}=(n+3)(n+4)$

に戻って，考えてみます。

(i) $n=9m$ のとき

$a_n=9m(9m+1)$
9 で割り切れる。

$a_{n+3}=(9m+3)(9m+4)$
$=3(3m+1)(9m+4)$
9 で割り切れない。

(ii) $n+1=9m$ のとき

$n=9m-1$ だから

$a_n=(9m-1)\cdot9m$
9 で割り切れる。

$a_{n+3}=(9m+2)(9m+3)$
9 で割り切れない。

(iii) $n+3=9m$ のとき

$n=9m-3$ だから

$a_n=(9m-3)(9m-2)$
$=3(3m-1)(9m-2)$
9 で割り切れない。

$a_{n+3}=9m(9m+1)$
9 で割り切れる。

(iv) $n+4=9m$ のとき

$n=9m-4$ だから

$a_n=(9m-4)(9m-3)$
$=3(3m-1)(9m-4)$
9 で割り切れない。

$a_{n+3}=(9m-1)\cdot 9m$
9 で割り切れる。

(i)～(iv)より，$a_n$ と $a_{n+3}$ がともに 9 で割り切れるとすると矛盾する。よって，$d_n$ は 9 で割り切れない。

 また，2 のときと同様，$3^3=9\cdot3$，$3^4=9\cdot9$，$\cdots$ となり $3^3$ 以上ならすべて 9 で割り切れることになります。

話をまとめると，$d_n$ の可能なパターンは

$2^0\times3^1$，$2^1\times3^0$，$2^1\times3^1$，$2^2\times3^0$，$2^2\times3^1$

の 5 つです。

したがって，$d_n\leqq12$　（証明終わり）

さらに，$d_n=12$ となるような $n$ を 1 つ求めてみます。

最大公約数が 12 であるということは，$a_n$ と $a_{n+3}$ がともに 12 の倍数となる $n$ を見つければ良いことになります。

どちらも連続する 2 つの数の積なので，$1\cdot2$，$2\cdot3$，$\cdots$ のように順番に数をあてはめて，どちらも 12 の倍数になる場合を求めれば良いでしょう。

$n=3$ のとき

$a_n=3\cdot4=12$
$a_{n+3}=6\cdot7=72$ ⇒ 不適

$n=8$ のとき

$a_n=8\cdot9=72$
$a_{n+3}=11\cdot12=132$

どちらも 12 の倍数である。

したがって，$n=8$ （答え）