§ 2.4. Алгоритм Эвклида

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

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

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

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

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

К счастью, наибольший общий делитель можно подсчитать и другим, весьма эффективным способом. Эвклид приводит его в предложениях 1 и 2 книги VII своих «Элементов». Алгоритм Эвклида действует следующим образом. Разделим а на с остатком; назовем этот остаток Если то разделим на с остатком; пусть остаток второго деления. Аналогично, если то разделим на и получим новый остаток Таким образом, цикл алгоритма состоит из одного деления с остатком, причем делимое равно остатку, полученному в цикле, а делитель — остатку, полученному в цикле. Цикл повторяется до тех пор, пока мы не получим нулевого остатка; наименьший ненулевой остаток является наибольшим общим делителем чисел

Применим алгоритм Эвклида для вычисления наибольшего общего делителя чисел 1234 и 54. Деления с остатком выглядят так:

Последний ненулевой остаток равен 2, поэтому

Отметим, что неполные частные не принимают непосредственного участия в подсчете наибольшего общего делителя. Опишем теперь алгоритм, следуя модели, предложенной в § 2.1 и § 2.2.

Алгоритм Эвклида

Ввод: натуральные числа а и b, а Вывод: наибольший общий делитель чисел а и b.

Шаг 1. Положить

Шаг 2. Заменить значение остатком от деления А на В и перейти к шагу 3.

Шаг 3. Если то сообщить: «наибольший общий делитель чисел равен В», и остановиться; в противном случае перейти к шагу 4.

Шаг 4. Заменить значение А на значение В, значение В на значение и возвратиться к шагу 2.

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

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

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

получаем цепочку

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

С помощью рассуждения из предыдущего параграфа можно получить верхнюю оценку на число делений, необходимое для вычисления наибольшего общего делителя. Вернемся к неравенствам (4.1). Каждое число в последовательности строго меньше предыдущего. Поэтому наибольшее возможное значение остатка в каждом делении на единицу меньше значения остатка на предыдущем делении. Если бы в каждом цикле это наибольшее возможное значение достигалось, то для получения нулевого остатка нам потребовалось бы делений. Ясно, что это и есть наихудший возможный случай. Поэтому при применении алгоритма Эвклида к паре чисел а число делений не превосходит

На самом деле, несложно показать, что при число делений всегда меньше Зафиксируем число Тогда задачу лучше переформулировать так: для каких наименьших взаимно простых вычисление требует делений? Заметим, что для того, чтобы числа были минимально возможными, частные на каждом шаге тоже должны быть минимально возможными. Если теперь предположить, что делитель меньше делимого, то ясно, что наименьшее возможное частное двух целых чисел равно 1. Предположим, что мы выполнили делений до получения нулевого остатка. Тогда последовательность остатков имеет вид

Мы уже видели, однако, что в наихудшем возможном случае все неполные частные равны 1. Запишем теперь все деления,

начиная с последнего. В силу взаимной простоты чисел мы получаем

Вот как выглядит последовательность остатков при

Значит, наименьшая пара взаимно простых чисел для подсчета наибольшего общего делителя которых необходимо 10 делений с остатком, это Заметьте, что хотя число и наименьшее, все равно оно больше, чем Приведенная выше последовательность — это начало знаменитой последовательности Фибоначчи. Вы снова встретитесь с ней в упражнении 6.