SKILLCARD « Algorithme d'Euclide : PGCD et PPCM » — PCSI

Quand l’utiliser ?

Pour calculer le PGCD de deux entiers sans les décomposer, puis leur PPCM.

La règle

a=bq+r, 0≤r<b ⟹ pgcd⁡(a,b)=pgcd⁡(b,r)a = bq + r,\ 0 \leq r < b \ \Longrightarrow\ \operatorname{pgcd}(a,b) = \operatorname{pgcd}(b,r) — Pour a,b≥1a, b \geq 1 : pgcd⁡(a,b)×ppcm⁡(a,b)=ab\operatorname{pgcd}(a,b) \times \operatorname{ppcm}(a,b) = ab.

La méthode

  1. Diviser aa par bb : a=bq+ra = bq + r.
  2. Remplacer (a,b)(a, b) par (b,r)(b, r) et recommencer tant que r≠0r \neq 0.
  3. Le dernier reste non nul est le PGCD ; le PPCM vaut abpgcd⁡(a,b)\frac{ab}{\operatorname{pgcd}(a,b)}.

Exemple

pgcd⁡(84,30)\operatorname{pgcd}(84, 30)

84=2×30+2484 = 2 \times 30 + 24, 30=24+630 = 24 + 6, 24=4×624 = 4 \times 6.

→ PGCD 66, PPCM 84×306=420\frac{84 \times 30}{6} = 420.

Les pièges à éviter

Le PGCD est le dernier reste non nul ; le PPCM n'est pas le produit abab en général.

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.