Algorytm Euklidesa:

Algorytm Euklidesa służy do wydzielania największego wspólnego dzielnika dwóch liczb naturalnych. Algorytm ten opiera się na prostym założeniu, że jeśli dana liczba dzieli bez reszty dwie liczby, to jest również dzielnikiem ich różnicy. Z tego wynika, że $NWD$ dwóch liczb $a$ i $b$ można obliczyć poprzez wyznaczenie reszty z dzielenia większej liczby przez mniejszą, a następnie kontynuowanie tego procesu z mniejszą z dwóch liczb i uzyskaną resztą, aż do momentu, gdy reszta wyniesie zero. Wówczas $NWD$ to wartość ostatniej różnej od zera reszty.