Calcolatrice dell'algoritmo di Euclide

a = q * b + r, quindi MCD(a, b) = MCD(b, r); ripeti finché r = 0, e allora la risposta è b

a = q * b + r

Un giro dell'algoritmo, scritto come equazione. a è il più grande dei due numeri di quel giro, b il più piccolo, q quante volte intere b entra in a e r quello che avanza. Questa è esattamente la notazione dei passaggi che vedi sulla pagina: 1071 = 2 * 462 + 147 è un giro

a, b

I due numeri messi a confronto. Cambiano identità a ogni giro: il b di un giro diventa l'a del giro successivo e l'r diventa il nuovo b. È questo rimescolamento il motivo per cui i campi di ingresso non si chiamano dividendo e divisore: nel primo giro 1071 è il dividendo, nel secondo lo è 462, e un'etichetta giusta per un giro è sbagliata per tutti gli altri

q

Il quoziente, quante volte intere b sta in a. È sempre almeno 1, perché la coppia viene messa in ordine decrescente prima che il ciclo cominci: è anche il motivo per cui qui non vedrai mai q = 0. L'unico giro in cui q non ha niente di particolare è l'ultimo, dove il resto è zero e il quoziente è esatto

r

Il resto, sempre minore di b e mai negativo. La regola di arresto dell'algoritmo è r = 0, stampata come ultimo giro invece che omessa: 147 = 7 * 21 + 0 è la riga che dice che la ricerca è finita e che la risposta è 21

MCD(a, b)

Il massimo comun divisore: il più grande numero intero che divide esattamente sia a sia b. La risposta è il b dell'ultimo giro, preso direttamente dal ciclo invece di essere ricalcolato. Per 1071 e 462 è 21, ed è per questo che 1071 = 21 × 51 e 462 = 21 × 22, e nessun numero più grande li divide entrambi

610 = 1 * 377 + 233

Il giro di apertura del caso peggiore: due numeri di Fibonacci consecutivi. Qui ogni quoziente vale 1 e i numeri si rimpiccioliscono appena, ed è questo che fa impiegare tredici giri alla coppia. Il teorema di Lamé dice che nessuna coppia di numeri di questa grandezza può impiegare di più

Ridurre una frazione è l'uso di ogni giorno. Per scrivere 462/1071 ai minimi termini ti serve il massimo comun divisore dei due, e questa pagina te lo consegna insieme alla prova: 21, e i tre giri che l'hanno prodotto. Dividendo numeratore e denominatore per 21 si ottiene 22/51, e i passaggi stampati sono ciò che ti permette di controllare la riduzione invece di fidarti. Lo stesso bisogno si presenta ogni volta che un rapporto va semplificato: rapporti di trasmissione, formati dello schermo, disegni in scala e due misure qualsiasi che vuoi esprimere come proporzione invece che come coppia di numeri. Il secondo uso è nel codice e a lezione, dove l'algoritmo si insegna come il primo davvero interessante: termina, è veloce ed è corretto per una ragione che si vede in una sola equazione. È anche il modo standard di calcolare un inverso modulare — la versione estesa porta con sé due numeri in più lungo gli stessi giri — che è il passo dentro la generazione delle chiavi RSA. Un terzo uso è il controllo di sanità sulla fattorizzazione. Scoprire che 1071 è 3 × 357 e che 462 è 2 × 3 × 7 × 11 è lavoro; scoprire che il loro massimo comun divisore è 21 costa tre divisioni, quindi passare prima da questa pagina ti dice se semplificare sarà facile prima ancora di iniziare. Quando ti serve solo la risposta e non il procedimento, la calcolatrice del MCD pone la stessa domanda in forma più breve e gestisce più di due numeri alla volta; la calcolatrice del mcm usa il divisore per ottenere il minimo comune multiplo, dato che mcm = (a / MCD) * b; la calcolatrice del resto copre che cosa significa un singolo resto quando i numeri possono essere negativi, cosa che questa pagina non deve mai affrontare.

1. La coppia da manuale: 1071 e 462

   1. Quante volte entra 462 in 1071? Due, e 2 × 462 = 924, quindi avanza 1071 − 924 = 147
   2. Adesso la coppia è 462 e 147: 147 entra in 462 tre volte, 3 × 147 = 441, e avanza 21
   3. Adesso la coppia è 147 e 21: 21 entra in 147 esattamente sette volte, e non avanza niente
   4. Il resto è zero, quindi l'algoritmo si ferma e la risposta è 21

   L'ingresso predefinito, e l'esempio svolto con cui questo algoritmo viene di solito presentato. Vale la pena fare due controlli sul risultato. Dividi entrambi i numeri per 21 e ottieni 51 e 22, che non hanno fattori in comune, ed è questo che rende 21 il massimo e non semplicemente un divisore comune. E nota che qui non c'è stata alcuna fattorizzazione: per trovare i fattori di 1071 per tentativi dovresti arrivare fino a 32, mentre l'algoritmo ha sempre e solo diviso un numero per uno che aveva già in mano. Tre giri, ognuno più economico del precedente.

2. Un giro basta: 12 e 60

   1. Metti la coppia in ordine decrescente: prima 60, poi 12
   2. 60 = 5 × 12 + 0, quindi 12 divide 60 esattamente
   3. Il resto è subito zero, quindi l'algoritmo si ferma dopo un solo giro
   4. La risposta è 12, il più piccolo dei due, perché divide il più grande

   La corsa non banale più breve possibile, e il caso che mostra perché l'ultimo giro viene stampato invece che saltato. La riga 60 = 5 * 12 + 0 è tutta la risposta: dice che il resto ha raggiunto lo zero, che è l'unico modo in cui questo algoritmo si ferma. Togli quella riga e i passaggi resterebbero vuoti, e il lettore non avrebbe modo di distinguere una risposta da un giro solo da una pagina che non ha girato affatto. Ogni volta che un numero divide l'altro esattamente, il massimo comun divisore è semplicemente il più piccolo dei due.

3. Numeri coprimi: 9 e 20

   1. 20 = 2 × 9 + 2, quindi la coppia diventa 9 e 2
   2. 9 = 4 × 2 + 1, quindi la coppia diventa 2 e 1
   3. 2 = 2 × 1 + 0, quindi l'algoritmo si ferma
   4. La risposta è 1, il che significa che 9 e 20 non hanno alcun divisore in comune oltre a 1

   Un massimo comun divisore di 1 è una risposta vera e non un fallimento, e ha un nome: i numeri sono coprimi. È anche il segno che la frazione 9/20 è già ai minimi termini, quindi non c'è nessuna semplificazione disponibile. Nota che i giri non si sono accorciati: l'algoritmo è sceso fino a 1 in tre passi, perché nessuno dei due numeri divideva l'altro esattamente. Le coppie coprime sono il caso comune man mano che i numeri crescono: la probabilità che due numeri presi a caso abbiano un divisore in comune cala in fretta, ed è esattamente questo che rende il metodo utile per costruire un inverso modulare in crittografia.

Entrambi i numeri devono essere interi, e devono stare fra 1 e 1.000.000. Lo zero viene rifiutato invece di essere trattato come un caso speciale. Il massimo comun divisore di a e 0 è a, che è una risposta del tutto legittima, ma questa pagina non può mostrarla: il primo giro sarebbe a = q * 0 + r, e quel q non esiste. Invece di stampare un procedimento con un buco dentro, la pagina rifiuta l'ingresso. I numeri negativi vengono rifiutati per la stessa ragione: i passaggi così come sono stampati danno per scontato che entrambi i numeri siano almeno 1, e un operando negativo avrebbe bisogno di una regola su che cosa significano quoziente e resto che questa pagina non enuncia da nessuna parte. Il tetto di 1.000.000 non riguarda l'algoritmo, che girerebbe felicemente su numeri molto più grandi: serve a far sì che ogni sottrazione, moltiplicazione e resto lungo la strada sia esatto in aritmetica ordinaria a doppia precisione, e che i passaggi stampati non possano diventare così lunghi da non essere più leggibili. Due numeri piuttosto piccoli possono comunque produrre molti giri — 610 e 377 ne impiegano tredici — ma nella pratica il conteggio è limitato dal tetto, e la tabella di riferimento ha una colonna con il numero di giri proprio per fartelo vedere variare. I passaggi sono stampati come equazioni — a = q * b + r, separati da punti e virgola — e non come divisioni in colonna, quindi se stai cercando la parentesi della divisione che si usa a scuola questa pagina non te la darà. Gli ingressi sono intercambiabili: la pagina li ordina in senso decrescente prima di partire, quindi non puoi usarla per vedere come sarebbe 3 = 0 * 5 + 3, perché quel giro non viene mai prodotto. Se i tuoi numeri possono essere negativi, o se vuoi che la convenzione sul resto sia scritta per esteso, la calcolatrice del resto è la pagina per quella domanda. I due campi accettano solo cifre: qui 1.000.000 va digitato come 1000000, senza i punti di separazione delle migliaia, perché è la stessa funzione che legge il valore a rifiutarli.

Che cos'è il massimo comun divisore, in una frase?

Il più grande numero intero che divide esattamente entrambi i numeri, senza lasciare resto. Per 1071 e 462 è 21: 1071 = 21 × 51 e 462 = 21 × 22, e 51 e 22 non hanno fattori in comune, ed è questo che rende 21 il massimo. Nota che anche 3 e 7 dividono entrambi i numeri: sono divisori comuni, semplicemente non il più grande. Il risultato principale della pagina è sempre questo numero, e i passaggi sotto sono la prova.

Perché l'ultimo passaggio finisce sempre con + 0?

Perché un resto uguale a zero è l'unica cosa che ferma l'algoritmo. Il ciclo sostituisce la coppia con una coppia più piccola, il secondo numero e il resto, e i numeri calano a ogni giro, quindi prima o poi devono arrivare a zero. 147 = 7 * 21 + 0 è il giro in cui succede, e il massimo comun divisore è il divisore di quel giro, 21. La pagina lo stampa invece di nasconderlo perché un elenco di passaggi che si fermasse all'ultimo resto non nullo lascerebbe al lettore il compito di capire che la ricerca era finita.

L'ordine in cui digito i due numeri ha importanza?

No. La pagina li mette in ordine decrescente prima del primo giro, quindi 462 e 1071 producono esattamente le stesse tre righe di 1071 e 462. È una scelta e non una proprietà dell'algoritmo — la regola MCD(a, b) = MCD(b, a) fa sì che entrambi gli ordini diano la risposta giusta — ma senza l'ordinamento la prima riga per la coppia 3 e 5 sarebbe 3 = 0 * 5 + 3, che è una divisione lecita ma si legge come se dividere un numero piccolo per uno più grande facesse parte del metodo. È anche il motivo per cui i campi di ingresso si chiamano primo numero e secondo numero invece che dividendo e divisore: quei due ruoli si scambiano a ogni giro.

Che cosa significa una risposta uguale a 1?

Che i due numeri non hanno alcun divisore in comune oltre a 1, il che è una risposta completa e non un fallimento. Numeri così si dicono coprimi, e la coppia 9 e 20 su questa pagina ne è un esempio. Ti dice anche qualcosa di pratico: la frazione 9/20 è già ai minimi termini, quindi non c'è nessuna semplificazione disponibile. Man mano che i numeri crescono, le coppie coprime diventano il caso comune, ed è per questo che il metodo conta in crittografia: costruire una chiave RSA significa trovare numeri che non abbiano divisori in comune con uno dato.

I numeri più grandi richiedono sempre più giri?

No, e la tabella di riferimento è lì per rendere concreta questa risposta. 1.000.000 e 999.998 finiscono in due giri, mentre 610 e 377 — tre cifre ciascuno — ne impiegano tredici. A imporre molti giri non è la grandezza, ma quanto lentamente i numeri si rimpiccioliscono, e le coppie che si rimpiccioliscono più lentamente sono i numeri di Fibonacci consecutivi, dove ogni resto è vicino al divisore. Quel risultato è il teorema di Lamé, e mette un tetto al numero di giri che cresce solo con il numero di cifre: è per questo che l'algoritmo è considerato veloce.

In che cosa è diverso dal fattorizzare entrambi i numeri?

Fattorizzare è molto più lavoro, ed è un lavoro che questa pagina non fa mai. Per fattorizzare 1071 per tentativi dovresti provare i divisori fino alla sua radice quadrata, circa 32; l'algoritmo invece divide un numero per uno che ha già in mano e finisce in tre giri. Su numeri piccoli come questi la differenza è invisibile, ma fattorizzare diventa drammaticamente più difficile man mano che i numeri crescono, mentre l'algoritmo di Euclide se ne accorge appena. È tutto lì il motivo per cui si insegna ancora, ed è anche il motivo per cui la risposta qui sopra esce dal ciclo invece che da un secondo calcolo: farli entrambi rischierebbe che i passaggi stampati non vadano d'accordo con il numero stampato sopra di essi.

• Euclidean Algorithm — the recurrence gcd(a, b) = gcd(b, a mod b), the proof that it terminates, and the connection to continued fractions — Wolfram MathWorld (United States)
• Greatest Common Divisor — what the greatest common factor is, and why gcd(a, 0) = a is the base case the algorithm stops on — Wolfram MathWorld (United States)
• Lamé's Theorem — the result that the pair taking the most rounds for its size is always a pair of consecutive Fibonacci numbers — Wolfram MathWorld (United States)
• Massimo comun divisore — che cos'è il MCD, perché si ottiene dall'ultimo resto non nullo dell'algoritmo di Euclide e perché il MCD è unico — Treccani, Istituto della Enciclopedia Italiana (Italia)