QuickCalculators esegue l'algoritmo di Euclide su due interi non negativi, stampando ogni quoziente e resto finché compare il MCD come ultimo resto non nullo. Inserisci la coppia in qualsiasi ordine; la tabella dei passaggi mostra la forma di divisione così ogni riga è verificabile a mano.
Trovare il MCD con divisioni ripetute
L'algoritmo di Euclide trova il massimo comun divisore dividendo il numero maggiore per il minore e sostituendo il maggiore con il resto, poi ripetendo. Quando compare resto zero, il divisore di quel passo è il MCD. Euclid's Algorithm Calculator registra ogni divisione così la catena è controllabile.
Per 816 e 2260, iniziare con 2260 ÷ 816. Il quoziente è 2 e il resto 628. Poi 816 ÷ 628 lascia resto 188. Continuare finché un resto zero ferma la catena. L'ultimo resto non nullo è il MCD della coppia originale.
Leggere la tabella dei passaggi
La tabella elenca dividendo, divisore, quoziente e resto per ogni round. Scendere nella colonna dei resti mostra la sequenza decrescente che termina a zero. QuickCalculators allinea quelle colonne così una copia su quaderno può verificare a × b + r uguale al dividendo precedente su ogni riga.
Schizzo compatto per 48 e 18:
| Dividendo | Divisore | Quoziente | Resto |
|---|---|---|---|
| 48 | 18 | 2 | 12 |
| 18 | 12 | 1 | 6 |
| 12 | 6 | 2 | 0 |
L'ultimo resto non nullo è 6, quindi MCD(48, 18) = 6.
Evitare questo errore comune
La forma per sottrazione e la forma per divisione sono lo stesso algoritmo. La divisione è sottrazione ripetuta compressa in un quoziente. A volte gli studenti le trattano come metodi rivali con risposte diverse. Entrambe terminano allo stesso MCD se eseguite correttamente. Sottrarre 18 da 48 due volte arriva a 12, esattamente ciò che il quoziente 2 codifica in una riga.
Preferire la divisione risparmia scrittura senza cambiare il percorso matematico descritto da Euclide.
Comprendere perché l'algoritmo termina sempre
Ogni resto è un intero non negativo strettamente minore del divisore precedente, quindi la sequenza dei resti non può scendere all'infinito. La discesa finita forza un resto zero dopo un numero finito di passaggi. Questa garanzia vale per tutti gli input interi non negativi accettati dalla pagina.
Coppie peggiori legate ai numeri di Fibonacci richiedono più passaggi degli esempi didattici tipici, ma terminano comunque. Il conteggio dei passaggi cresce approssimativamente con il logaritmo degli input per coppie casuali ordinarie, ed è per questo che il metodo di Euclide scala oltre l'elenco dei divisori.
Domande frequenti
Cos'è l'algoritmo di Euclide?
È un metodo per trovare il massimo comun divisore di due interi non negativi con divisioni ripetute con resto. L'ultimo resto non nullo è il MCD. La calcolatrice stampa ognuno di quei passaggi di divisione.
Come l'algoritmo di Euclide trova il MCD?
Sostituendo il numero maggiore con il resto dopo divisione per il minore, ripetendo finché il resto è zero. Il divisore usato nel passo con ultimo resto non nullo è il MCD.
Qual è il MCD di 816 e 2260?
Si trova eseguendo l'algoritmo di Euclide su quella coppia e leggendo l'ultimo resto non nullo dalla tabella dei passaggi. Inserire entrambi gli interi in questa pagina per vedere ogni quoziente e resto in ordine.
Perché l'algoritmo di Euclide funziona?
Ogni divisore comune di a e b è anche divisore comune di b e a mod b. Sostituire la coppia con il numero minore e il resto preserva il MCD finché il resto arriva a zero.
Quanti passaggi richiede l'algoritmo di Euclide?
Dipende dagli input; ogni resto è minore del divisore precedente, quindi il processo è finito. Coppie in stile Fibonacci richiedono più passaggi della media, ma numeri tipici da compito finiscono rapidamente.
Qual è la differenza tra forme per sottrazione e divisione?
La forma per sottrazione toglie ripetutamente il minore dal maggiore; la forma per divisione sottrae in blocco con un quoziente. Entrambe calcolano lo stesso MCD. La divisione è solo sottrazione ripetuta scritta in modo compatto.
Riepilogo
Euclid's Algorithm Calculator trova un MCD con divisioni ripetute e mostra ogni quoziente e resto in una tabella dei passaggi. Coppie come 48 e 18 terminano a resto 6, coincidente con MCD(48, 18). Forme per sottrazione e divisione sono lo stesso algoritmo a livelli di compressione diversi. I resti diminuiscono strettamente, quindi il processo termina sempre per interi non negativi.