abbiamo due numeri interi con $b$ diverso da $0$ e noi vogliamo trovare il massimo comun divisore tra i due numeri:
ora cerchiamo di trovare il MCD senza fattorizzare in numeri primi.
Esiste un unico $q \in \Z$ tale che $r=a-q\times b \in \{0,1,…,|b|-1 \}$, $r$ rappresenta il resto e $q$ il quoziente
per calcolarlo dobbiamo fare:
e si va avanti così, possiamo scrivere il tutto anche così:
è evidente che in un numero finito di passi arriveremo a 0 e il valore assoluto di b è il numero massimo di passi.
arriviamo al fatto che il resto faccia 0. Sia $k$ tale che $r_k \neq 0$ e $r_{k+1} = 0$. Adesso posso affermare che $|r_k| = MCD(a,b)$
Dimostriamo:
alla fine troviamo che:
ora dimostriamo che troviamo un MCD:
