L’algoritmo di Euclide è un metodo per calcolare il Massimo Comune Divisore tra due numeri, secondo cui se loro sono divisibili per uno stesso numero questo vale anche per la loro differenza a patto che il primo sia maggiore del secondo.
Questo metodo si basa quindi sul teorema della divisibilità della differenza. Se due numeri a e b, con a > b sono divisibili per uno stesso numero c, anche a – b sarà divisibile per c.
Per dimostrare questo teorema basta scomporre le due variabili
a : c = q1; di conseguenza a = q1 ∙ c
b : c = q2; di conseguenza b = q2 ∙ c
Questo perché la divisione è l’inverso della moltiplicazione. Adesso scomponiamo a – b e raccogliamo il fattore c a motivo della proprietà distributiva della moltiplicazione.
a – b = q1 ∙ c – q2 ∙ c = (q1 – q2 ) ∙ c
a – b = (q1 – q2 ) ∙ c; a – b è divisibile per c
A questo punto possiamo dire che se a e b hanno lo stesso divisore comune anche a – b avrà lo stesso divisore, quindi possiamo scrivere:
MCD (a; b) = MCD (a – b; b)
Nell’algoritmo teniamo anche conto del fatto che il MCD tra un numero e se stesso è quello stesso numero
MCD (a; a) = a
Come funziona l’algoritmo di Euclide
Prendiamo in considerazione due numeri a e b con a > b. Se a – b = b, allora è come se avessimo b = b e il Massimo Comune Divisore è lo stesso b.
Se invece abbiamo, come esempio, a – b = c il numero più grande tra b e c prenderà il posto di a mentre il minore il posto di b e continuiamo con il procedimento facendo una nuova differenza.
Se b > c: b – c = d
Se b < c: c – b = d
Continuiamo in questo modo fino a quando il valore della differenza non sarà uguale a quello del sottraendo. Vediamo adesso un esempio cercando il M.C.D tra 62 e 14.
62 – 14 = 48; 48 prende il posto di 62.
48 – 14 = 34; 34 prende il posto di 48.
34 – 14 = 20; 20 prende il posto di 34.
20 – 14 = 6; 14 > 6: 14 prende il posto di 20 e 6 passa al sottraendo.
14 – 6 = 8; 8 prende il posto di 14.
8 – 6 = 2; 6 > 2: 6 prende il posto di 8 e 2 passa al sottraendo.
6 – 2 = 4; 4 prende il posto di 6.
4 – 2 = 2; 2 è il Massimo Comune Divisore.
Dimostriamo che è così trovando il M.C.D. con scomponendo i due numeri: 62 = 2 ∙ 31 mentre 14 = 2 ∙ 7. Quindi l’algoritmo di Euclide ci permette di trovare il Massimo Comune Divisore tramite sottrazioni successive.
Possiamo ridurre il numero di calcoli da fare applicando il teorema della divisibilità del resto, secondo cui se due numeri a e b, con a > b, sono divisibili per uno stesso numero c, anche il resto della divisione a : b è divisibile per c.
Nell’algoritmo di Euclide significa che se a : b = b con resto 0 abbiamo trovato il MCD. proprio come nella differenza. Se la divisione riporta il resto, il valore di b prenderà il posto di a e r prenderà il posto di b. Dimostriamolo usando i numeri 62 e 14.
62 : 14 = 4 con resto 6; 14 passa al dividendo mentre il resto al divisore.
14 : 6 = 2 con resto 2; 6 passa al dividendo mentre 2 al divisore.
6 : 2 = 3 con resto 0; Dato che il resto è 0 il divisore 2 è anche il MCD ottenibile.
MCD (a; b) = b, se r = 0.
