QuickCalculators exécute l’algorithme d’Euclide sur deux entiers non négatifs, imprimant chaque quotient et reste jusqu’à ce que le PGCD apparaisse comme dernier reste non nul. Entrez la paire dans l’un ou l’autre ordre; Le tableau des étapes montre la forme de division afin que chaque ligne puisse être vérifiée à la main.
Trouver le PGCD par division répétée
L’algorithme d’Euclide trouve le plus grand facteur commun en divisant le plus grand par le plus petit et en remplaçant le plus grand par le reste, puis en répétant. Lorsqu’un reste de zéro apparaît, le diviseur de cette étape est la PGCD. la calculatrice d’algorithmes d’Euclid enregistre chaque division afin que la chaîne soit auditable.
Pour 816 et 2260, commencez par 2260 ÷ 816. Le quotient est 2 et le reste est 628. Ensuite, 816 ÷ 628 laisse le reste 188. Continuez jusqu’à ce qu’un reste zéro arrête la chaîne. Le dernier reste non nul est la PGCD de la paire originale.
Lisez le tableau d’étape
Le tableau d’étapes indique le dividende, le diviseur, le quotient et le reste pour chaque tour. En lisant la colonne du reste, on voit la séquence de réduction qui se termine à zéro. QuickCalculators aligne ces colonnes de sorte qu’une copie de carnet puisse vérifier que × b + r est égal au dividende précédent sur chaque ligne.
Un croquis compact pour les 48 et 18:
| Dividende | Diviseur | Quotient | Reste |
|---|---|---|---|
| 48 | 18 | 2 | 12 |
| 18 | 12 | 1 | 6 |
| 12 | 6 | 2 | 0 |
Le dernier reste non nul est 6, donc PGCD(48, 18) = 6.
Éviter cette erreur courante
La forme de soustraction et la forme de division sont le même algorithme. La division est une soustraction répétée compressée en un quotient. Les élèves les considèrent parfois comme des méthodes rivales avec des réponses différentes. Les deux se terminent au même PGCD lorsqu’ils sont correctement appliqués. Soustraire 18 de 48 deux fois obtient 12, ce qui est exactement ce que le quotient 2 encode en une seule ligne.
Préférer la division permet d’économiser l’écriture sans modifier le chemin mathématique décrit par Euclide.
Comprendre pourquoi l’algorithme se termine toujours
Chaque reste est un entier non négatif strictement plus petit que le diviseur précédent, donc la suite du reste ne peut pas descendre indéfiniment. La descente finie force un reste zéro après un nombre fini d’étapes. Cette garantie est valable pour toutes les entrées entières non négatives que la page accepte.
Les paires de pires cas liées aux nombres de Fibonacci nécessitent plus d’étapes que les exemples typiques en classe, tout en restant terminées. Le nombre de pas croît approximativement avec le logarithme des entrées pour les paires aléatoires ordinaires, c’est pourquoi la méthode d’Euclide dépasse les facteurs de listage.
Questions fréquentes
Qu’est-ce que l’algorithme d’Euclide?
L’algorithme d’Euclide est une méthode permettant de déterminer le facteur commun le plus élevé de deux entiers non négatifs par division répétée avec le reste. Le dernier reste non nul est le PGCD. La calculatrice affiche chacune de ces étapes de division.
Comment l’algorithme d’Euclide trouve-t-il la PGCD?
L’algorithme d’Euclide trouve la PGCD en remplaçant le nombre le plus grand par le reste après division par le plus petit nombre, répétant jusqu’à ce que le reste soit nul. Le diviseur utilisé dans la dernière étape non nulle est la PGCD.
Quel est le PGCD de 816 et 2260?
La PGCD de 816 et 2260 est trouvée en exécutant l’algorithme d’Euclide sur cette paire et en lisant le dernier reste non nul à partir de la table d’étapes. Entrez les deux entiers sur cette page pour voir chaque quotient et reste dans l’ordre.
Pourquoi l’algorithme d’Euclide fonctionne-t-il?
L’algorithme d’Euclide fonctionne parce que tout diviseur commun de a et b est aussi un diviseur commun de b et d’un mod b. Remplacer la paire par le plus petit nombre et le reste préserve la PGCD jusqu’à ce que le reste atteigne zéro.
Combien d’étapes prend l’algorithme d’Euclide?
Le nombre d’étapes que l’algorithme d’Euclide effectue dépend des entrées; chaque reste est plus petit que le diviseur à priori, donc le processus est fini. Les paires de type Fibonacci nécessitent plus d’étapes que la moyenne, mais les nombres typiques en classe se terminent rapidement.
Quelle est la différence entre les formes de soustraction et de division?
La forme de soustraction soustrait à plusieurs reprises le plus petit du plus grand; La forme de division soustrait en volume à l’aide d’un quotient. Les deux formes calculent le même PGCD. La division est simplement une soustraction répétée écrite de manière compacte.
Résumé
la calculatrice d’algorithmes d’Euclide trouve une PGCD par division répétée et affiche chaque quotient et reste dans une table à pas. Des paires comme 48 et 18 se terminent au reste 6, correspondant à PGCD(48, 18). Les formes de soustraction et de division sont le même algorithme à différents niveaux de compression. Les restes diminuent strictement, donc le processus se termine toujours pour les entiers non négatifs.