PGCD par l'algorithme d'Euclide | 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'à maîtriser les étapes de l'algorithme.

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 divisions euclidiennes successives.
À utiliser après la méthode par diviseurs et les soustractions successives.

TBI Automatismes Arithmétique

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

👨‍👩‍👧 Pour les parents

L'algorithme d'Euclide est une méthode rapide pour trouver le PGCD en utilisant des divisions euclidiennes successives plutôt que des soustractions.

Chaque étape s'écrit : a = b × q + r
On continue en remplaçant a par b et b par r, jusqu'à obtenir un reste nul. Le dernier diviseur non nul est le PGCD.

Exemple : PGCD(48, 18)
48 = 18 × 2 + 12
18 = 12 × 1 + 6
12 = 6 × 2 + 0
PGCD(48, 18) = 6 ✓

Parents Division euclidienne

🔍 Pour les curieux

L'algorithme d'Euclide date d'environ 300 av. J.-C. et figure dans les Éléments d'Euclide — l'un des ouvrages mathématiques les plus influents de l'histoire. C'est l'un des plus anciens algorithmes encore utilisés aujourd'hui.

On le retrouve au cœur de la cryptographie moderne : le chiffrement RSA, qui sécurise vos connexions bancaires et messageries, repose directement sur des calculs de PGCD et de nombres premiers entre eux. Euclide sécurise vos achats en ligne depuis 2 300 ans !

Curieux Cryptographie

📐 L'algorithme d'Euclide

Principe

À chaque étape, on effectue la division euclidienne du plus grand par le plus petit : a = b × q + r.
On remplace ensuite (a, b) par (b, r) et on recommence jusqu'à obtenir un reste r = 0. Le PGCD est le dernier diviseur non nul.

Étapes

Diviser a par b : a = b × q + r.
Si r = 0 : PGCD = b. Fin.
Sinon : remplacer a par b et b par r. Retour à 1.

💡 Exemple : PGCD(252, 84)
252 = 84 × 3 + 0
Reste = 0 dès la 1ère étape → PGCD(252, 84) = 84 ✓

💡 Exemple plus complexe : PGCD(144, 60)
144 = 60 × 2 + 24
60 = 24 × 2 + 12
24 = 12 × 2 + 0
PGCD(144, 60) = 12 ✓

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

Question Flash : PGCD par l'algorithme d'Euclide | Site2Wouf