Algorytm Euklidesa służy do obliczania NWD dwóch liczb naturalnych. W wersji przez odejmowanie (jak w podręczniku) dla pary m,nm,n powtarzamy:
jeśli m=nm=n, to NWD(m,n)=m\operatorname{NWD}(m,n)=m;
jeśli m<nm<n, zastępujemy nn przez n−mn-m;
jeśli m>nm>n, zastępujemy mm przez m−nm-n.
Wspólny dzielnik liczb mm i nn jest też dzielnikiem ich różnicy, więc
NWD(m,n)=NWD(m,n−m)dla n>m 
