PGCD par soustractions successives | Question Flash Cycle 4

🎒 Pour les élèves

Effectue l'algorithme sur ton brouillon avant de cliquer sur Réponse.
Le chronomètre démarre automatiquement : 2 minutes, c'est parti !
Clique sur Nouvelle question pour un autre couple de nombres.
Recommence jusqu'à exécuter l'algorithme sans hésiter.

5ème 4ème 3ème Cycle 4

📽️ Pour les enseignants

Projetez cette page au TBI en début de séance.
Cliquez sur Nouvelle question sans recharger la page.
La correction affiche toutes les étapes de l'algorithme.
À utiliser après la méthode par listes de diviseurs et avant l'algorithme d'Euclide.

TBI Automatismes Arithmétique

📋 Programme : Nombres et calcul — Déterminer le PGCD de deux entiers par l'algorithme des soustractions successives (Cycle 4, B.O. 2020).

👨‍👩‍👧 Pour les parents

L'algorithme des soustractions successives est une méthode pour trouver le PGCD de deux nombres sans avoir à lister tous leurs diviseurs.

Le principe : on soustrait le plus petit au plus grand, et on recommence jusqu'à obtenir deux nombres égaux. Ce nombre égal est le PGCD.

Exemple : PGCD(12, 8)
12 − 8 = 4 → on a 8 et 4
8 − 4 = 4 → on a 4 et 4
PGCD(12, 8) = 4 ✓

Parents Algorithme

🔍 Pour les curieux

L'algorithme des soustractions successives est intuitif mais peut être très lent si les deux nombres sont très différents. Par exemple, PGCD(1000, 3) nécessiterait des centaines de soustractions !

C'est exactement pour remédier à ce problème qu'Euclide a remplacé les soustractions répétées par une seule division euclidienne (qui revient à faire toutes ces soustractions en une étape). Résultat : l'algorithme d'Euclide est bien plus rapide, en particulier pour les grands nombres.

Curieux Complexité algorithmique

📐 L'algorithme des soustractions successives

Principe

On soustrait le plus petit nombre au plus grand, et on recommence avec le résultat jusqu'à obtenir deux nombres égaux. Ce nombre est le PGCD.

Étapes

Si a > b : remplacer a par a − b.
Si b > a : remplacer b par b − a.
Répéter jusqu'à a = b.
PGCD = a (= b).

💡 Exemple : PGCD(18, 12)
18 − 12 = 6 → (6, 12)
12 − 6 = 6 → (6, 6)
PGCD(18, 12) = 6 ✓

⚠️ Pour les grands nombres, cet algorithme peut être long. Voir l'algorithme d'Euclide pour une méthode plus efficace.

📖 Leçon : arithmétique 🔗 PGCD sans algorithme 🔗 PGCD algorithme d'Euclide 🔗 Labyrinthe : multiples et diviseurs 🎲 Jeu : Juniper Green

Question Flash : PGCD par soustractions successives | Site2Wouf