Razširjeni Evklidov algoritem

Iz Wikipedije, proste enciklopedije
Jump to navigation Jump to search
Prikaz postopka

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

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