Razširjen Evklidov algoritem

Iz Wikipedije, proste enciklopedije
Skoči na: navigacija, iskanje
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.