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

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

r₂ = r₀ – q₁r₁ = a – q₁b,

r₃ = r₁ – q₂r₂ = b – q₂(a – q₁) = – q₂a + (1 + q₁ q₂)b,

.....

r_i-2 = s_i-2a + t_i-2b,

r_i-1 = s_i-1a + t_i-1b,

r_i = r_i-2 – q_i-1r_i-1 = a(s_i-2 – q_i-1s_i-1) + b(t_i-2 – q_i-1t_i-1)

.....

r_m = s_ma + t_mb.

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

r_m = НОД(a, b) = s_ma + t_mb.

При НОД(a, b) = 1; 1 º t_mb (mod a); b ^{– 1} º t_m (mod a).