整数の性質 最難関編の問題 全8問

方針

解答

⓪ 発想(どう考え始めるか) 「素数になる組をすべて」型は、候補を消していく消去法で進める。

第一の刃は偶奇だ。$p,q$ がともに奇素数なら、$p^q+q^p$ は奇数+奇数=偶数で、2より大きいから合成数。よって一方は2。

$p=2$ として $2^q+q^2$ を調べると、$q=3$ で17(素数)が見つかる。問題は「$q>3$ では全部だめ」とどう言い切るかだ。ここで法を3に切り替える。$2\equiv -1(\mathrm{mod}3)$ だから $2^q$ の余りは $q$ の偶奇だけで決まり、$q^2$ の余りは「3で割れない数の平方は1」で決まる。2つを足すと3の倍数になってしまう、という仕掛けだ。

① 一方は2。 $p,q$ がともに奇素数なら $p^q+q^p$ は偶数で4以上だから素数でない。対称性から $p=2$ の場合を調べ、最後に $p,q$ の入れ替えを含めればよい。

② 小さい $q$ を試す。 $q=2$: $2^2+2^2=8$ で不適。$q=3$: $2^3+3^2=8+9=17$ は素数。候補になる。

③ $q>3$ の素数はすべて不適。 $q$ は奇数で、3の倍数でもない。$2\equiv -1(\mathrm{mod}3)$ より

$$2^q\equiv (-1{)}^q=-1\equiv 2(\mathrm{mod}3)$$

また $q$ は3で割れないから $q^2\equiv 1(\mathrm{mod}3)$。よって

$$2^q+q^2\equiv 2+1=3\equiv 0(\mathrm{mod}3)$$

つまり $2^q+q^2$ は3の倍数で、明らかに3より大きいから合成数。

④ 結論。 $(p,q)=(2,3)$ と、入れ替えた $(3,2)$ のみ。値は $17$。

まとめ: 偶奇 → 法3、と刃を持ち替える消去法。「$-1$ の奇数乗は $-1$」「3で割れない数の平方は1」という2つの小さな道具を組み合わせると、無限個の候補がまとめて消える。

発展。 実は $p^q+q^p$ が素数になる組は、$(2,3)$ 型のほかには1つも知られていない。2つの素数の組合せだけの問題なのに、その先はまだ分かっていない。問題の意味は易しいのに答えが分かっていない、整数論によくある問いの例だ。

別解

法の選び方:なぜ「3」を試すのか(得意な人向け)。 本解の法3は天下りに見える。候補の法を順に打診する思考をそのまま見せよう。

$2^q+q^2$ の余りを調べやすい法は、$2^q$ か $q^2$ の余りが単純になる法だ。

• 法4: $q\ge 3$ なら $2^q\equiv 0$、$q$ は奇数で $q^2\equiv 1$。和は $\equiv 1$。矛盾は出ない
• 法8: 同じく $2^q\equiv 0$、奇数の平方は $\equiv 1$。和は $\equiv 1$。やはり決まらない
• 法3: $2\equiv -1$ だから $2^q\equiv -1$($q$ 奇数)。$q$ が3の倍数でなければ $q^2\equiv 1$。和は $\equiv 0$ となり、当たり

平方の余りが単純な法(3, 4, 8)を並べ、$2^q$ の余りの周期と噛み合うものを探す。この「打診」の目で見ると、法3は偶然ではなく、$2\equiv -1(\mathrm{mod}3)$ という好都合の帰結だと分かる。合同式の問題で法をどう選ぶか。その判断こそがこの種の問題の本当の技術だ。

方針

解答

⓪ 発想(どう考え始めるか) 「素数でない」ことを示すには、1と自分以外の約数を実際に見つける。つまり因数分解を作るのが本筋だ。

決め手は、$m$ が奇数のときの恒等式 $x^m+1=(x+1)(x^{m-1}-x^{m-2}+\cdots -x+1)$($x=-1$ を代入すると0になるから、$x+1$ を因数にもつ)。$n$ が奇数の約数 $m(\ge 3)$ をもつなら $n=mt$ と書けて、$2^n=(2^t{)}^m$。$x=2^t$ を代入すれば、因数 $2^t+1$ が現れる。

① (1) の証明。 $n=mt$($m$ は3以上の奇数、$t$ は自然数)とする。$x=2^t$ とおくと

$$2^n+1=(2^t{)}^m+1=(2^t+1)\left((2^t{)}^{m-1}-(2^t{)}^{m-2}+\cdots +1\right)$$

ここで $m\ge 3$ より $n>t$ だから

$$1<2^t+1<2^n+1$$

つまり $2^t+1$ は $2^n+1$ の真の約数で、$2^n+1$ は素数でない。

② 素数になり得る $n$ の形。 (1)の対偶から、$2^n+1$ が素数なら $n$ は3以上の奇数の約数をもたない。すなわち $n$ は $2^k$ の形($n=1,2,4,8,16,\dots$)だ。

③ (2) の答え。 $n\le 10$ で2のべきの形は $n=1,2,4,8$。値を確かめる:

$$2^1+1=3,2^2+1=5,2^4+1=17,2^8+1=257$$

3, 5, 17 は素数。257 は $\sqrt{257}<17$ だから 2, 3, 5, 7, 11, 13 で割れないことを確かめればよく、実際どれでも割れないので素数。ほかの $n$($3,5,6,7,9,10$)はすべて3以上の奇数の約数をもつので、(1)より不適。

まとめ: 素数性の議論は「合成数になる仕組み=因数分解」から攻める。指数の奇数因子がそのまま因数分解を生むので、$2^n+1$ が素数になり得るのは $n$ が2のべきのときに限られる。

発展。 $2^{2^k}+1$ の形の数はフェルマー数と呼ばれる。$3,5,17,257,65537$ と5連続で素数だったため、フェルマーは「すべて素数」と予想した。だが次の $2^{32}+1=4294967297$ は $641$ で割り切れる(オイラーの発見)。その先、新しい素数は1つも見つかっていない。

別解

合同式で1行に畳む(得意な人向け)。 因数分解の恒等式を、合同式の言葉で書き直すとさらに短くなる。$n=mt$($m$ は3以上の奇数)とする。法を $2^t+1$ に取ると

$$2^t\equiv -1(\mathrm{mod}{2}^t+1)$$

(これは定義そのもの。)両辺を $m$ 乗すれば、$m$ が奇数だから

$$2^n=(2^t{)}^m\equiv (-1{)}^m=-1(\mathrm{mod}{2}^t+1)$$

すなわち $2^n+1\equiv 0$。つまり $2^t+1$ は $2^n+1$ を割り切る。あとは $1<2^t+1<2^n+1$ で真の約数と確認するだけだ。

恒等式の長い第2因子を書かずに、「$-1$ の奇数乗は $-1$」の一言で同じ約数に到達する。因数分解と合同式は、同じ事実の2つの表し方である。

方針

解答

⓪ 発想(どう考え始めるか) 「解が存在しない」ことの証明は、うまい法(割る数)を選んで両辺の余りを比べ、矛盾を出すのが基本だ。

平方数は法4で余り 0, 1 の2種類。だが $2023\equiv 3(\mathrm{mod}4)$ は $1+1+1$ で作れてしまい、矛盾が出ない。

そこで一段細かく、法8で見る。平方数の余りは 0, 1, 4 の3種類しかなく、3つ足しても余り7だけは作れない。$2023=8\cdot 252+7$ だから、これで結論が出る。法の選び方(4でだめなら8)が決め手だ。

① 平方数の余りを分類する。 整数 $t$ を偶奇で分ける。

• $t=2k$ のとき $t^2=4k^2$。$k$ が偶数なら $16$ の倍数で余り0、$k$ が奇数なら $4\times (奇数{)}^2$ で余り4
• $t=2k+1$ のとき $t^2=4k(k+1)+1$。$k(k+1)$ は連続2整数の積で偶数だから、$t^2=8m+1$ の形で余り1

よって $x^2,y^2,z^2$ の8で割った余りはどれも 0, 1, 4 のいずれか。

② 3つの和の余りを調べる。 0, 1, 4 から3つ(重複可)選んで足した和は

$$0,1,2,3,4,5,6,8,9,12$$

のいずれかで、8で割った余りとしては $0,1,2,3,4,5,6$ のどれか。余り7だけは決して作れない。

③ 矛盾。 一方、$2023=8\cdot 252+7$ だから、$x^2+y^2+z^2=2023$ の左辺の余りは7でなければならない。これは②に反する。よって整数解は存在しない。

まとめ: 「存在しない」ことは余りで考えて示す。平方数の余りの表(法8で 0, 1, 4)は、平方和の問題でよく使う道具だ。実は $8m+7$ の形の数はどれも3つの平方数の和では表せない。2023はその一例にすぎない。

発展。 逆も知られている。$4^a(8m+7)$ の形「以外」の自然数は、必ず3つの平方数の和で表せる(ガウスの三平方の定理)。表せない数がどんな数かまで、完全に分かっている。

別解

法4で追い込んでから、偶奇でとどめ(2段ロケット)。 法8の表を使わずに、法4と「連続整数の積」だけで落とす道もある。

まず法4。平方数の余りは 0 か 1 で、$2023\equiv 3(\mathrm{mod}4)$。余り3を作る組合せは $1+1+1$ しかない。つまり、解があるなら $x,y,z$ はすべて奇数だ。

そこで $x=2a+1,y=2b+1,z=2c+1$ とおいて代入する。$(2a+1{)}^2=4a(a+1)+1$ だから

$$4\{a(a+1)+b(b+1)+c(c+1)\}+3=2023$$

整理して $a(a+1)+b(b+1)+c(c+1)=505$。ここでとどめ。$a(a+1)$ は連続2整数の積で必ず偶数。3つ足しても偶数だ。ところが右辺505は奇数。矛盾。

法8の「余りの表」を暗記していなくても、法4 → 奇数を強制 → 連続積の偶奇、という自前の2段で同じ結論に届く。実はこの計算は、法8の表の「奇数の平方は $8m+1$」を自分の手で見つけ直していることと同じだ。

方針

解答

⓪ 発想(どう考え始めるか) (1)の写像で $(3,2)$ から次々に解が作れる。だが「4番目」と言い切るには、この列がすべての解を尽くしていることが要る。

そこで逆向きの写像 $(x,y)\mapsto (3x-4y,3y-2x)$ を考える。これも解を解に移し、しかも($y\ge 3$ の解なら)$x$ を真に小さくする。どんな解もこの下降を繰り返すと、いつか最小解 $(3,2)$ に落ちる。つまり、逆に $(3,2)$ から昇る列がすべての解だ。

生成(作る)と下降(全部であることの保証)の両輪で、解の全リストが確定する。

① (1) の証明。 代入して展開する:

$$(3x+4y{)}^2-2(2x+3y{)}^2=(9x^2+24xy+16y^2)-2(4x^2+12xy+9y^2)=x^2-2y^2=1$$

② 解の列を作る。 最小の解は $y=1,2$ を試して $(3,2)$($y=1$ は $x^2=3$ で不適)。(1)の写像を繰り返すと

$$(3,2)\to (17,12)\to (99,70)\to (577,408)$$

($x$ は $3x+4y>x$ で真に増えるから、この列は $x$ の小さい順に並ぶ。)

③ この列で全部であること。 解 $(x,y)$ に対し $(x^{\prime },y^{\prime })=(3x-4y,3y-2x)$ とおくと、①と同じ展開で $x^{\prime 2}-2y^{\prime 2}=1$。さらに $x^2=2y^2+1$ を使うと

• $x^{\prime }>0$: $3x>4y⟺9x^2>16y^2⟺9(2y^2+1)>16y^2⟺2y^2+9>0$ で常に成立
• $y^{\prime }\ge 1$: $3y>2x⟺9y^2>4x^2=8y^2+4⟺y^2>4$、つまり $y\ge 3$ なら成立
• $x^{\prime }<x$: $3x-4y<x⟺x<2y⟺x^2<4y^2⟺2y^2+1<4y^2$ で常に成立

よって $y\ge 3$ のどんな解も下降するとより小さい自然数解に移る。下降を繰り返すと $y\le 2$ の解、すなわち $(3,2)$ に必ず到達する。つまりすべての解は $(3,2)$ から②の列を昇って得られるものに限る。

④ 答え。 4番目の組は $(x,y)=(577,408)$。(検算: $577^2-2\cdot 408^2=332929-332928=1$。)

まとめ: 「作れる」ことと「それで全部」は別の仕事だ。無限降下の親戚である下降の議論が「間に解はない」を保証して、はじめて「4番目」が確定する。

発展。 $\frac{577}{408}=1.414215\cdots$ は $\sqrt{2}=1.414213\cdots$ と小数第5位まで一致する。$x^2-2y^2=1$ の解は $\sqrt{2}$ の最良クラスの近似分数を次々に与え、この型の方程式はペル方程式と呼ばれ、連分数の理論とつながっている。

別解

$(3+2\sqrt{2})$ 倍の意味(数としての掛け算)。 (1)の写像は、じつは「数を掛けているだけ」だ。左辺は $x^2-2y^2=(x+y\sqrt{2})(x-y\sqrt{2})$ と因数分解できる。そこで解 $(x,y)$ を数 $x+y\sqrt{2}$ で代表させる。$(3,2)$ は $3+2\sqrt{2}$ だ。掛け算してみると

$$(x+y\sqrt{2})(3+2\sqrt{2})=(3x+4y)+(2x+3y)\sqrt{2}$$

これで(1)の写像そのものが現れた。積 $(x+y\sqrt{2})(x-y\sqrt{2})=1$ どうしを掛けても積は1のままだから、解が解に移るのは当然である。この見方の御利益は計算にもある。4番目の解は $(3+2\sqrt{2}{)}^4$ で、2乗を2回すればよい:

$$(3+2\sqrt{2}{)}^2=17+12\sqrt{2},(17+12\sqrt{2}{)}^2=577+408\sqrt{2}$$

3回の写像が2回の平方に縮んだ。「解の変換=数の掛け算」という視点は、この型の方程式の理論全体の基礎である。

方針

解答

⓪ 発想(どう考え始めるか) 3変数に方程式1本では、自由度が高すぎるように見える。だが $x\le y\le z$ から $\frac{1}{x}\ge \frac{1}{y}\ge \frac{1}{z}$。最大の項 $\frac{1}{x}$ は「3項の平均以上」つまり $\frac{1}{x}\ge \frac{1}{3}\cdot \frac{1}{2}$、かつ単独では全体未満 $\frac{1}{x}<\frac{1}{2}$ だ。

この両側からのはさみうちで、$x$ は数個に絞られる。$x$ を固定すれば残りは2変数の同じ問題。同じ論法をもう一度使えば $y$ も絞られ、$z$ は式から自動的に決まる。

① $x$ を絞る。 $\frac{1}{2}=\frac{1}{x}+\frac{1}{y}+\frac{1}{z}\le \frac{3}{x}$ より $x\le 6$。また $\frac{1}{x}<\frac{1}{2}$ より $x\ge 3$。よって $x=3,4,5,6$。

② $x=3$ のとき。 $\frac{1}{y}+\frac{1}{z}=\frac{1}{6}$、$y\le z$ だから $\frac{1}{6}\le \frac{2}{y}$ かつ $\frac{1}{y}<\frac{1}{6}$ より $7\le y\le 12$。順に $z$ を求めると

• $y=7$: $z=42$ / $y=8$: $z=24$ / $y=9$: $z=18$ / $y=10$: $z=15$ / $y=12$: $z=12$(いずれも整数で適)
• $y=11$: $\frac{1}{z}=\frac{1}{6}-\frac{1}{11}=\frac{5}{66}$ で $z$ が整数にならず不適

この場合5組。

③ $x=4,5,6$ のとき。 同じはさみうちで

• $x=4$: $\frac{1}{y}+\frac{1}{z}=\frac{1}{4}$、$5\le y\le 8$ → $(4,5,20),(4,6,12),(4,8,8)$ の3組($y=7$ は不適)
• $x=5$: $\frac{1}{y}+\frac{1}{z}=\frac{3}{10}$、$y\ge x=5$ かつ $\frac{3}{10}\le \frac{2}{y}$ より $y\le 6$ → $y=5$ で $z=10$、$y=6$ は不適。1組
• $x=6$: $\frac{1}{y}+\frac{1}{z}=\frac{1}{3}$、$y\ge 6$ かつ $\frac{1}{3}\le \frac{2}{y}$ より $y\le 6$ → $y=z=6$ の1組

④ 結論。 あわせて $5+3+1+1=10$ 組:

$$(3,7,42),(3,8,24),(3,9,18),(3,10,15),(3,12,12),(4,5,20),(4,6,12),(4,8,8),(5,5,10),(6,6,6)$$

まとめ: 「大小順をつける → 最大項をはさむ → 先頭から確定」の反復。無限にありそうな分数の分解がはさみうち1つで有限の場合分けに落ちる。

発展。 $\frac{4}{n}=\frac{1}{x}+\frac{1}{y}+\frac{1}{z}$ が すべての $n\ge 2$ で解けるか、という問い(エルデシュ・シュトラウス予想)は、いまだに未解決だ。単位分数の分解は遊びのように見えて、今も研究されている問題につながっている。

別解

積の形に直す(因数分解を使う近道)。 2変数に落ちた後の $\frac{1}{y}+\frac{1}{z}=\frac{1}{6}$ は、分母を払って因数分解の形にできる。

$$6(y+z)=yz⟺yz-6y-6z+36=36⟺(y-6)(z-6)=36$$

あとは36の約数ペアを書き出すだけだ。$y\le z$ に対応して

$$(y-6,z-6)=(1,36),(2,18),(3,12),(4,9),(6,6)$$

の5組。$(y,z)=(7,42),(8,24),(9,18),(10,15),(12,12)$ となり、②の結果と一致する。$y=11$ が消える理由も明快で、$11-6=5$ が36の約数でないからだ。

$x=4$ の場合も同様に $(y-4)(z-4)=16$ から $(1,16),(2,8),(4,4)$ の3組。「$\frac{1}{y}+\frac{1}{z}=\frac{1}{k}$ ⟺ $(y-k)(z-k)=k^2$」という変形は、単位分数の2変数問題を約数の列挙に変える有効な道具だ(分子が1でないときは少し手直しがいる)。はさみうちと使い分けたい。

方針

解答

⓪ 発想(どう考え始めるか) 約数の総和は、素因数分解から機械的に計算できる。$N=2^{p-1}\cdot M$($M$ は奇素数)の約数は「$2^i$($i=0,\dots ,p-1$)」と「$2^{i}M$」で全部だ。だから総和は $(1+2+\cdots +2^{p-1})(1+M)$ という積にまとまる。

ここで、等比数列の和 $1+2+\cdots +2^{p-1}=2^p-1$ がちょうど $M$ 自身である、ということに気づけば解ける。あとは掛けるだけで $2N$ が現れる。

① 総和を積の形にする((1)の証明)。 $N=2^{p-1}M$ で $M$ は奇素数だから、約数の総和 $\sigma (N)$ は

$$\sigma (N)=(1+2+2^2+\cdots +2^{p-1})(1+M)=(2^p-1)(M+1)$$

② $M=2^p-1$ を代入する。

$$\sigma (N)=M(M+1)=M\cdot 2^p=2\cdot 2^{p-1}M=2N$$

これが示すべき等式。自分自身を除いた約数の和が $\sigma (N)-N=N$。つまり $N$ は「自分以外の約数の和が自分に一致する数」(完全数)である。

③ $p=5$ で確かめる((2)の答え)。 $M=2^5-1=31$ は素数で、$N=2^4\cdot 31=496$。約数の総和は

$$\sigma (496)=(1+2+4+8+16)(1+31)=31\cdot 32=992=2\cdot 496$$

たしかに成り立つ。

まとめ: 等比数列の和 $1+2+\cdots +2^{p-1}=2^p-1$ がそのまま $M$ に戻ってくる、という一致が証明の中心だ。$2^p-1$ 型の素数(メルセンヌ素数)1つにつき、完全数が1つ生まれる。

発展。 偶数の完全数はすべてこの $2^{p-1}(2^p-1)$ の形に限られる(オイラーの証明)。一方、奇数の完全数は「存在するかどうか」自体が2000年以上未解決のままだ。本問の等式はこの問題を考えるときの出発点になる。

別解

約数を書き並べて2系列を見る(具体で確かめるルート)。 $p=5$ の $N=496$ で、約数を実際に全部書いてみよう。

$$1,2,4,8,16,31,62,124,248,496$$

前半は $2^i$ の系列、後半はその31倍の系列だ。和を系列ごとに取ると

• 前半: $1+2+4+8+16=31$
• 後半: $31\times (1+2+4+8+16)=31\times 31=961$

合計 $31+961=31\times 32=992=2\times 496$。この計算を見ると、証明の構造が目に見える。「前半の和がちょうど31($=M$)になる」から、全体が $M(M+1)=M\cdot 2^p$ ときれいに畳まれるのだ。一般の $p$ の証明(本解)はこの表の内容をそのまま文字で書いたものである。

方針

解答

⓪ 発想(どう考え始めるか) 約数を全部掛ける、という一見つかみどころのない量は、ペアリングで簡単な式になる。約数 $d$ と $\frac{n}{d}$ を組にすると、各組の積はちょうど $n$ だ。

約数が $D$ 個なら組は $\frac{D}{2}$ 組で、積は $n^{D/2}$($\sqrt{n}$ が約数になる場合も、自分と組んだとして同じ式でよい)。すると条件 $n^{D/2}=n^3$ は、$n\ge 2$ から指数を比べて $D=6$。「約数がちょうど6個」という個数の問題に言い換えられる。

あとは、個数6を実現する素因数分解の型を比べるだけだ。

① 約数の積を求める。 約数 $d$ が $n$ の約数なら $\frac{n}{d}$ も約数で、$d\cdot \frac{n}{d}=n$。全約数をこの組に分ける(平方数のときの $\sqrt{n}$ は自分と組む)と、積は

$${\left(n\right)}^{D/2}=n^{D/2}$$

② 条件を個数で表す。 $n^{D/2}=n^3$ で $n\ge 2$ だから、指数を比べて $\frac{D}{2}=3$、すなわち $D=6$。

③ 約数6個の最小の数。 素因数分解 $n=p^a{q}^b\cdots$ に対し $D=(a+1)(b+1)\cdots$。$6=6$ または $6=3\times 2$ だから、型は

• $p^5$ 型: 最小は $2^5=32$
• $p^{2}q$ 型: 最小は $2^2\cdot 3=12$

よって最小は $n=12$。(検算: 12の約数 $1,2,3,4,6,12$ の積は $1728=12^3$。)

まとめ: 「約数の積 → $n^{D/2}$」「条件 → 個数 $D$」「個数 → 素因数分解の型」と、3回の言い換えで問題がだんだん簡単になっていく。ペアリング($d$ と $n/d$)は約数の問題でよく使う第一手だ。

発展。 同じ言い換えで、「約数の積が $n^4$」なら $D=8$。型は $p^7$(最小128)、$p^{3}q$(最小24)、$pqr$(最小30)で、答えは24になる。指数を1つ動かすだけで、型の競争の顔ぶれが変わる。

別解

2回書いて掛ける(平方数の心配が消えるルート)。 ペアの作り方で $\sqrt{n}$ の扱いが気になった人へ。ペアを作らずに済む方法がある。

約数全体の積を $P$ とする。約数を小さい順に書いた列と、大きい順に書いた列を、縦に並べて掛ける:

$$P^2=\prod _{d}d\cdot \prod _d\frac{n}{d}=\prod _d\left(d\cdot \frac{n}{d}\right)=n^D$$

(2列目が「大きい順」になるのは、$d\mapsto \frac{n}{d}$ が約数全体を逆順に並べ替えるから。)よって

$$P=n^{D/2}$$

$\sqrt{n}$ が約数かどうかの場合分けは、最初から現れない。これは、$1+2+\cdots +100$ を「逆順に書いて足す」ガウス少年の計算の、掛け算版だ。ペアにする代わりに全体を2回使う。この小さな変更で、例外処理が要らなくなる。

方針

解答

⓪ 発想(どう考え始めるか) 大きな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$ より大きい」という部品(発展の種)も、この視点の副産物だ。