Calcolo dell’MCD: dividere ancora e ancora -----------------------------------------
Il teorema della divisione euclidea fornisce un algoritmo — precisamente l’algoritmo di Euclide — per calcolare il massimo comun divisore, o MCD, di due numeri. Nei casi più semplici, il valore dell’MCD salta agli occhi! Così, l’MCD di 21 e 15 è 3. Ma che dire dell’MCD di 1 597 e 987? L’algoritmo di Euclide permette di calcolare l’MCD di due numeri naturali non nulli a e b mediante divisioni successive: si divide a per b; poi b per il resto ottenuto; poi il primo resto per il secondo; il secondo per il terzo… e l’ultimo resto non nullo è l’MCD. Così, l’MCD di 1597 e 987 è 1; questi due interi sono primi tra loro.
Il teorema di Lamé: poche divisioni da effettuare in pratica --------------------------------------------------------------
Non appena si dispone di un algoritmo, ci si interessa alla sua efficienza. Come «misurarla»? Qual è il «tempo di calcolo»? È questo l’oggetto di una nota, cara agli informatici di oggi, pubblicata nel 1844 da Gabriel Lamé (1795-1870). Vediamo che cosa scrive, nei Comptes rendus hebdomadaires de l’Académie des sciences, questo accademico appena nominato: «Nei trattati di aritmetica ci si limita a dire che il numero delle divisioni da effettuare, nella ricerca del massimo comun divisore tra due interi, non potrà superare la metà del più piccolo. Questo limite, che può essere superato se i numeri sono piccoli, si allontana eccessivamente quando hanno più cifre.» Stabilisce poi: «Il numero di divisioni da effettuare per trovare il massimo comun divisore tra due interi A e B < A è sempre inferiore a cinque volte il numero di cifre di B [il divisore].»
Conclude con un esempio che mostra la forza del suo teorema: «Si prendano, per esempio, i due numeri 1597 e 987. La ricerca del loro massimo comun divisore richiederà quattordici divisioni. Il limite assegnato dal presente teorema è quindici. Il limite adottato nei trattati di aritmetica sarebbe quattrocentonovantatré.»