1. Introduction

En mathématiques, le plus grand commun diviseur (PGCD) de deux nombres entiers est le plus grand entier qui divise ces deux nombres sans reste. Il est essentiel pour simplifier des fractions, résoudre des équations diophantiennes, etc.

2. Définition du PGCD

Soient deux entiers naturels \( extbf{a}\) et \( extbf{b}\). Le PGCD de \( extbf{a}\) et \( extbf{b}\), noté \( extbf{PGCD}(a, b)\), est le plus grand entier \(d\) tel que \(d \mid a\) et \(d \mid b\).

Par exemple, \( extbf{PGCD}(48, 60) = 12\).

3. Algorithme d’Euclide

L’algorithme d’Euclide permet de calculer efficacement le PGCD de deux nombres entiers naturels. Il repose sur la propriété suivante :

\( extbf{PGCD}(a, b) = extbf{PGCD}(b, a mod b) \)

où \(mod\) désigne le reste de la division euclidienne.

Voici la procédure :

1. On divise \(a\) par \(b\), on note le reste \(r\).
2. Si \(r = 0\), alors \(b\) est le PGCD.
3. Sinon, on remplace \(a\) par \(b\) et \(b\) par \(r\), puis on recommence.

Ce processus aboutit rapidement au résultat.

4. Exemple de calcul

Calculons le PGCD de 252 et 105 :

• Divisons 252 par 105 : \(252 = 105 imes 2 + 42\), reste \(r = 42\).
• Puis, calculons \( extbf{PGCD}(105, 42)\) :
• Divisons 105 par 42 : \(105 = 42 imes 2 + 21\), reste \(r = 21\).
• Ensuite, \( extbf{PGCD}(42, 21)\) :
• Divisons 42 par 21 : \(42 = 21 imes 2 + 0\), reste \(r = 0\).

Quand le reste est nul, le PGCD est le diviseur courant, ici 21. Donc, \( extbf{PGCD}(252, 105) = 21\).

5. Conclusion

Le PGCD permet de simplifier les calculs en arithmétique et est calculé efficacement grâce à l’algorithme d’Euclide. La connaissance de cette notion et de cet algorithme est fondamentale en mathématiques de niveau 2nde.