НОД, решение ax+by=1, нахождение обратного элемента по модулю

Бинарный алгоритм Евклида.

Этот алгоритм использует соотношения для НОД:

НОД(2*a, 2*b) = 2*НОД(a,b)

НОД(2*a, b) = НОД(a,b) при нечетном b,

Он иллюстрируется следующей программой:

m:= a; n:=b; d:=1; {НОД(a,b) = d * НОД(m,n)} while not ((m=0) or (n=0)) do begin if (m mod 2 = 0) and (n mod 2 = 0) then begin d:= d*2; m:= m div 2; n:= n div 2; end else if (m mod 2 = 0) and (n mod 2 = 1) then begin m:= m div 2; end else if (m mod 2 = 1) and (n mod 2 = 0) then begin n:= n div 2; end else if (m mod 2=1) and (n mod 2=1) and (m>=n)then begin m:= m-n; end else if (m mod 2=1) and (n mod 2=1) and (m<=n)then begin n:= n-m; end; end; {m=0 => ответ=d*n; n=0 => ответ=d*m}

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

Алгоритм Евклида можно расширить так, что он не только даст НОД(a,b)=d, но и найдет целые числа x и y, такие что ax + by = d.

Псевдокод

Исходник на Си