Razširjeni Evklidov algoritem

Prikaz postopka

Razširjeni Evklidov algoritem je razširitev Evklidovega algoritma. Poleg iskanja največjega skupnega delitelja dveh celih števil $a$ in $b$ poišče tudi celi števili $x$ in $y$, ki zadoščata Bézoutovi enakosti:

$ax+by=\gcd (a,b).$

Razširjeni Evklidov algoritem je še posebej uporaben, ko sta $a$ in $b$ tuji števili, ker je $x$ multiplikativni inverz števila $a$ po modulu $b$ in $y$ multiplikativni inverz števila $b$ po modulu $a$.