【神戸大学数学】公約数が1または5に限られる理由｜ユークリッドの互除法で見る整数問題

神戸大学の整数問題から、「公約数をどう見るか」を整理します。

今回のポイントは、次の恒等式です。

(n²+1) − (n+2)(n−2) = 5

この式を使って、n+2 と n²+1 の公約数が1または5に限られることを示します。計算を進めることより、「なぜ右辺が5になっているのか」を見ると、この問題の狙いが見えやすくなります。

まずはInstagramの解説動画

実際の問題を、具体例から順に動画で解説しています。

問題

自然数 n について、恒等式

(n²+1) − (n+2)(n−2) = 5

を利用して、n+2 と n²+1 の公約数は1または5に限ることを示します。

まず n=1〜5 で実験してみる

いきなり文字だけで考えにくい場合は、具体的な値を代入してみます。

n	n+2	n2+1	最大公約数
1	3	2	1
2	4	5	1
3	5	10	5
4	6	17	1
5	7	26	1

確かに、ここでは最大公約数として1か5しか現れません。しかし、具体例をいくつ確認しても「すべての自然数 n でそうなる」ことの証明にはなりません。

公約数とは「両方を割り切る数」

例えば35と15を考えます。

• 35の約数：1、5、7、35
• 15の約数：1、3、5、15

共通している1と5が公約数で、その中で最も大きい5が最大公約数です。

また、5に注目すれば

35 = 5×7　　15 = 5×3

と書けます。つまり「d が2つの数の公約数である」とは、2つの数がどちらも d の整数倍であるということです。

本題：公約数 d は5も割り切る

n+2 と n²+1 の公約数を d とします。

すると、d は n+2 を割り切ります。したがって、その整数倍である

(n+2)(n−2)

も d で割り切れます。n が自然数なら n−2 も整数なので、この部分に問題はありません。

一方、d は n²+1 の公約数でもあるので、もちろん

n²+1

も d で割り切れます。

つまり、次の恒等式の左辺にある2つの項は、どちらも d の倍数です。

(n²+1) − (n+2)(n−2) = 5

d の倍数から d の倍数を引いた数も、d の倍数です。したがって、右辺の5も d で割り切れなければなりません。

d｜5

5の正の約数は1と5だけなので、

d = 1 または 5

となります。これで、n+2 と n²+1 の公約数が1または5に限られることが示せました。

この恒等式はユークリッドの互除法と同じ構造

問題の恒等式を移項すると、

n²+1 = (n+2)(n−2) + 5

となります。

これは一般に

A = BQ + R

という形です。一方の数から、もう一方の数の整数倍を引いても、共通して割れる数は変わりません。最大公約数の記号 gcd を使えば、

gcd(A,B) = gcd(B,R)

というユークリッドの互除法の基本的な考え方です。

今回なら、

gcd(n²+1, n+2) = gcd(n+2, 5)

と見ることができます。右側には5しか残っていないため、共通因数の候補も5の約数まで一気に絞られます。

この問題で見るべきポイント

この問題では、恒等式を展開できるかどうか以上に、「なぜ差を取った結果が5になっているのか」を見ることが重要です。

複雑な式同士の公約数を直接探すのではなく、一方からもう一方の整数倍を引いて、小さな数に公約数の候補を押し込む。この構造に気づくと、一気に見通しが立ちます。

ユークリッドの互除法を知っている人なら見覚えのある形ですが、公式として覚えるだけでなく、「両方を割る数なら、その差も割る」というところから理解しておくと、整数問題で使いやすくなります。

ユークリッドの互除法の手順を確認したい人へ

この問題で使っている公約数の考え方を基礎から確認したい場合は、ユークリッドの互除法を長方形から理解する解説を先に読むと、割り算の余りで最大公約数を求める流れが整理できます。