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$