隣り合う階乗+1の最大公約数

方針

解答

⓪ 発想 — どう考え始めるか。 巨大な2数の最大公約数は、互除法の原理「$\gcd (a,b)=\gcd (a,b-ka)$(倍数を引いても不変)」で小さくするのが定石だ。

$(n+1)!+1$ は、$(n+1)(n!+1)=(n+1)!+n+1$ にとても近い。差を作ると階乗が消えて、$n$ だけが残る。

これで問題は「$n!+1$ と $n$」という圧倒的に小さい2数の話になり、最後は「$n!$ は $n$ の倍数」という当たり前の一言で決着する。

① 差を作って小さくする。 $g=\gcd (n!+1,(n+1)!+1)$ とおく。$g$ は2数の組合せ

$$(n+1)(n!+1)-\{(n+1)!+1\}=(n+1)!+n+1-(n+1)!-1=n$$

も割り切る。よって $g$ は $n!+1$ と $n$ の公約数でもある。

② 互いに素で仕上げる。 $g\ge 2$ と仮定する。$g\mid n$ だから、$n!=1\cdot 2\cdots n$ は $n$ を因数に含み $g$ の倍数。すると

$$g\mid (n!+1)-n!=1$$

となり $g\ge 2$ に矛盾。よって $g=1$、すなわち $n!+1$ と $(n+1)!+1$ は互いに素。

まとめ: 互除法は「割り算」でなく「倍数を引いて小さくする」操作だと捉えると、階乗のような巨大な数にも自在に使える。$n!$ が $1$ 〜 $n$ のすべての倍数である、という当たり前が最後の一撃になる構図も覚えておきたい。

発展 — 一歩先へ。 ②の議論を裏返すと、「$n!+1$ の素因数はすべて $n$ より大きい」ことが分かる。どんな $n$ に対しても $n$ より大きい素数が存在する — つまり素数は無限にある、という古典の証明(ユークリッド)が、この1行から出てくる。

別解

素因数の目で見る(得意な人向け)。 公約数 $g$ を丸ごと扱う代わりに、その素因数 $p$ を1つ取って追い詰める。

$p$ を $g$ の素因数とする。まず $p\mid n!+1$ から、$p$ の大きさが分かる。もし $p\le n$ なら、$p$ は $n!=1\cdot 2\cdots n$ の因数だから $p\mid n!$。すると $p\mid (n!+1)-n!=1$ となり矛盾。よって

$$p>n$$

一方、本解①と同じ引き算で $p\mid n$。素数 $p$ が $n$ を割り切るなら $p\le n$ のはずだ。

「$p>n$」と「$p\le n$」が正面衝突した。そんな素数 $p$ は存在しない。素因数をもたない自然数は1だけだから、$g=1$。

大きさの矛盾で仕留めるこの形は、素数がらみの互いに素の証明でよく効く。「$n!+1$ の素因数は $n$ より大きい」という部品(発展の種)も、この視点の副産物だ。