数学A / 整数の性質

連続する整数が互いに素であること

★★ 標準互いに素倍数の証明

問題

$n$ を整数とする。連続する $2$ つの整数 $n$ と $n + 1$ は互いに素であることを証明せよ。

ヒントを見る

$n$ と $n + 1$ の共通の(正の)約数を $d$ とおく。 $d$ が $n$ も $n + 1$ も割り切るなら、その差 $(n + 1) - n$ も割り切るはず — 差はいくつ?

解答・解説

『互いに素』は『 $1$ 以外に共通の約数がない』こと。共通の約数を $d$ とおき、 $d$ が $1$ しかありえないことを示す。

⓪ 発想 — どう考え始めるか。 「互いに素」とは、 $1$ 以外に共通の約数がないこと。示したいのは「無い」ことだ。

無いことの証明は、あると仮定して調べるのが定石になる。共通の約数を $d$ とおく。

$d$ は $n$ も $n + 1$ も割り切る。割り切るなら、その差 $(n + 1) - n = 1$ も割り切るはずだ。 $1$ を割り切る正の整数は $1$ だけ。だから $d = 1$ しかない。「差も割り切る」が一撃の急所である。

重要公約数は差も割り切る:

g cd (n, n + 1)

は

(n + 1) - n = 1

を割る → 互いに素

$n$ と $n + 1$ の正の公約数を $d$ とする。 $d$ は $n$ を割り切り、 $n + 1$ も割り切る。

すると、その差も $d$ で割り切れる。

$(n + 1) - n = 1$

つまり $d$ は $1$ を割り切る。 $1$ を割り切る正の整数は $1$ だけだから、 $d = 1$ 。

よって $n$ と $n + 1$ の公約数は $1$ しかなく、互いに素である。 $■$

(カギは『 $2$ 数を割り切る数は、その差も割り切る』という性質。差が $1$ になったことで、公約数が $1$ に追い込まれた。連続整数が互いに素なのは、この『差 $1$ 』のおかげだ。)

発展 — 一歩先へ。 「差を取って公約数の候補を絞る」技は広く使える。たとえば $n + 2$ と $2 n + 7$ の公約数は、 $2 (n + 2)$ との差 $3$ の約数に限られる、という具合だ(分数が整数になる条件の問題で、この形が主役になる)。

連続整数が互いに素である事実は、「連続する2整数の積は必ずどちらか一方の素因数しか持たない」など、整数の証明問題の部品として頻繁に引用される。1行で示せるようにしておきたい。

答

$n$ と $n + 1$ の公約数は $1$ だけ(証明は解答参照)

互除法を学んだ目で見ると、この証明は1行になる。

互除法の原理は「 $g cd (a, b) = g cd (b, r)$ ( $r$ は $a$ を $b$ で割った余り)」だった。

$n + 1$ を $n$ で割ると、商 $1$ ・余り $1$ 。だから

$g cd (n + 1, n) = g cd (n, 1) = 1$

割り算1回で、最大公約数が $1$ と確定した。

本解の「差も割り切る」は、実はこの互除法の1ステップ(余り $1$ に落ちる)を素朴な言葉で言ったものだ。連続する2整数はいつでも互除法が一瞬で終わる、最も仲の悪い(共通点のない)隣人どうしなのである。