Система Orphus

расширенный алгоритм Евклида

Расширенный алгоритм Евклида для целых a, b находит
Q,P,d = gcd(a,b) : aQ + Pb = d

Введем обозначения: – остаток от деления, – частное от деления на 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)

Система Orphus

Комментарии