PGCD et PPCM par l'algorithme d'Euclide

Application directe du cours · niveau 2 · mathématiques (PTSI), chapitre 1 — Raisonnement et vocabulaire ensembliste · G. Divisibilité, division euclidienne, PGCD et PPCM

Énoncé

Calculer $1071 \land 462$ à l'aide de l'algorithme d'Euclide, puis en déduire $1071 \lor 462$ .
Retrouver ces résultats à partir des décompositions en facteurs premiers $1071 = 3^{2} \times 7 \times 17$ et $462 = 2 \times 3 \times 7 \times 11$ .

Corrigé

Exécutons l'algorithme d'Euclide, chaque étape étant une division euclidienne :

$1071 = 2 \times 462 + 147, 462 = 3 \times 147 + 21, 147 = 7 \times 21 + 0.$

Le dernier reste non nul est $21$ , donc $1071 \land 462 = 21$ . D'après la relation $(a \land b) (a \lor b) = ab$ :

$1071 \lor 462 = \frac{1071 \times 462}{21} = 1071 \times 22 = 23 562.$

Sur les décompositions $1071 = 3^{2} \times 7 \times 17$ et $462 = 2 \times 3 \times 7 \times 11$ , le PGCD s'obtient avec les plus petits exposants et le PPCM avec les plus grands :

$1071 \land 462 = 3 \times 7 = 21, 1071 \lor 462 = 2 \times 3^{2} \times 7 \times 11 \times 17 = 23 562.$

On retrouve bien les résultats de la première question.

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.