Massimo comun divisore: come calcolarlo? Spiegazione con esempi

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?

Trova un tutor 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.

Articolo correlato Strategie utili per andare bene in matematica

Le lezioni di matematica sono il nemico numero uno di molti studenti. Magari ci fosse una formula magica per poter avere sempre la sufficienza e soprattutto per riuscire a capire sempre tutto, ma...

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.

Ripetizioni di matematica nella tua città e online

Veronica 1ª lezione gratis (1)10100

Chiara 1ª lezione gratis (1)10100

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.