§ 2.5. Доказательство корректности алгоритма Эвклида

Мы показали, что алгоритм обязательно остановится. Действительно, он не может выполнить больше делений с остатком, чем меньшее из двух введенных чисел. Но почему последний ненулевой остаток в точности равен наибольшему общему делителю? Чтобы это понять, нам понадобится один вспомогательный результат из тех, что математики называют леммами. Это слово древнегреческого происхождения, и означает оно то, что «предполагается» в доказательстве теоремы.

Лемма. Пусть натуральные числа. Предположим, что существуют такие целые числа при которых Тогда

Мы должны показать справедливость утверждения леммы. Воспользуемся, однако, сначала этой леммой и покажем, что последний ненулевой остаток в алгоритме Эвклида действительно равен наибольшему общему делителю. Применяя алгоритм к целым числам и предполагая, что остаток после деления равен нулю, имеем

На этот раз мы будем смотреть только на то, что происходит в левом столбце. Последнее равенство означает, что делится на Поэтому наибольший общий делитель этих двух чисел равен Другими словами,

Теперь в действие вступает лемма. Применяя ее к предпоследнему равенству, мы заключаем, что

причем последняя величина, как мы видели, равна Повторное применение леммы, на этот раз к предыдущему венству, дает

что опять равно Продолжая действовать таким же

образом до вершины столбца, мы заключаем, что что и требовалось доказать.

Доказательство корректности алгоритма будет завершено, если мы докажем лемму. Напомним, она утверждает, что если четыре неотрицательных целых числа связаны соотношением то Доказательство легче объяснить, если положить

Пока мы ничего не сделали, просто присвоили имена наибольшим общим делителям чисел и чисел Мы хотим доказать, что Доказательство проведем в два этапа. Сначала мы покажем, что а затем — что Равенство чисел немедленно следует из этих двух неравенств.

Покажем, что второе неравенство доказывается аналогично, и мы оставляем его в качестве упражнения. Напомним, что Тогда делит как а, так и Это означает, что существуют такие натуральные числа что

Подставляя эти значения в равенство получаем Другими словами,

Но последнее равенство означает, что s делится на

Подведем итог. По предположению, , поэтому делит Но проведенные вычисления показывают, что также делит число s. Поэтому является общим делителем чисел Однако наибольший из таких общих делителей, поэтому что мы и хотели доказать.

Отметим, что в доказательстве существенно используется соотношение аналогичное соотношению в теореме

деления. Однако здесь нам нет необходимости предполагать, что s меньше на самом деле s не должно быть и положительным. Значит, предположение о том, что остаток от деления меньше делителя, используется не в доказательстве того, что последний ненулевой остаток является наибольшим общим делителем, а только для того, чтобы доказать, что алгоритм завершает работу.