§A4.9無限降下法

1 最小反例の考え方

「反例がない」と直接示す代わりに、「反例がある」と仮定します。反例に正整数$N$を対応させ、反例の中から$N$が最小のものを選びます。

その後、同じ条件を満たす反例で$N'<N$のものを作れば、最小反例の存在に矛盾します。重要なのは、単に別の解を作るだけでなく、必ず小さくすることです。

2 基本例：$x^2=2y^2$の不可能性

正整数解$(x,y)$があると仮定し、$x$を最小に選びます。$x^2$が偶数なので$x=2u$。代入すると

$y^2=2u^2$

であり、$(u,y)$も解です。しかし$u<x$。したがって最小性に矛盾します。

この短い証明には、次の3要素があります。

• 反例の集合が空でないという仮定
• 正の整数全体の空でない部分集合には最小元が存在するという整列性による、最小反例の存在
• 同じ性質を保ったまま小さくする構成

3 典型例：平方数の和

方程式$x^4+y^4=z^2$の不可能性では、原始ピタゴラス三つ組を使って、最後に$p^4+q^4=u^2$という同型の解を作ります。元の$z$より小さい$u$が得られるため降下です。

ここで、証明の途中に現れる因数分解だけを追っても降下とは言えません。新しい解が「同じ問題の解」であることと、比較する量が小さいことの両方が必要です。

4 最小性の選び方

問題に応じて最小化する量を選びます。

• 分子・分母をもつ分数解：分母、または分子と分母の和
• ピタゴラス型方程式：斜辺、最大の変数
• 組合せ構成：要素数、面積、操作回数
• 整数配置：最大値、総和、辞書式順序

複数の量を比較する場合は、「まず最大値、同じなら総和」のように順序を明示します。曖昧な「小さい」を使わないことが大切です。

5 演習

1. 最小反例法で$\sqrt3$が無理数であることを証明せよ。
2. $x^4+y^4=z^2$の降下証明で、新しい解のどの量が元より小さいかを明記せよ。
3. 「正整数解があれば、互いに素な正整数解もある」という約分が、どの問題で許されるかを説明せよ。
4. 無限降下と、単に「無限に続くから矛盾」と言う議論の違いを説明せよ。

整数論の具体例は 競技数学入門 にまとめています。