JeRaisonne

Toutes les SKILLCARDS
SKILLCARD « Algorithme d'Euclide et identité de Bézout » — MPSI

SKILLCARD · Algorithme

Algorithme d'Euclide et identité de Bézout — MPSI

  • Maths prépa
  • Arithmétique
  • MPSI
Travailler cette SKILLCARD

Exercices reliés, progression et HORA dans l’app JeRaisonne — le premier exercice est gratuit.

Quand l’utiliser ?

Pour calculer un PGCD et trouver u,vu, v tels que au+bv=pgcd⁡(a,b)au + bv = \operatorname{pgcd}(a,b).

La règle

∃(u,v)∈Z2,au+bv=a∧b\exists (u,v) \in \mathbb{Z}^2,\quad au + bv = a \wedge b — a∧b=1  ⟺  ∃(u,v), au+bv=1a \wedge b = 1 \iff \exists (u,v),\ au + bv = 1 (Bézout).

La méthode

  1. Divisions successives : a=bq+ra = bq + r, puis (a,b)←(b,r)(a,b) \leftarrow (b,r) jusqu'à r=0r = 0.
  2. Le dernier reste non nul est le PGCD.
  3. Remonter les calculs pour exprimer le PGCD en au+bvau + bv.

Exemple

pgcd⁡(30,21)\operatorname{pgcd}(30, 21) : 30=21+930 = 21 + 9, 21=2⋅9+321 = 2 \cdot 9 + 3, 9=3⋅39 = 3 \cdot 3 ; 3=21−2⋅9=3⋅21−2⋅303 = 21 - 2 \cdot 9 = 3 \cdot 21 - 2 \cdot 30 ⇒ 3=30⋅(−2)+21⋅33 = 30 \cdot (-2) + 21 \cdot 3

Les pièges à éviter

Le couple (u,v)(u,v) n'est pas unique : (u+kb′,v−ka′)(u + kb', v - ka') convient aussi.

La méthode HORA dans chaque Skill Card.

Chaque Skill Card te guide avec la méthode HORA pour réussir les exercices, faire progresser et entretenir ton niveau de maîtrise.

  1. Hypothèse

    Je comprends l’énoncé, j’identifie ce qu’on cherche et les informations données.

  2. Outil

    Je choisis l’outil mathématique adapté (définition, propriété, théorème, formule…).

  3. Raisonnement

    Je justifie pourquoi cet outil est pertinent et je construis ma démarche.

  4. Application

    J’applique la méthode au problème et je conclus en vérifiant le résultat.

SKILLCARDS proches