Алгоритм Евклида (отыскания НОД 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–1=r_nq_n+1.

Получение последнего равенства (то есть равенства с разложением без остатка) неизбежно, т.к. ряд 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-1,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. Каждый столбец таблице соответствует состоянию процесса на отдельном шаге.

Ответ: НОД(603,108)=9.

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

Вход: a, b >0.

1. Находим разложение a=bq+r, 0≤r<b

2. если r=0 Шаг 5 (выход)

3. a:=b; b:=r.

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

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

Пример

a=603, b=108

603=5·108+63

108=1·63+45

63=1∙45+27

45=1∙27+18

27=1∙18+9

18=2∙9+0

Ответ: НОД(603,108)=9.