algorytm Euklidesa

algorytm Euklidesa,

mat. metoda wyznaczania największego wspólnego dzielnika (NWD) 2 liczb całkowitych lub 2 wielomianów (znana już w starożytności).

Schemat czynnościowy algorytmu Euklidesa dla liczb orzeka: weź liczby a i b, oznacz przez M większą z nich [max (a, b)], a przez m mniejszą [min (a, b)], oblicz resztę z dzielenia M : m [r = reszta (M : m)]. Gdy ta reszta jest zerem, wówczas m jest szukanym NWD liczb a i b; jeżeli reszta r ≠ 0, wówczas w miejsce M weź m [m → M], w miejsce m weź r [r → m], po czym kontynuuj (pętla powrotna) obliczanie reszty z dzielenia nowych wartości M i m itd., aż któraś z kolei reszta będzie równa zeru. Algorytm Euklidesa jest także nazywany metodą kolejnych dzieleń lub algorytmem ułamka ciągłego.

Euklidesa algorytm, schemat wykonawczy