algoritmo di Euclide

Teorema

Per ogni coppia di elementi $a,b\in \mathbb{Z}$ esiste il loro massimo comun divisore.

Dimostrazione

Dati $a,b\in \mathbb{Z}$, dal Teorema 2.1.7 possiamo scrivere $a=q_{0}b+r_0$ mentre dall’Osservazione 2.1.8 abbiamo che $MCD(a,b)=MCD(a-b,b)=MCD(a-2b,b)=\cdots =MCD(a-q_{0}b,b)$. Dunque $MCD(a,b)=MCD(r_0,b)$ dove $r_0$ è il resto della divisione euclidea e si ha $0\le r_0<|b|$.

Possiamo ora ripetere il procedimento in questo modo: avremo $b=q_1{r}_0+r_1$ e $MCD(r_0,b)=MCD(r_0,b-r_0)=MCD(r_0,b-2r_0)=\cdots =MCD(r_0,b-q_1{r}_0)=MCD(r_0,r_1)$ con $0\le r_1<r_0$. In generale troveremo che $MCD(a,b)=MCD(r_i,r_{i+1})$. Trovandoci in $\mathbb{Z}$ e osservando che la successione $\{r_i{\}}_i$ è strettamente decrescente e limitata inferiormente da $0$ avremo che dopo un numero finito di passaggi si otterrà $MCD(a,b)=MCD(r_j,0)=r_j$.

Quella appena vista è una dimostrazione costruttiva, a titolo di esempio si mostra una applicazione di questo algoritmo per la ricerca di $MCD(54,16)$:

1. $54=3\cdot 16+6\to MCD(54,16)=MCD(6,16)$
2. $16=2\cdot 6+4\to MCD(6,16)=MCD(6,4)$
3. $6=1\cdot 4+2\to MCD(6,4)=MCD(4,2)$
4. $4=2\cdot 2+0\to MCD(4,2)=MCD(2,0)=2=MCD(54,16)$

Risorse