L'algoritmo di Euclide dà il MCD e la ricetta per costruirlo
Pubblicato il 27/10/2026 · 3 min di lettura · Calcolatrici quotidiane
Daniel Okonkwo — Sviluppatore front-end e redattore Tech presso OneKitly
Performance web · Formati di file
Verificato su 2 fonti
L'algoritmo ordinario sostituisce ripetutamente il numero maggiore con il suo resto contro il minore: 252 lascia 42 contro 105, 105 lascia 21 contro 42, e 42 non lascia nulla contro 21, quindi 21 è il massimo comune divisore. La versione estesa tiene traccia di come ogni resto è stato costruito lungo la strada e restituisce due interi che combinano i numeri originali in quel divisore — qui −2 e 5, poiché 252 × (−2) + 105 × 5 = −504 + 525 = 21. Quella combinazione esiste sempre, fatto chiamato identità di Bézout, ed è essa a produrre un inverso modulare: quando il divisore è uno, il coefficiente del primo numero è esattamente l'inverso di quel numero modulo il secondo.
252 e 105 hanno un massimo comune divisore di 21, e la versione estesa restituisce anche −2 e 5: 252 × (−2) + 105 × 5 = 21 esattamente.
Perché finisce così in fretta
Ogni passo sostituisce una coppia con una coppia più piccola, e la riduzione è rapida: dopo due passi il numero maggiore vale al più la metà di prima, perché un resto è sempre minore del divisore e uno dei due deve scendere sotto la metà. Il numero di passi è quindi proporzionale al numero di cifre e non ai numeri stessi, da cui la facilità con cui il metodo tratta valori di centinaia di cifre. Il caso peggiore risulta essere quello dei numeri di Fibonacci consecutivi, dettaglio gradevole e ragione per cui il limite si enuncia di norma in logaritmo.
I coefficienti non sono unici
Per 240 e 46 l'algoritmo restituisce −9 e 47, dando 240 × (−9) + 46 × 47 = 2, ed è una risposta fra infinite: aggiungere ventitré al primo coefficiente e sottrarre centoventi al secondo dà un'altra coppia valida, e così via senza fine. L'algoritmo restituisce la coppia di ampiezze minori, rappresentante utile, e ogni implementazione che confronti due risultati deve normalizzare prima di concludere che differiscono. È un rischio generale dei problemi le cui risposte formano una famiglia e non un punto.
| Passo | Resto |
|---|---|
| 252 = 2 × 105 + 42 | 42 |
| 105 = 2 × 42 + 21 | 21 |
| 42 = 2 × 21 + 0 | 0 — fine |
Domande frequenti
- Quanti anni ha questo metodo?
- Compare negli Elementi di Euclide, scritti circa trecento anni prima della nostra era, il che ne fa l'algoritmo più antico ancora in uso corrente. Nulla vi è stato migliorato nel senso che conta: esistono varianti che evitano la divisione o si adattano meglio all'hardware binario, ma il numero di passi e l'idea di fondo sono immutati. Che una procedura scritta per la geometria su papiro si trovi dentro ogni apparecchio che fa crittografia a chiave pubblica è una delle continuità più notevoli del settore.
- A cosa servono i coefficienti oltre agli inversi?
- A risolvere equazioni in numeri interi, che è l'uso per cui furono voluti per primi. Un'equazione che chiede quantità intere di due grandezze che devono totalizzare una terza ha soluzione esattamente quando il massimo comune divisore delle due divide la terza, e i coefficienti ne danno una direttamente; le altre seguono aggiungendo multipli di un passo fisso. Ciò copre comporre un importo con due tagli di moneta, far coincidere due cicli ripetitivi, e ogni domanda analoga in cui risposte frazionarie non siano ammesse. È anche il macchinario dietro la ricostruzione di un valore da più resti insieme.
Articoli che potrebbero interessarti
Tutte le guide →Strumenti correlati
Fonti
Hai notato un errore in questo articolo?