L'algoritmo originale di Euclide, era basato inizialmente su sottrazioni successive.

L'algoritmo per il calcolo del MCD di due interi positivi, nella sua versione più semplice, si basa sulla seguente proprietà:

Se due numeri, m, n, sono divisibili per un terzo numero, x, allora anche la loro differenza è divisibile per x.

Per dimostrarla, si può utilizzare la proprietà distributiva. Supponiamo m>n , m=kx, n=hx, m-n=kx-hx=x(k-h). Dunque si può dire che:

MCD(m,n) = MCD((m-n),n)

Come si vede, questa regola permette di passare, per mezzo di sottrazioni successive, a MCD di numeri sempre più piccoli, fino ad ottenere:

MCD(a,0)=a

L'algoritmo può essere scritto, in un qualsiasi linguaggio strutturato, così:

Finché m>0, se n>m, allora scambia m con n. Sottrai n da m, e assegna ad m il valore della differenza (m=m-n). Ripeti il ciclo, ed n è il MCD cercato.