Метод бесконечного спуска

Доказательство того, что квадратный корень из 2 (√2) — иррационален (то есть не может быть выражен в виде дроби с целыми числами), было открыто древними греками и, возможно, является самым ранним известным примером доказательства методом бесконечного спуска. Пифагорейцы обнаружили, что диагональ квадрата несоизмерима с его стороной, или, говоря современным языком, что квадратный корень из двух — иррационален. В связи с этим открытием часто упоминается имя Гиппаса из Метапонта. Некоторое время пифагорейцы держали открытие иррациональности квадратного корня из двух в секрете, а по легенде Гиппас был убит за его разглашение^[6][7][8]. Квадратный корень из двух иногда называют «числом Пифагора» или «константой Пифагора», например, Conway & Guy (1996)^[9].

Древние греки, не обладая алгеброй, разработали геометрическое доказательство методом бесконечного спуска (Джон Хортон Конвей представил другое геометрическое доказательство^[10]). Ниже приведено алгебраическое доказательство по аналогии:

Пусть √2 — рациональное число. Тогда его можно записать в виде

${\displaystyle {\sqrt {2}}={\frac {p}{q}}}$

для некоторых натуральных чисел p и q. Возведя обе части в квадрат, получим

${\displaystyle 2={\frac {p^{2}}{q^{2}}},}$

${\displaystyle 2q^{2}=p^{2},}$

то есть 2 делит p². Поскольку 2 — простое число, оно делит и p (по лемме Евклида). Значит, p = 2r для некоторого целого r.

Тогда

${\displaystyle 2q^{2}=(2r)^{2}=4r^{2},}$

${\displaystyle q^{2}=2r^{2},}$

что показывает, что 2 делит и q. Следовательно, q = 2s для некоторого целого s.

Отсюда

${\displaystyle {\frac {p}{q}}={\frac {2r}{2s}}={\frac {r}{s}}}$.

Таким образом, если бы √2 можно было записать в виде рационального числа, то его всегда можно было бы записать в виде дроби с меньшими числителем и знаменателем, и так далее, ad infinitum. Но это невозможно в множестве натуральных чисел. Поскольку √2 — вещественное число, которое может быть либо рациональным, либо иррациональным, остаётся только вариант, что √2 иррационален^[11].

Это доказывает, что если бы √2 было рациональным, не существовало бы «наименьшего» представления в виде дроби, так как любая попытка найти «наименьшее» представление p/q приводила бы к существованию ещё меньшего, что также является противоречием.

Пусть k — положительное целое число, и √k не является целым, но рационален и может быть выражен как mn для натуральных m и n. Пусть q — наибольшее целое, меньшее √k (то есть q — целая часть √k). Тогда

${\displaystyle {\begin{aligned}{\sqrt {k}}&={\frac {m}{n}}\\[6pt]&={\frac {m\left({\sqrt {k}}-q\right)}{n\left({\sqrt {k}}-q\right)}}\\[6pt]&={\frac {m{\sqrt {k}}-mq}{n{\sqrt {k}}-nq}}\\[6pt]&={\frac {\left(n{\sqrt {k}}\right){\sqrt {k}}-mq}{n\left({\frac {m}{n}}\right)-nq}}\\[6pt]&={\frac {nk-mq}{m-nq}}\end{aligned}}}$

Числитель и знаменатель были умножены на выражение (√k − q), которое положительно, но меньше 1, и затем упрощены независимо. Полученные произведения, обозначим их m′ и n′, также являются целыми числами и меньше m и n соответственно. Следовательно, для любых натуральных m и n, выражающих √k, существуют меньшие натуральные числа m′ < m и n′ < n с тем же отношением. Но бесконечный спуск по натуральным числам невозможен, значит, исходное предположение о рациональности √k неверно^[12].

Неразрешимость уравнения ${\displaystyle r^{2}+s^{4}=t^{4}}$ в целых числах достаточна для доказательства неразрешимости ${\displaystyle q^{4}+s^{4}=t^{4}}$ в целых числах, что является частным случаем Великой теоремы Ферма, и исторические доказательства последней строились через более общее доказательство первого с помощью бесконечного спуска. Следующее, более современное доказательство, охватывает оба случая, показывая, что пифагоров треугольник не может иметь две стороны, каждая из которых является квадратом или удвоенным квадратом, поскольку не существует наименьшего такого треугольника:^[13]

Пусть существует такой пифагоров треугольник. Тогда его можно привести к примитивному (то есть с взаимно простыми сторонами) пифагорову треугольнику с тем же свойством. Стороны примитивного пифагорова треугольника выражаются как ${\displaystyle x=2ab,}$ ${\displaystyle y=a^{2}-b^{2},}$ ${\displaystyle z=a^{2}+b^{2}}$, где a и b — взаимно простые числа, причём a+b нечётно, а значит, y и z нечётны. Свойство нечётности y и z означает, что ни y, ни z не могут быть удвоенным квадратом. Кроме того, если x — квадрат или удвоенный квадрат, то и a, и b — квадрат или удвоенный квадрат. Возможны три случая, в зависимости от того, какие две стороны предполагаются квадратами или удвоенными квадратами:

• y и z: В этом случае y и z — квадраты. Тогда прямоугольный треугольник с катетами ${\displaystyle {\sqrt {yz}}}$ и ${\displaystyle b^{2}}$ и гипотенузой ${\displaystyle a^{2}}$ также имел бы целые стороны, включая квадратный катет (${\displaystyle b^{2}}$) и квадратную гипотенузу (${\displaystyle a^{2}}$), причём гипотенуза ${\displaystyle a^{2}}$ меньше исходной ${\displaystyle z=a^{2}+b^{2}}$.
• z и x: z — квадрат. Прямоугольный треугольник с катетами ${\displaystyle a}$ и ${\displaystyle b}$ и гипотенузой ${\displaystyle {\sqrt {z}}}$ также имел бы две стороны (${\displaystyle a}$ и ${\displaystyle b}$), каждая из которых — квадрат или удвоенный квадрат, и меньшую гипотенузу (${\displaystyle {\sqrt {z}}}$ по сравнению с ${\displaystyle z}$).
• y и x: y — квадрат. Прямоугольный треугольник с катетами ${\displaystyle b}$ и ${\displaystyle {\sqrt {y}}}$ и гипотенузой ${\displaystyle a}$ имел бы две стороны (b и a), каждая из которых — квадрат или удвоенный квадрат, причём гипотенуза ${\displaystyle a}$ меньше исходной ${\displaystyle z=a^{2}+b^{2}}$.

В любом из этих случаев один пифагоров треугольник с двумя сторонами, являющимися квадратами или удвоенными квадратами, приводит к меньшему такому треугольнику, и так далее; поскольку такая последовательность не может продолжаться бесконечно, исходное предположение о существовании такого треугольника ошибочно.

Это означает, что уравнения

${\displaystyle r^{2}+s^{4}=t^{4},}$

${\displaystyle r^{4}+s^{2}=t^{4},}$ и

${\displaystyle r^{4}+s^{4}=t^{2}}$

не могут иметь нетривиальных решений, так как такие решения давали бы пифагоровы треугольники с двумя сторонами, являющимися квадратами.