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

Позволяет найти не только НОД(a, b), но и мультипликативный обратный к b по модулю a. Преобразуем формулы для алгоритма Евклида, выразив все остатки ri через a и b:

r2 = r0q1r1 = a q1b,

r3 = r1q2r2 = bq2(a q1) = – q2a + (1 + q1 q2)b,

.....

ri-2 = si-2a + ti-2b,

ri-1 = si-1a + ti-1b,

ri = ri-2qi-1ri-1 = a(si-2qi-1si-1) + b(ti-2qi-1ti-1)

.....

rm = sma + tmb.

Расширенный алгоритм Евклида по данным целым числам a и b выдает rm, sm и tm, так что

rm = НОД(a, b) = sma + tmb.

При НОД(a, b) = 1; 1 º tmb (mod a); b – 1 º tm (mod a).