§ 3. АЛГОРИТМ ЕВКЛИДА И КОНЕЧНЫЕ ЦЕПНЫЕ ДРОБИ

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

Рассмотрим наиболее простой способ нахождения наибольшего общего делителя двух целых чисел.

ПРЕДЛОЖЕНИЕ 3.1. Пусть а - два целых числа, и

Тогда .

Доказательство. Из (1) следует, что любой общий делитель чисел а и b есть делитель числа и любой общий делитель чисел есть делитель числа а. Поэтому множество всех общих делителей чисел а и b совпадает с множеством всех общих делителей чисел b и . Отсюда следует, что положительный общий делитель чисел а и b совпадает с положительным общим делителем чисел .

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

Если то Если же то рассуждения повторяем, отправляясь от b и . В результате получим цепочку равенств

Мы получили убывающую последовательность натуральных чисел

которая не может быть бесконечной. Поэтому существует остаток, равный нулю; пусть

На основании предложения 3.1 из равенств (2) следует, что . Итак, мы приходим к выводу: если к целым числам а, b, где применить алгоритм Евклида, то последний ненулевой остаток в этом алгоритме есть