Algorytm Euklidesa

Praktycznym i szybkim sposobem obliczania największego wspólnego dzielnika dwóch liczb całkowitych jest algorytm Euklidesa. Jest to jeden z najstarszych algorytmów - został opisany przez Euklidesa ok roku 300 p.n.e.. Opiera się on na spostrzeżeniu, że jeśli od większej liczby odejmiesz mniejszą, to mniejsza liczba i otrzymana różnica będą miały taki sam największy wspólny dzielnik jak pierwotne liczby. Jeśli w wyniku kolejnego odejmowania otrzymasz parę równych liczb, oznacza to, że znalazłeś nwd.

Algorytm Euklidesa jest algorytmem rekurencyjnym, chociaż w bardzo prosty sposób można go przekształcić do formy iteracyjnej. Mając do policzenia NWD$(a, b)$ sprawdzamy, czy $b = 0$. Jeśli tak jest, to nwd$(a, b) = a$. W przeciwnym przypadku wywołujemy rekurencyjnie algorytm dla liczb $b$ i reszty z dzielenia $a$ przez $b$.

Dane są dwie liczby naturalne $a$ i $b$.
1. Jeśli $b \neq 0$ oblicz $c$ jako resztę z dzielenia $a$ przez $b$ i zastąp $a$ przez $b$, zaś $b$ przez $c$.
2. Jeżeli $b = 0$, nwd wynosi $a$, w przeciwnym przypadku wróć do punktu pierwszego i kontynuuj.

Nasuwa się pytanie, czy takie postępowanie zawsze się skończy. Istotnie dla liczb naturalnych zawsze tak jest. Korzyść z algorytmu Euklidesa jest taka, że ostatnia niezerowa reszta jest, co łatwo sprawdzić, największym wspólnym dzielnikiem liczb $a$ i $b$.

Przykład
nwd$(243, 111) = ?$
$243 \div 111 = 2$, reszty $21$
$111 \div 21 = 5$, reszty $6$
$21 \div 6 = 3$, reszty $3$
$6 \div 3 = 2$, reszty $0$
Ostatnia niezerowa reszta wynosi $3$.
nwd$(243, 111) = 3$