L'algoritmo euclideo

Nella prop. 2 del Libro VII degli Elementi, Euclide espone una procedura sistematica, o algoritmo, per trovare il massimo 

comune divisore di due numeri assegnati. 

Siano a e b due numeri naturali assegnati, e supponiamo che a > b. Vogliamo di esaminare i divisori comuni ad a e b. 

Se a è divisibile per b, allora questo insieme consiste semplicemente in tutti i divisori di b, e ciò esaurisce la questione. 

Se a non è divisibile per b, possiamo esprimere a come un multiplo di b a cui si somma un resto minore di b, ossia

                                                                        a = qb + r,    dove  r < b               (2)
 

Questo è il procedimento di "divisione con resto", ed esprime il fatto che a, qualora non divisibile per b, deve trovarsi

compreso tra due opportuni multipli di questo. Se a capita tra qb e (q+1)b, allora

                                                                        a = qb + r,    dove 0 < r < b

E' una conseguenza dell'equazione (2) che ogni divisione comune a b e r sia anche divisore di a. Non solo, ogni divisore

di a e b divide anche r, poichè  r = a-qb. Pertanto i divisori comuni ad a e b, qualunque essi possano essere, coincidono

coi divisori comuni di  b e r. Il problema di trovare i divisori comuni ad a e b è così stato trasformato nel medesimo problema

per i numeri b ed r, che sono rispettivamente minori di a e b.

L'essenza dell'algoritmo giace nell'iterazione di questa procedura. Se b è divisibile per r, i loro divisori comuni sono tutti i

divisori di r. Altrimenti esprimiamo b nella forma

                                                                        b = q₁ r + r₁ ,     dove r₁ <r

Nuovamente, i divisori comuni a b e r coincidono con quelli comuni a r e r₁. Il procedimento continua sino a terminare, e ciò

può accadere solo quando si abbia divisibilità esatta, ossia quando si pervenga ad un numero nella sequenza a, b, r, r₁, ..., che

sia un divisore del numero precedente. E' chiaro che ciò accadrà prima o poi poichè la sequenza decrescente a, b, r, r₁, ...,  di

numeri naturali non può continuare indefinitivamente.  L'ultimo resto  r_j  non nullo sarà il massimo comune divisore, e lo

indicheremo così:

                                                                        r₁ = MCD(a,b)

Se a e b sono due numeri naturali assegnati tali che MCD(a,b)=1 allora diremo che a e b sono primi tra loro (ovvero coprimi).

Come illustrazione numerica consideriamo i numeri 3132 e 7200, e calcoliamo MCD(3132,7200). L'algoritmo procede come

segue:

                                                                      7200 = 2 x 3132 + 936
                                                                      3132 = 3 x 936 + 324
                                                                        936 = 2 x 324 + 288
                                                                        324 = 1 x 288 + 36
                                                                        288 = 8 x 36
da cui segue:

                                                                      MCD(3132,7200) = 36