L’algorithme d’Euclide donne le PGCD de deux entiers. Que devient-il lorsqu’on en a trois ? Et quel lien le PGCD entretient-il avec le PPCM ? L’exercice qui suit répond à ces deux questions, puis en pose une troisième dont la réponse surprend presque tous les élèves — et quelques enseignants. Le corrigé paraîtra dans notre prochain article, consacré à l’identité de Bézout.
Cet exercice fait suite à notre article sur l’algorithme d’Euclide, dont il réutilise directement la méthode. Il ne demande aucune connaissance supplémentaire.
Exercice
Partie A — Trois entiers
On pose 
- Calculer
par l’algorithme d’Euclide, en écrivant chaque division.
- Démontrer que, pour tous entiers naturels non nuls
,
et
, on a
. On raisonnera sur les ensembles de diviseurs communs, comme dans l’article précédent.
- En déduire
.
- Vérifier le résultat en décomposant les trois nombres en facteurs premiers. Laquelle des deux méthodes a été la plus rapide ?
Partie B — Le lien entre PGCD et PPCM
- Calculer
sans chercher de nouveau les facteurs premiers.
- Démontrer que, pour tous entiers naturels non nuls
.
Partie C — La question qui piège
- La relation de la question 6 se généralise-t-elle à trois entiers ? Autrement dit, a-t-on toujours
? Répondre en justifiant, et produire un contre-exemple s’il y a lieu.
La question 7 mérite qu’on s’y arrête. Une identité vraie pour deux nombres semble naturellement devoir l’être pour trois : c’est là une des habitudes de pensée les plus coûteuses en mathématiques. Le contre-exemple le plus court tient en trois caractères.
Des exercices de ce type, entièrement corrigés, figurent au chapitre 3 de Mathématiques en terminales scientifiques, Tome 2 — Arithmétique : cours et exercices corrigés.
Formalis Mathematica 