数学オリンピック / 数論

無限降下法

無限降下法は「解がある」と仮定して、そこからもっと小さい解を作り続ける方法です。正の整数は無限に下がれないので、矛盾が出ます。

考え方

証明を見る

\(\sqrt2=a/b\,(\gcd(a,b)=1)\) と仮定します。すると \(a^2=2b^2\) なので \(a\) は偶数、\(a=2k\) と書けます。代入すると \(4k^2=2b^2\)、よって \(b^2=2k^2\) で \(b\) も偶数です。

つまり a,b がともに偶数となり、既約分数という仮定に反します。これは「より小さい分数に下げられる」ことと同じで、降下が止まりません。

方程式 \(x^2=2y^2\) に正整数解がないことを示します。

上の証明と同じで、解があれば偶数で割れてより小さい解ができ、無限降下になります。

\(x^4+4y^4=z^2\) 型の問題で降下が使える理由を説明します。

Sophie Germain の因数分解 \((x^4+4y^4)=(x^2-2xy+2y^2)(x^2+2xy+2y^2)\) から、互いに素条件をつけて小さい解を作る流れが典型です。

ピタゴラス三つ組の性質 \(x^2+y^2=z^2\) を調べるときの入口。

原始三つ組のパラメータ表示を使うと、「もし別の条件も満たすならさらに小さい三つ組が作れる」という降下の形に持ち込みやすくなります。