Il massimo comune divisore senza tentativi casuali

L'idea centrale

Se due lunghezze devono essere divise in pezzi uguali senza scarti, serve un divisore comune. Cercare tutti i divisori funziona con numeri piccoli, ma con numeri grandi è inefficiente. L'algoritmo di Euclide sostituisce la coppia (a,b) con (b,r), dove r è il resto di a diviso b: i divisori comuni restano gli stessi. Quando il resto diventa zero, l'ultimo divisore non nullo è il MCD.

Perché i resti conservano i divisori comuni

Il massimo comune divisore risponde a una domanda concreta: qual è la misura intera più grande che divide due quantità senza lasciare resto? Se due nastri sono lunghi 72 e 30 centimetri, la lunghezza di ogni pezzo deve dividere entrambe le lunghezze. Il MCD è 6: non basta trovare un divisore comune, perché 2 e 3 funzionano anch'essi ma producono pezzi più corti. Un problema può chiedere anche il numero di pezzi: dopo aver trovato la lunghezza, si calcolano 72/6 e 30/6 e si sommano 12+5=17.

Se a=qb+r, ogni numero che divide a e b divide anche r=a−qb. Viceversa, ogni numero che divide b e r divide anche a=qb+r. Dunque le coppie (a,b) e (b,r) hanno esattamente gli stessi divisori comuni. Questa è la ragione della procedura, non un trucco da memorizzare. Poiché 0≤r<b, il secondo numero positivo diminuisce a ogni passo e il calcolo termina. Quando r=0, il secondo numero divide il primo: è l'ultimo divisore non nullo e quindi il MCD.

Altri casi e trasferimenti

L'algoritmo non serve solo a due numeri già piccoli. Per MCD(119,34), scrivi 119=3·34+17 e 34=2·17+0: il MCD è 17. Puoi confrontarlo con la scomposizione in fattori, 119=7·17 e 34=2·17, ma non sei obbligato a fattorizzare numeri grandi. Il resto è sempre minore del divisore: se scrivessi 119=2·34+51, l'uguaglianza sarebbe vera ma 51 non è un resto valido della divisione per 34, perché si può sottrarre ancora 34. Questo controllo impedisce di fermare la procedura troppo presto. Con tre lunghezze, puoi applicare il metodo due volte: MCD(a,b,c)=MCD(MCD(a,b),c).

Il MCD compare quando si vogliono gruppi identici senza avanzo. Con 42 penne blu e 30 rosse, se ogni sacchetto deve contenere lo stesso numero di penne blu e lo stesso numero di rosse, il numero massimo di sacchetti è MCD(42,30)=6. Ogni sacchetto contiene 42/6=7 blu e 30/6=5 rosse. Qui il MCD non è la quantità in ogni sacchetto, ma il numero di sacchetti: la domanda concreta decide come interpretarlo. Se invece chiedi la lunghezza massima di pezzi uguali ricavati da due corde, il MCD è una lunghezza. Copiare l'unità del risultato da un esempio all'altro è un errore anche quando il calcolo numerico è corretto.

Il minimo comune multiplo risolve problemi di ricorrenza diversi. Due segnali lampeggiano ogni 6 e 8 secondi; se partono insieme, si ritrovano insieme dopo mcm(6,8)=24 secondi. Il MCD è 2 e non è la risposta. Per due interi positivi a e b, MCD(a,b)·mcm(a,b)=a·b: con 6 e 8, 2·24=48. La relazione permette un controllo, ma prima si deve decidere quale grandezza è cercata. L'algoritmo euclideo si può usare per trovare il MCD e quindi ricavare il mcm come a·b/MCD; così un solo metodo sostiene entrambi i problemi senza confonderne il significato.

Per capire perché l'algoritmo può essere efficiente, osserva il caso 987 e 610: 987=1·610+377, 610=1·377+233, 377=1·233+144, e i resti continuano a calare fino a 1. Non occorre provare tutti i possibili divisori fino a 610. Ogni nuova coppia conserva esattamente gli stessi divisori comuni della precedente; per questo, anche una catena lunga rimane una prova controllabile. Se un resto calcolato è negativo o non è minore del divisore, ricontrolla subito la divisione: il procedimento non è valido da quel punto in poi. Nella risposta finale, 'coprimi' significa MCD uguale a 1; non significa che entrambi i numeri siano primi. Per esempio 8 e 9 sono composti, ma non hanno divisori comuni maggiori di 1.