Ciao a tutti! In questo post parleremo del calcolo del massimo comun divisore, o MCD, tra due numeri naturali.
Innanzitutto, che cosa significano queste parole che così spesso sentiamo a lezioni di matematica?
- Divisore: Diciamo che un numero a divide un numero b diverso da 0 se possiamo effettuare la divisione esatta, ovvero se esiste un altro numero c tale che a=bc. Per esempio, 3 è un divisore di 12 perché 3x4=12, oppure 11 divide 66 perché 11x6=66, ma 5 non è un divisore di 13 perché la divisione tra 13 e 5 dà come resto 3.
- Dati due numeri naturali, possiamo elencare tutti i divisori di ciascuno di essi. Per esempio, i divisori di 12 sono 1, 2, 3, 4, 6, 12, mentre i divisori di 28 sono 1, 2, 4, 7, 14, 28. Tra questi, i divisori comuni sono i divisori che compaiono in entrambi gli elenchi, quindi sono i numeri che dividono sia il primo che il secondo numero; nel nostro esempio, 1, 2, 4 sono i divisori comuni di 12 e 28.
- Tra tutti i divisori comuni, il più grande sarà il massimo comun divisore. Nel nostro esempio, 4 è il massimo comun divisore tra 12 e 28. Scriveremo:
MCD(12,28)=4.
Ora che abbiamo capito la definizione, vediamo come calcolare il massimo comun divisore. Un primo, semplice algoritmo è quello descritto sopra. Tuttavia, elencare tutti i divisori tra due numeri, specie se molto grandi, è inutilmente noioso e richiede molto tempo. Vediamo quindi un algoritmo più utile.
Calcolo del MCD
Passo 1: Calcolare la scomposizione in fattori primi dei due numeri dati.
Per calcolare la scomposizione in fattori primi, è utile conoscere bene i criteri di divisibilità: essi ci permetteranno, infatti, di riconoscere velocemente quali sono i numeri primi che compariranno nella fattorizzazione.
Procediamo in questo modo:
- Se il numero da scomporre è 1, la scomposizione è terminata.
- Se il numero da scomporre è maggiore di 1, cerchiamo il numero primo più piccolo per il quale è divisibile: proviamo quindi a controllare la divisibilità per 2, poi 3, poi 5 e così via.
- Una volta trovato il numero primo del passo precedente, calcoliamo il risultato della divisione e ripetiamo la procedura su questo nuovo numero.
Per esempio, se dobbiamo scomporre il numero 180, ragioniamo come segue:
- 180 è divisibile per 2
- 180:2=90
- 90 è divisibile per 2
- 90:2=45
- 45 è divisibile per 3
- 45:3=15
- 15 è divisibile per 3
- 15:3=5
- 5 è divisibile per 5
- 5:5=1
- Fine.
Come ricaviamo la scomposizione in fattori primi, a questo punto? Ci basta scrivere, utilizzando le proprietà delle potenze, il prodotto tra tutti i numeri primi così trovati. Nel nostro esempio:
180=2x2x3x3x5=2^2x3^3x5.
Passo 2: Calcolare il MCD utilizzando la scomposizione trovata.
Abbiamo trovato la scomposizione in fattori primi dei due numeri di cui vogliamo calcolare il MCD. Come facciamo adesso a calcolare il MCD? Possiamo trovarne la scomposizione in fattori primi con questa semplice regola:
Prendiamo tutti i numeri primi che compaiono in entrambe le scomposizioni e li eleviamo all'esponente più piccolo.
Per esempio, se vogliamo calcolare MCD(180, 75), osserviamo che:
180=2^2x3^2x5
75=3x5^2 (provate a farlo per esercizio!)
...e i fattori comuni sono 3 e 5. Di questi, l'esponente più piccolo per il 3 è 1, ma anche l'esponente più piccolo per il 5 è 1, quindi...
MCD(180,75)=3^1x5^1=3x5=15.
