Сказать "Спасибо"
расширенный алгоритм Евклида
Расширенный алгоритм Евклида для целых a, b находит
Q,P,d = gcd(a,b) : aQ + Pb = d
Введем обозначения:
– остаток от деления, 
– частное от деления на i-ом шаге.
Алгоритм:
Алгоритм останавливается, когда = 0.
Пример. В табл. приведен числовой пример алгоритма для a = 136, b = 36. Найдено x = 4, y = –15, d = 4.
Введем обозначения:
– остаток от деления, – частное от деления на i-ом шаге.
Алгоритм:
Алгоритм останавливается, когда
= 0.Пример. В табл. приведен числовой пример алгоритма для a = 136, b = 36. Найдено x = 4, y = –15, d = 4.
| Шаг | Частное | Остаток | Подстановка |
| 1 | 3 | 28 | 28 = 136–3*36 |
| 2 | 1 | 8 | 8 = 36–1*28 = 36–1*(136–3*36) = –1*136+4*36 |
| 3 | 3 | 4 | 4 = 28–3*8 = 28–3*(–1*136+4*36) = 4*136–15*36 |
| 4 | 2 | 0 | 4*136–15*36 = 4 = gcd(136, 36) |
