4. Алгоритм Евклида.

Метод доказательства теоремы 2 очень быстро приводит к цели, но он не дает средства для фактического вычисления d. Предлагаемый способ — найти наименьшее натуральное число в бесконечном множестве чисел М — совершенно не эффективен. Однако деление с остатком позволяет быстро «спускаться» внутри М к наименьшему натуральному числу, содержащемуся в М, т. е. к наибольшему общему делителю. Именно, поделим с остатком а на b (считаем, что ), затем b на первый остаток, затем первый на второй и т. д. Получим цепочку равенств и неравенств:

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

Покажем, что последний отличный от нуля остаток равен b). Для этого сначала пересмотрим все равенства снизу вверх: делится на как сумма двух чисел, делящихся на тоже делится на и т. д. К третьему сверху равенству мы придем, зная, что делятся на и заключим отсюда, что делится на . Из второго заключим, что b делится на из первого — что а делится на Таким образом, а и b делятся на

Пусть теперь d — какой-либо общий делитель для а и b. Пересмотрим равенства сверху вниз с точки зрения делимости на d. Из первого равенства заключаем, что как разность двух чисел, делящихся на d, делится на d. Из второго — что делится на d по той же причине, и т. д.

Из предпоследнего заключим, что делится на d и, следовательно, Итак, оказывается общим делителем, причем наибольшим.

Изложенный способ отыскания называется алгорифмом Евклида, он известен уже более 2 000 лет. В процессе доказательства мы вновь установили свойство (2) н. о. д. Далее, из сказанного ранее ясно, что все остатки принадлежат множеству М, что дает доказательство и свойства (1), причем представление остатков в виде легко осуществляется шаг за шагом. Таким образом, алгорифм Евклида дает не только способ вычисления н.о.д. чисел а и но и его линейное представление в виде

Пример. Пусть Найти их и найти его линейное представление.

Решение: . Таким образом, Далее, . Таким образом, при