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 ta 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 wypadku wywołujemy rekurencyjnie algorytm dla liczb b i reszty z dzielenia a przez b.
1 .Dane są dwie liczby naturalne a i b.
2. Oblicz c jako resztę z dzielenia a przez b
3. Zastąp a przez b, zaś b przez c.
4. Jeżeli b = 0, to szukane NWD wynosi a, w przeciwnym
wypadku wróć do punktu drugiego 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.