Razširjen Evklidov algoritem

Prikaz postopka

Razširjen 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 zadostita Bézoutovi identiteti

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

Razširjen 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$.