🏷 Thème : Pgcd

Ce qu'il faut savoir

Le PGCD de deux entiers est le plus grand des nombres entiers qui les divisent tous les deux. Chaque mot du sigle compte, et le lire en entier évite déjà la confusion la plus fréquente du chapitre : un diviseur commun ne peut pas dépasser le plus petit des deux nombres.

Trois façons de le trouver — et quand utiliser laquelle

• Par la liste des diviseurs. On écrit les diviseurs de chacun, on repère les communs, on prend le plus grand. Simple et sûr, mais impraticable au-delà de nombres à deux chiffres.
• Par la décomposition en facteurs premiers. On décompose les deux nombres, puis on garde les facteurs communs affectés du plus petit exposant. Efficace, et surtout parlant : on voit ce que les deux nombres ont en commun.
• Par l'algorithme d'Euclide. La méthode qui ne recule devant aucun nombre.

Le principe qui le fait fonctionner tient en une ligne : tout diviseur commun à deux nombres divise aussi leur reste. Chaque étape remplace donc le problème par un problème plus petit ayant la même réponse, jusqu'à ce qu'il devienne évident.

Premiers entre eux, et fractions irréductibles

Deux entiers dont le PGCD vaut 1 sont dits premiers entre eux : ils n'ont aucun diviseur commun autre que 1. Attention, cela ne veut pas dire qu'ils sont premiers — 8 et 9 sont premiers entre eux sans qu'aucun des deux ne soit un nombre premier.

C'est de là que vient l'usage le plus courant du PGCD. Une fraction est irréductible exactement lorsque son numérateur et son dénominateur sont premiers entre eux. Pour la rendre irréductible, on divise l'un et l'autre par leur PGCD — et l'on obtient le résultat en une seule étape, là où les simplifications successives s'y reprennent à trois fois et s'arrêtent souvent trop tôt.

Les erreurs classiques

• 1.Confondre PGCD et PPCM. Le PGCD divise les deux nombres : il est donc inférieur ou égal au plus petit des deux. Le PPCM en est un multiple : il est supérieur ou égal au plus grand. Un PGCD annoncé plus grand que l'un des deux nombres est impossible, et cela se voit sans vérifier le calcul.
• 2.Prendre le dernier reste au lieu du dernier reste non nul. L'algorithme d'Euclide se termine sur un reste nul, et zéro n'est évidemment pas le PGCD. La réponse est la valeur juste au-dessus, dans la ligne précédente.
• 3.Prendre le plus grand exposant dans la décomposition. Pour le PGCD, on retient les facteurs communs au plus petit exposant — le plus grand donnerait un nombre qui ne divise plus les deux. C'est le PPCM qui prend les plus grands.
• 4.Oublier les facteurs non communs… ou les inclure. Un facteur premier qui n'apparaît que dans l'un des deux nombres ne peut pas faire partie d'un diviseur commun. On ne garde que ce qui figure des deux côtés.
• 5.Confondre diviseur et multiple. 6 est un diviseur de 24, et 24 est un multiple de 6. Les deux mots décrivent la même relation vue des deux bouts, et les intervertir renverse tout l'exercice.
• 6.Ne pas vérifier. Le contrôle est immédiat et gratuit : le PGCD trouvé doit diviser les deux nombres de départ, sans reste. Deux divisions suffisent à écarter presque toutes les erreurs de calcul.

Avant et après

Ce qu'il faut maîtriser avant

• La division euclidienne — quotient et reste —, sans laquelle l'algorithme d'Euclide reste une recette incompréhensible.
• Les diviseurs et les multiples d'un entier, et les critères de divisibilité.
• Les nombres premiers et la décomposition, vus en arithmétique.
• Les tables de multiplication et le calcul mental, qui rendent la recherche de diviseurs immédiate.

Ce que ça prépare

• La simplification des fractions, où le PGCD transforme une suite d'essais en une seule division.
• Les problèmes de partage et d'organisation, qui se retrouvent bien au-delà des mathématiques.
• La cryptographie : les nombres premiers entre eux sont au cœur du chiffrement moderne.
• Au lycée et au-delà : l'arithmétique modulaire, les congruences, et l'algorithme d'Euclide étendu — le même, poussé un cran plus loin.