Vai al contenuto
OneKitly

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

Daniel Okonkwo — Sviluppatore front-end e redattore Tech presso OneKitly

Performance web · Formati di file

Verificato su 2 fonti

Vedi il profilo →
In breve

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.

Pubblicità

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.

I passi di divisione per 252 e 105
PassoResto
252 = 2 × 105 + 4242
105 = 2 × 42 + 2121
42 = 2 × 21 + 00 — fine
Calcolatore dell'algoritmo di Euclide estesoEsegui l'algoritmo di Euclide esteso su due interi a e b: restituisce il loro massimo comune divisore insieme ai coefficienti di Bézout x e y che soddisfano a·x + b·y = mcd(a, b). Oltre al mcd, quei coefficienti sono esattamente ciò che serve per costruire inversi modulari e risolvere equazioni diofantee lineari. È mostrata la tabella completa delle divisioni per seguire ogni riduzione.Prova lo strumento →
Pubblicità

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?