18. Trouver un pgcd avec l'algorithme d'Euclide

Comment trouver un PGCD avec l'algorithme d'Euclide en Terminale Maths expertes ?

Pour calculer le Plus Grand Commun Diviseur (PGCD) de deux nombres entiers, la méthode classique de la décomposition en facteurs premiers peut vite devenir longue et très fastidieuse si les nombres étudiés sont grands. En spécialité Maths expertes, tu vas apprendre une technique beaucoup plus puissante, directe et moins sujette aux erreurs de calcul : l'algorithme d'Euclide.

Le principe repose sur une propriété fondamentale de la division euclidienne et de l'arithmétique : si tu cherches le PGCD de deux entiers naturels \(a\) et \(b\), tu as le droit de chercher à la place le PGCD de \(b\) et du reste de la division euclidienne de \(a\) par \(b\). En résumé, la formule centrale est \(\text{PGCD}(a ; b) = \text{PGCD}(b ; r)\).

En répétant cette propriété en boucle, tu vas faire chuter la taille des nombres très rapidement. La méthode d'Euclide affirme que, dans cette suite de divisions, le PGCD cherché correspond exactement au dernier reste non nul obtenu avant de tomber sur une division dont le reste est égal à zéro.

Quelle est la méthode étape par étape pour calculer le PGCD d'après la vidéo ?

Dans la vidéo de cours de cette page, on te montre comment déterminer le \(\text{PGCD}(3046 ; 400)\). Au lieu de tester des dizaines de diviseurs potentiels, on applique l'algorithme en divisant à chaque étape le diviseur précédent par le reste précédent, jusqu'à obtenir un reste nul.

Voici la rédaction détaillée de cet exemple :

• On divise d'abord \(3046\) par \(400\) : \[3046 = 7 \times 400 + 246\]
• On prend les deux nouveaux nombres (le diviseur \(400\) et le reste \(246\)) pour une nouvelle division : \[400 = 1 \times 246 + 154\]
• On recommence avec \(246\) et \(154\) : \[246 = 1 \times 154 + 92\]
• Puis avec \(154\) et \(92\) : \[154 = 1 \times 92 + 62\]
• On continue avec \(92\) et \(62\) : \[92 = 1 \times 62 + 30\]
• Puis avec \(62\) et \(30\) : \[62 = 2 \times 30 + 2\]
• Et enfin, on divise \(30\) par \(2\) : \[30 = 15 \times 2 + 0\]

L'algorithme s'arrête ici de manière définitive car on a obtenu un reste nul. D'après le théorème, le PGCD est le dernier reste non nul de ces calculs successifs. En remontant d'une ligne, on lit clairement que c'est le nombre \(2\). On en déduit de façon certaine que \(\text{PGCD}(3046 ; 400) = 2\).

Comment réussir les exercices interactifs et éviter les pièges classiques ?

Pour maîtriser cet algorithme incontournable du programme de Terminale, rien ne remplace la pratique régulière. Les 6 exercices interactifs ci-dessous sont là pour t'entraîner sur la mécanique du calcul et sur les applications concrètes que tu croiseras dans tes contrôles.

Voici un aperçu des notions abordées et des erreurs à ne pas commettre :

• La maîtrise mécanique de l'algorithme : Les exercices 1, 2 et 3 te guident pas à pas dans l'enchaînement des divisions euclidiennes. Le piège classique des élèves est de s'emmêler les pinceaux en recopiant les nombres pour l'étape suivante. Souviens-toi bien : on reprend toujours le diviseur et le reste, il ne faut surtout pas utiliser le quotient !
• La recherche d'un diviseur inconnu : L'exercice 4 te demande de retrouver un entier à partir de l'énoncé de ses restes. Attention au piège théorique majeur de l'arithmétique : par définition, dans toute division euclidienne, le diviseur doit être strictement supérieur au reste. Sans cette condition indispensable, tu ne pourras pas déterminer la bonne valeur finale.
• Le lien avec le PPCM : L'exercice 5 fait appel à une formule cruciale de ton cours. Tu devras utiliser la propriété qui relie le produit du PGCD et du PPCM au produit des deux entiers de départ.
• La modélisation de problèmes géométriques : L'exercice 6 te met au défi de remplir une boîte avec des cubes. Tu devras ici calculer le PGCD de trois dimensions (astuce : on calcule le PGCD des deux premiers nombres, puis le PGCD de ce résultat avec le troisième). Le vrai piège se cache dans la toute dernière question : obtenir l'arête du cube ne suffit pas à donner le nombre total de cubes ! Pense à bien calculer et multiplier entre elles les quantités de cubes présentes sur la longueur, la largeur et la hauteur.

Prends une feuille de brouillon pour poser soigneusement tes divisions successives et valide tes réponses directement dans les champs pour vérifier que tu as bien compris le chapitre !