Algoritmo di Euclide per il calcolo del Massimo Comune Divisore (MCD)
Con “Algoritmo di Euclide” si indica una successione di calcoli algebrici finalizzati a trovare il Massimo Comune Divisore (MCD) di due numeri che indichiamo, in questa sede, con la lettera “a” e la lettera “b”. Il metodo scavalca quello, più comune, del calcolo del MCD mediate la scomposizione in fattori primi e, pertanto, risulta più veloce in caso di numeri particolarmente grandi.
Si indichi il Massimo Comune Divisore di due numeri, “a” e “b”, con la seguente funzione:
MCD (a, b)(1) con a > b;
Si indichi con il simbolo “%” l’operazione che restituisce il resto della divisione tra due numeri che viene indicata con il termine “modulo”; indicando con “r” il resto della divisione tra “a” e “b” potremo scrivere:
a % b = r;
in alternativa potremo anche scrivere:
a mod b = r;
Si può dimostrare, e verrà fatto in altra sede, che:
MCD (a, b) = MCD (b, r)(2)
Iniziamo ad analizzare il caso in cui “b” sia divisore di “a”, dunque:
a % b = 0;
In tal caso è evidente che “b” è il MCD di “a” e “b”:
MCD (a, b) = b;
In sintesi possiamo scrivere:
a % b = 0 → MCD (a, b) = b;
dove la freccina indica una “implicazione”. Potremmo così leggere: a % b = 0 implica che il MCD(a, b) è b.
Se, diversamente, a % b ≠ 0, quindi a % b = r, è valida la (2).
Anche in questo secondo caso potremmo avere:
b % r = 0 → MCD(b , r) = MCD (a, b) = r
Diversamente se b % r ≠ 0 allora b % r = r1, sempre per la due
MCD (b, r) = MCD (r, r1);
Dunque, se:
r % r1 = 0 → MCD (r, r1) = MCD (b, r) = MCD (a, b) = r1;
... e così via.
È possibile schematizzare i passaggi in una tabella:
| MCD(a, b) | a % b = 0 | MCD(a, b) = b | Trovato! |
| a % b > 0 | a % b = r | MCD(a, b) = MCD(b, r) | |
| MCD(b, r) | b % r = 0 | MCD(b, r) = r | Trovato! |
| b % r > 0 | r1 = a % r | MCD(b, r) = MCD(r, r1) | |
| MCD(r, r1) | r % r1 = 0 | MCD(r, r1) = r1 | Trovato! |
| r % r1 > 0 | r2 = r % r1 | MCD(r, r1) = MCD( r1 , r2) |
Il MCD viene trovato quando il rapporto modulo (%) restituisce come risultato 0.
Si noti che nella seconda colonna, dove sono riportati i possibili valori del modulo, avviene uno scambio,
a scalare, dei valori degli operandi:
a b
b r
r r1
Dal primo tentativo in poi, nel caso in cui non si verifichi la condizione di uguaglianza a 0 che terminerebbe la ricerca, il valore del secondo operando diviene il valore del primo e il valore del secondo viene sostituito con il valore del modulo del rapporto precedente. Questo scambio è il punto cruciale dell’algoritmo:
(a % b ≠ 0) {
r = a % b;
a = b;
b = r;
}
MCD(a, b) = b;
Create due variabili a e b con i rispettivi valori, quello di a maggiore di quello di b, viene dato il via ad una interazione che modifica i valori di a e b: la variabile a scabia il suo valore con quello di b e b con quello del modulo a, b. Quando i valori delle variabili a e b soddisfano la condizione a % b = 0 viene trovao il MCD(a,b) pari a b e l'interazione termina.