PGCD par algorithme d'Euclide et identité de Bézout — Bac Côte d'Ivoire 2023

Facile Inspiré BAC Côte d'Ivoire
Partager
Exercice inspiré d'un BAC Côte d'Ivoire
Source-style : BAC Côte d'Ivoire Série C 2023
Inspiré du style BAC Côte d'Ivoire Série C 2023
Énoncé et solution adaptés au programme marocain. Voir crédits.

Énoncé

Exercice 2 — PGCD, Bézout et application (Niveau : Facile)

On considère les entiers a = 252 et b = 189.

  1. Appliquer l'algorithme d'Euclide pour calculer d = pgcd(252, 189). Détailler toutes les étapes.
  2. En remontant les étapes de l'algorithme, déterminer deux entiers u et v tels que 252u + 189v = d. (Identité de Bézout)
  3. En déduire l'ensemble des solutions entières de l'équation 252x + 189y = 63.
  4. Parmi ces solutions, trouver celle pour laquelle x est le plus petit entier naturel possible.

Indices

— clique pour révéler
1 Indice 1
Pour l'algorithme d'Euclide, commence par diviser $252$ par $189$ et note le reste. Répète ensuite avec $189$ et ce reste jusqu'à obtenir un reste nul.
2 Indice 2
Pour Bézout, reprends la première ligne de l'algorithme : $252 = 1 \times 189 + 63$. Isole le reste $63$ pour l'exprimer comme combinaison de $252$ et $189$.

Bloqué sur cet exercice ?

Prof Hicham peut t'expliquer pas à pas, en s'adaptant à ton niveau.

Demander à Prof Hicham

La méthode — par où commencer

Pour l'algorithme d'Euclide, commence par diviser par et note le reste. Répète ensuite avec et ce reste jusqu'à obtenir un reste nul.

Pour Bézout, reprends la première ligne de l'algorithme : . Isole le reste pour l'exprimer comme combinaison de et .

La rédaction complète, étape par étape, se trouve juste en dessous.

Exercice Terminé? 🎉

Validez votre réponse pour enregistrer votre progression et gagner des points

Congruences et reste de grandes puissances Tous les exercices du chapitre Congruences avancées, invariants et caractérisation d'entiers