Алгоритм Евклида (отыскания НОД 2-х чисел)

Пусть a>b. Тогда в силу теоремы делимости находим ряд равенств:

a=bq₁+r₁, 0<r₁<b

b=r₁q₂+r₂, 0<r₂<r₁

r₁=r₂q₃+r₃, 0<r₃<r₂

...…………………

r_n-2=r_n-1q_n+r_n, 0<r_n<r_n-1

r_n_–₁=r_nq_n₊₁.

Получение последнего равенства (то есть равенства с разложением без остатка) неизбежно, т.к. ряд b, r₁, r₂, …. – ряд убывающих целых чисел, который не может содержать более b положительных чисел, а значит рано или поздно в этом ряду возникнет «0».

Видим, что общие делители a и b, b и r₁, r₁ и r₂,..., r_n_–1 и r_n совпадают с делителями числа r_n (a,b)=(b,r₁)=(r₁,r₂)=…=(r_n_-₁,r_n)= r_n.

Таким образом, (a,b)=r_n.

Вышеизложенная идея нахождения НОД может быть реализована в виде алгоритма. Ниже приведены несколько вариантов реализации алгоритма Евклида.

Реализация алгоритма Евклида (вариант алгоритма с вычитанием)

Вход: a, b>0.

1.Если a>b Шаг 3

если a<b Шаг 2

если a=b Шаг 5 (выход)

2.Меняем местами a и b.

3.a:=a–b

4.Возвращаемся на Шаг 1.

5. Выход: a – НОД

Ниже приведен пример использования этой реализации алгоритма.

Пример

a=603, b=108

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