Massimo comune divisore: cos'è e come si calcola con l'algoritmo di Euclide

Il divisore comune e il più grande di tutti

Un numero intero diverso da zero divide un altro numero quando lo contiene un numero esatto di volte, senza lasciare resto. Quando due numeri condividono uno di questi divisori, si parla di divisore comune. Il massimo comune divisore — il MCD — è il più grande fra questi divisori comuni: l’unico numero naturale che divide entrambi i numeri di partenza ed è, al tempo stesso, il più grande a farlo.

Preso da solo il concetto resta astratto. Messo alla prova con due numeri si capisce meglio: 234 e 42 condividono i divisori 1, 2, 3 e 6, e il più grande fra questi, 6, è il loro massimo comune divisore. Il MCD vive nell’insieme dei numeri naturali, lo stesso dominio descritto negli insiemi numerici: non ha senso cercarlo tra numeri con la virgola.

Trovarlo elencando i divisori funziona con numeri piccoli, ma diventa lento quando i numeri crescono. Per questo esiste un metodo più rapido, descritto per la prima volta più di duemila anni fa, uno dei capitoli più antichi dell’aritmetica.

L’algoritmo di Euclide, passo per passo

L’algoritmo di Euclide trova il MCD senza bisogno di elencare nulla: procede per divisioni con resto, ripetute sulla coppia di numeri che la divisione precedente produce. Applicato a 234 e 42 funziona così:

L’ultimo resto diverso da zero è 6: è il massimo comune divisore di 234 e 42, lo stesso numero trovato poco sopra elencando i divisori a mano.

Esempio pratico: per il MCD di 48 e 18 si ripete lo stesso schema. 48 = 18×2+12, poi 18 = 12×1+6, poi 12 = 6×2+0. Il resto prima dello zero è 6, quindi il MCD di 48 e 18 è 6.

Perché il procedimento funziona

Il principio che regge l’intero algoritmo è questo: il massimo comune divisore di due numeri resta identico a quello formato dal secondo numero e dal resto della divisione tra i due. Il MCD di 234 e 42 è uguale al MCD di 42 e 24, perché 234 si scrive come 42×5+24: un numero che divide sia 234 sia 42 divide anche 24, e un numero che divide 42 e 24 divide anche 234, quindi i due divisori comuni coincidono sempre.

Ripetendo il passaggio, la coppia di numeri si restringe a ogni giro, e il resto diminuisce. Una sequenza di numeri naturali che calano non può proseguire all’infinito: arriva per forza a zero in un numero finito di passaggi. Quando arriva, l’ultimo resto diverso da zero è il massimo comune divisore cercato.

Più antico della scuola che lo insegna

Euclide descrive questo procedimento nel Libro VII degli Elementi, scritti verso il 300 a.C. Il libro apre con la definizione di unità come base del concetto di numero, e definisce il numero stesso come una quantità composta da unità: un numero più piccolo “misura” uno più grande quando è contenuto in esso un numero intero di volte, che è un altro modo di dire che lo divide esattamente.

Nella Proposizione 1 del Libro VII, Euclide descrive un test per stabilire se due numeri sono primi fra loro: si sottrae ripetutamente il più piccolo dal più grande, fino a restare con un’unità. Nella Proposizione 2 affronta il problema che oggi chiamiamo trovare il massimo comune divisore, con lo stesso tipo di sottrazioni ripetute, fino a un resto che divide esattamente quello precedente — quel resto è il MCD cercato. Il metodo che si insegna oggi, con le divisioni, è una forma più rapida dello stesso principio che Euclide descrisse per sottrazioni successive: una divisione, in fondo, non è che una sottrazione ripetuta più volte in un solo passaggio.

Dove si usa, oltre i compiti di matematica

Secondo la voce «Euclidean algorithm» di Wikipedia, il massimo comune divisore di due numeri si può sempre scrivere come combinazione dei due numeri di partenza, moltiplicati ciascuno per un intero opportuno, anche negativo: è l’identità di Bézout, e i due coefficienti si ricavano ripercorrendo all’indietro i passaggi dell’algoritmo appena descritto, in un procedimento distinto da quello visto qui sopra. Sempre secondo Wikipedia, una variante dello stesso algoritmo calcola l’inverso modulare, un passaggio della crittografia RSA che protegge le transazioni online. L’algoritmo risulta anche efficiente: Gabriel Lamé ha dimostrato nel 1844 che non servono mai più di cinque passaggi per ogni cifra del numero più piccolo della coppia.

Chi studia algebra e geometria euclidea incontra lo stesso nome, Euclide, da due porte diverse: la geometria degli Elementi e questo procedimento aritmetico, nati nello stesso trattato.