整数問題でいちばん扱いにくいのが、「解が存在しないことを示せ」という設問です。存在することは1つ見つければ済みますが、存在しないことは、いくら探しても示せません。
この記事では、数強塾の独自研究として、「存在しない」の証明を3つの段階に整理します。第1段階で片づくならそれがいちばん速く、片づかないときに第2・第3段階へ上がる。どこまで上がる必要があるかを見分けられることが、この分野の実力です。
整数問題シリーズの一部です。まずは 整数問題の3つの方針 をご覧ください。
1．「存在しない」を示す3段階
| 段階 | 方法 | 効くとき | 労力 |
|---|---|---|---|
| 第1 | 余りで矛盾を出す | 両辺の余りが「絶対に一致しない」とき | 数行 |
| 第2 | 背理法＋既約性（互いに素と仮定） | 比や分数の形で、割り切れなさを使いたいとき | 半ページ |
| 第3 | 無限降下法 | 「解から、もっと小さい解が作れてしまう」とき | 1ページ |
【見分け方】まず第1段階を試してください。余りで分類で扱った剰余表を当てて、矛盾が出れば終わりです。出ないときは、「解を1つ持ってきたら、そこから小さい解が作れないか」を考える。ここで作れるなら第3段階です。
2．第1段階 ―― 余りで矛盾を出す
いちばん速い方法です。法の選び方さえ分かっていれば、数行で終わります。
【例題1】
を満たす整数の組は存在しないことを示せ。
平方数があるので法は 。平方数を で割った余りは か だけなので、 の余りは のいずれか。ところが で余りは 。集合が交わらないので、解は存在しません。■
この形で片づく問題は、「余りの集合が最初から交わらない」という単純な構造をしています。逆に、余りの集合が交わってしまうと、この方法は使えません。そのときが第2・第3段階の出番です。
3．第2段階 ―― 背理法と「既約性」
背理法の骨格は「成り立つと仮定して、矛盾を出す」ですが、整数問題では仮定の置き方にコツがあります。それが「既約であるとしてよい」という一手です。
【例題2】
が無理数であることを示せ。
が有理数だと仮定します。すると （ は自然数）と書けますが、ここで と は互いに素としてよい——約分し切った形にできるからです。
両辺を2乗して 。よって は偶数、したがって も偶数（奇数の2乗は奇数だから）。 とおくと 、すなわち 。同じ論法で も偶数。
と がどちらも偶数になり、互いに素という仮定に反します。■
「互いに素としてよい」の正体
これは実質的に、無限降下法を1回だけ使った形です。「約分し切った」と言えるのは、約分を無限には続けられないから。自然数が無限に小さくなれないという事実を、静かに使っています。
4．第3段階 ―― 無限降下法
第2段階の「既約性」を、何度でも繰り返せる形にしたものが無限降下法です。
図1：無限降下法の考え方。解があると仮定 → そこから必ず小さい解が作れると示す → 自然数は無限に小さくなれない → 矛盾。「1より下がない」という当たり前の事実が、証明の心臓です。
【例題3】
を満たす自然数の組 は存在しないことを示せ。
ステップ1：法 で、 と を縛る
平方数を で割った余りは か 。右辺は の倍数なので、。ところが余りの組み合わせは の3通りしかなく、 になるのは のときだけ。すなわち
も も の倍数
ステップ2：小さい解を作る
とおいて代入すると 、両辺を で割って
右辺 が の倍数になったので、 は素数だから も の倍数です。 とおきます。
さらに代入して 、両辺を で割ると
元とまったく同じ形の式が出てきました。しかも なので、解が に縮んでいます。
ステップ3：矛盾
この操作は何度でも繰り返せます。すると と、自然数が無限に小さくなり続けることになります。自然数に より小さいものはないので、これは不可能。よって、はじめの仮定（自然数解が存在する）が誤りです。■
【検算】、 の全数探索でも、解は1つも見つかりませんでした。
別の書き方：最小性を使う
「無限に小さくなる」と書く代わりに、最初から最小の解を取る書き方もあります。「解が存在するとして、 が最小のものを取る。すると上の操作で を持つ解が作れ、 の最小性に反する」——こちらのほうが答案としては短く、減点されにくいです。
5．降下法が効く問題の見分け方
降下法のサイン
余りの議論をした結果、「すべての文字が同じ数の倍数になる」と出たとき。
例題3では、法 から が の倍数と出て、そこから も の倍数と出ました。全員が同じ数で割れる＝そのまま割って同じ式に戻れる＝降下できる、という流れです。
逆に、余りの議論で一部の文字だけが縛られる場合は、降下法にはなりません。その場合は別の方針（積の形や不等式）を探します。
6．応用 ―― ピタゴラス数の隠れた性質
降下法と同じ「全員を縛る」発想は、存在証明の否定以外にも使えます。
【例題4】
を満たす自然数について、 は必ず の倍数であることを示せ。
の倍数であること
がどちらも の倍数でないとすると、 より 。平方数の余りに はないので矛盾。よって の少なくとも一方は の倍数です。
の倍数であること
まず、 がどちらも奇数だと となり、平方数の余りに はないので不可能。よって少なくとも一方は偶数です。仮に が奇数、 が偶数とすると は奇数。ここで
はともに奇数なので と はどちらも偶数。 とおくと となり 、。ここで は奇数なので、 の一方は偶数。したがって は偶数、よって は偶数。 は の倍数です。（ がともに偶数の場合は、 が偶数という結論はそのまま成り立ちます。）
以上より は の倍数かつ の倍数、すなわち の倍数。■
【検算】 の範囲にあるピタゴラス数をすべて調べたところ、例外は1つもありませんでした。最小の でも です。
7．【この先へ】フェルマーが降下法で示したこと
無限降下法は、フェルマーが自ら「私の発明した方法」と呼んだものです。彼がこの方法で証明したのが、次の命題です。
を満たす自然数 は存在しない
証明の骨格は例題3と同じで、「解があれば、より小さい解が作れる」を示します（ただし途中でピタゴラス数の一般形が必要になるため、高校範囲でやり切るには長い議論になります）。
【なぜ重要か】この命題から、 に自然数解がないことがただちに従います（ だから）。つまりフェルマーの最終定理の の場合は、降下法だけで完全に解決しているのです。一般の が解決したのは1995年ですが、 は高校生でも筋を追えます。
検算として の範囲を全数探索しましたが、 が平方数になる組は1つもありませんでした。
8．答案の書き方
【答案例（骨格）：例題3】
自然数解が存在すると仮定し、そのうち が最小であるものを1つとって とする。
平方数を で割った余りは または である。 は の倍数だから、余りの組み合わせより 、すなわち はともに の倍数。
とおくと となり、 は の倍数だから も の倍数。 とおいて整理すると 。
も自然数解であり となるが、これは の最小性に反する。
よって自然数解は存在しない。■
答案で落としてはいけない3点
- 「最小のものを取る」と先に宣言する。これがないと、最後の矛盾が成立しません。
- 作った が自然数であることを言う。 で割り切れることを示したのは、このためです。
- 矛盾の中身を明示する。「 の最小性に反する」と書き切ります。
9．よくあるミス
1降下できていないのに降下法と書く
小さい解が実際に作れることを示さなければ、降下法にはなりません。「小さくなりそう」では証明になりません。
2最小性の宣言を忘れる
「解が存在すると仮定する」だけで始めると、小さい解を作った後に矛盾が言えません。最初に「最小のものを取る」と書きます。
3 を解に数えてしまう
は では成り立ちます。「自然数解」と「整数解」で結論が変わるので、設問の語を必ず確認してください。
4第1段階で済むのに降下法を持ち出す
に降下法は不要です。まず余りを試す。それで終わるなら、それがいちばん強い答案です。
10．練習問題
【練習1】
が無理数であることを示せ。
【練習2】
を満たす自然数の組は存在しないことを示せ。
【練習3】
を満たす自然数の組は存在しないことを示せ。
【答】
練習1 （ は互いに素な自然数）と仮定すると 。よって は の倍数で、 は素数だから も の倍数（素数の顔②）。 とすると 、 より も の倍数。互いに素に反する。■
練習2 右辺は偶数なので は偶数、よって奇数である文字は 0 個か 2 個。
(i) 3つとも偶数なら 等とおいて代入すると 、すなわち 。さらに右辺が偶数なので同じ議論を繰り返せ、解が半分ずつ小さくなり続けて矛盾（降下法）。
(ii) 奇数が2つのとき、たとえば が奇数で が偶数とすると、左辺は 、右辺 は が偶数なので の倍数。 で矛盾。
よって解は存在しない。■
練習3 左辺 は すなわち偶数なので は偶数。 とおくと 、両辺を で割って 。よって は偶数で 。代入して 、両辺を で割って 。よって も偶数で 。代入して 、両辺を で割ると ——元と同じ形で、すべてが半分になりました。最小性に反するので解は存在しない。■
11．まとめ
この記事の要点
- 「存在しない」の証明は3段階。まず第1段階（余りで矛盾）を試すのが鉄則。
- 第2段階の「互いに素としてよい」は、降下法を1回だけ使った形。
- 第3段階の無限降下法は、「解から必ず小さい解が作れる」を示して、自然数の下限と矛盾させる。
- 降下法のサインは「余りの議論で、すべての文字が同じ数の倍数になる」こと。
- 答案では「最小のものを取る」と先に宣言し、最後に最小性に反すると書き切る。
12．よくある質問
Q. 背理法と無限降下法は違うものですか？
A. 無限降下法は背理法の一種です。ただの背理法が「仮定から直接矛盾を出す」のに対し、降下法は「仮定からより小さい反例を作り、自然数の下限と矛盾させる」という特定の型を持ちます。降下法は背理法の中の一パターンと考えてください。
Q. 「最小のものを取る」と言ってよい根拠は何ですか？
A. 自然数の集合は、空でなければ必ず最小元をもつという性質（整列性）です。高校ではこれを当然のこととして使って構いません。ただし整数全体や有理数では成り立ちません（下に限りがないため）。だから「自然数解」に限定された問題でしか使えない、という点は意識しておいてください。
Q. 降下法は入試で出ますか？
A. 出ます。ただし多くの場合、誘導つきです。「(1) がともに3の倍数であることを示せ」「(2) 解が存在しないことを示せ」のように、ステップ1が小問として与えられます。誘導の意味が読めるかどうかが勝負なので、この記事の「サイン」を覚えておくと有利です。
Q. 第1段階で矛盾が出ないとき、次に何をすればいいですか？
A. 法を変えて2〜3回試すのが先です（ の順）。それでも出なければ、「余りの議論で全部の文字が縛られていないか」を見てください。全部が同じ数の倍数になっていれば降下法です。どちらでもなければ、そもそも解が存在する問題である可能性を疑ってください。
13．関連ページ
- 整数問題の3つの方針｜総論・判断基準
- ① 積の形に持ち込む整数問題
- ② 余りで分類する整数問題（第1段階の道具）
- ③ 不等式で絞る整数問題
- 一次不定方程式 ax+by=c｜互除法で解を「作る」
- 素数の使い方｜「素数である」こと自体が絞り込みになる
- 平方根とは｜根号・有理数・無理数を解説【中3】
「存在しないことを示せ」で手が止まりませんか
この設問は、誘導の意味が読めるかどうかで結果が分かれます。数強塾では、小問がなぜその順番で置かれているのかを読み解く訓練を、プロ講師が完全1対1で行います。
