PGCD, algorithme d'Euclide et identité de Bézout

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

Énoncé

Exercice 2 — PGCD, Bézout et équation diophantienne

On pose a = et b = .

  1. Appliquer l'algorithme d'Euclide pour calculer d = . Détailler chaque étape.

  2. En remontant les étapes de l'algorithme (méthode de remontée), exprimer d sous la forme d = avec . On donnera explicitement les valeurs de u et v.

  3. Résoudre dans l'équation diophantienne : .
    On donnera l'ensemble de toutes les solutions entières.

  4. Un marchand de Marrakech vend des sachets de dattes de deux formats : le grand format contient g et le petit format g. Il souhaite constituer des lots de masse exactement égale en combinant des sachets des deux formats (en pouvant éventuellement retirer des sachets d'un lot déjà constitué, ce qui revient à autoriser des coefficients négatifs). Quelle est la plus petite masse strictement positive réalisable ? Justifier à l'aide des questions précédentes.

Indices

— clique pour révéler
1 Indice 1
Pour calculer le PGCD avec l'algorithme d'Euclide, commence par diviser $252$ par $180$ et note le reste. Puis divise $180$ par ce reste, et continue jusqu'à obtenir un reste nul.
2 Indice 2
Une fois le PGCD trouvé, remonte les divisions : exprime le dernier reste non nul en fonction de l'avant-dernier, puis remplace dans cette expression chaque reste par sa valeur tirée des divisions précédentes.

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 calculer le PGCD avec l'algorithme d'Euclide, commence par diviser par et note le reste. Puis divise par ce reste, et continue jusqu'à obtenir un reste nul.

Une fois le PGCD trouvé, remonte les divisions : exprime le dernier reste non nul en fonction de l'avant-dernier, puis remplace dans cette expression chaque reste par sa valeur tirée des divisions précédentes.

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

Entiers premiers entre eux et équation diophantienne — Intermédiaire Tous les exercices du chapitre Divisibilité et congruences — Premiers pas