Calculer le PGCD de 24 et 36.
\(\gcd(24,36)=12\)
Le PGCD (Plus Grand Commun Diviseur) de deux entiers est le plus grand entier qui divise simultanément ces deux nombres sans laisser de reste. Pour le calculer de manière efficace, on utilise l’algorithme d’Euclide.
L’algorithme repose sur l’idée que le PGCD de deux nombres ne change
pas si l’on remplace le plus grand par son reste dans la division
euclidienne par le plus petit. Concrètement, pour deux entiers positifs
:
1. On divise le plus grand par le plus petit et on note le reste.
2. On remplace le premier nombre par le second, et le second par le
reste.
3. On répète l’opération jusqu’à obtenir un reste nul.
4. Le PGCD est alors le dernier reste non nul.
Nous voulons calculer \(\gcd(24,36)\).
On divise le plus grand, 36, par le plus petit, 24 :
\[ 36 = 24 \times 1 + 12 \]
Le reste est 12. Comme il n’est pas nul, on poursuit.
On remplace 36 par 24 et 24 par 12, puis on divise :
\[ 24 = 12 \times 2 + 0 \]
Le reste est 0. À ce stade, l’algorithme s’arrête.
Le dernier reste non nul est 12, donc :
\[ \gcd(24,36)=12 \]
Ainsi, le plus grand entier qui divise à la fois 24 et 36 est 12.