Алгоритм Евклида.
1 Шаг. Делим а на (b¹0), если а /b, то (a, b) = b по лемме 1, если а = bq0 + r1, то (a, b)=(b, r1)
2Шаг. Делим b на r1 если (b /r1) => (b, r1) = r1, если b = r1q1+r2, то (b, r1) = (r1, r2).
3 Шаг. Делим r1 на r2 и т. д.
Поскольку остатки, получаемые в процессе деления, убывают и являются натуральными числами, то на каком-то шаге получим остаток, равный нулю, т.е. rn-1 = rnqn и тогда (rn-1, rn) = rn.
Задача 2. Доказать, что последний неравный нулю остаток в алгоритме Евклида является наибольшим общим делителем чисел (а) и (b).
Решение: Применим к числам (а) и (b) алгоритм Евклида:
a = bqo+r1 0£r1<b
b = r1q1 + r2 0£ r2 <r1
. . . . . . . . . . . . . . . . . . . . .
rn-2=rn-1•qn-1 +rn 0 
rn<rn-1
rn-1 =rnqn + 0
Из первого равенства по лемме 2 будем иметь:
(a, b) = (b, r1)
Из второго равенства алгоритма Евклида тоже по лемме 2 будем иметь (b, r1)= (r1 г2) и т. д.
Из последнего равенства (rn-1 , rn) = rn по лемме 1. Т.е. получили цепочку равенств (а, b) = (b, r1) = (r1, r2) = (r2, r3) = …..
=(rn-2, rn-1) = (rn-1, rn) = rn
Итак, (а, b)=rn.
Пример 2. Найти d = (3220,1550) с помощью алгоритма Евклида
Решение:
Итак, (3220, 1550) = 10 = r2
Задача 3. Доказать, что если d=(а,b), то $х, у 
Z :
d = ах + by.
Решение:
Применим к числам а иb алгоритм Евклида:
а = bq0 + r1
b = r1 q1 + r2
ri = r2q2 + r3
……………………
rn-3 = rn-2qn-2 + rn-1
rn-2 = rn-1qn + d, (d = rn)
Тогда, последовательно выражая, из последнего равенства, d = rn-2 - rn-1 qn (*) из предпоследнего rn-1 = rn-3 – rn-2qn-2 и т.д.
Из первого r1 = а-bqo и последовательно подставляя их в равенство (*) получаем: d = ах + by.