Razširjeni Evklidov algoritem

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

${\displaystyle ax+by=\gcd(a,b)\!\,.}$

Prikaz postopka

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