Adloun

mathématiques (PCSI) · Chapitre 1 · Application directe du cours

PGCD et PPCM par l'algorithme d'Euclide

Raisonnement et vocabulaire ensembliste · G. Divisibilité, division euclidienne, PGCD et PPCM · niveau 2

É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.

Exercices semblables

Le PGCD de deux nombres de Mersenne corrigé
Problème — Le théorème de Lamé corrigé
Division euclidienne corrigé
Image directe de l'intersection corrigé
Reconstituer deux entiers d'après leur PGCD et leur PPCM corrigé

Le cours du chapitre · Tous les exercices du chapitre