Per un intero x definiamo D(x) come l'insieme dei divisori di x.
Ovvero D(x) = {z appartenente a N+ tale che esiste q di N. x = zq}

Euclide dimostra 2 teoremi:

1. se x = qy + r allora D(x) intersezione D(y) = D(y) intersezione D(r)
   dim.: bisogna dimostrare che

   z appartiene a D(x) intersezione D(y) se e solo se z appartiene a D(y) intersezione D(r)

   Se z appartiene a D(x) intersezione D(y)
   allora esistono q1 e q2 tali che x = z q1 e y = z q2
   per ipotesi x = qy + r e quindi z q' = q (z q2) + r
   da cui r = z (q2 - q q1)
   quindi r è divisibile per z
   cioè z appartiene a D(y) intersezione D(r)
   c.d.d. (analogamente il viceversa)
   corollario: MCD(x,y) = MCD(y,r)

   infatti, poichè D(x) intersezione D(y) = D(y) intersezione D(r)
   abbiamo che max(D(x) intersezione D(y)) = max(D(y) intersezione D(r)) c.d.d.

2. se x = q y allora MCD(x,y) = y
   dim: y = max(D(y))

Algoritmo risultante:

Esempio:

dati x = 132 e y = 24, si ha 132 = 5*24+12 e 24 = 2*12 + 0