Algorytm Euklidesa jest szybkim sposobem obliczania największego wspólnego dzielnika dwóch (zwłaszcza dużych) liczb całkowitych.

 

AlgorytmAby obliczyć NWD(a,b), wykonujemy kolejno następujące kroki: Dzielimy z resztą liczbę a przez liczbę b jeżeli reszta =0, to NWD(a,b)=b jeżeli reszta ?0, to przypisujemy liczbie a wartość liczby b, liczbie b wartość otrzymanej reszty, a następnie wykonujemy ponownie punkt 1.