eine geometrisch motivierte Methode zur Konstruktion des ggT zweier ganzer Zahlen a >b > 0.

Man setzt r₀ = a und r₁ = b und definiert r₂ als Rest bei Division von r₀ durch r₁ (Division mit Rest): \begin{eqnarray}{r}_{0}=c{r}_{1}+{r}_{2}\end{eqnarray} mit ganzen Zahlen c, r₂ und 0 ≤ r₂ ≤ r₁.

Solange r_k ≠ 0 berechnet man induktiv r_k+1 als Rest bei Division von r_k−1 durch r_k. Wegen 0 ≤ r_k+1< r_k ist irgendwann r_k+1 = 0; dann stoppt man das Verfahren, und es gilt r_k = ggT(a, b).

Die notwendigen algebraischen Voraussetzungen an den Rechenbereich, damit der euklidische Algorithmus durchführbar ist und nach endlich vielen Schritten zu einem Ergebnis kommt, sind im Begriff des euklidischen Rings kondensiert.

Der euklidische Algorithmus ist seinem Ursprung nach eine geometrische Methode zur Konstruktion eines gemeinsamen Teilers zweier (evtl. durch geometrische Konstruktionen gegebenen) Streckenlängen a, b. Man nennt diesen Algorithmus auch einen Divisionsalgorithmus.