【数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}$ はどちらも偶数です。

$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 をもつ)ので,互いに素でないからです。

つまり,最大公約数を求めようとして,2 つの数を何かで割ってみて,商がまだ何かで割れる状態だと最大公約数になってないってこと。でも,最大公約数で割ったときは $a’$ と $b’$ には共通因数がない状態,互いに素の状態になってる。

問題に戻ると,$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 で割り切れる。

実際に証明を書くときには,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$ (答え)