PGCD et PPCM

Avant de commencer

Vous voulez simplifier la fraction 60/84. Il faut trouver le plus grand diviseur commun à 60 et 84. Comment l'algorithmique résout-elle ce problème ?

1. PGCD par soustractions successives

Principe : PGCD(a, b) = PGCD(a − b, b) si a > b. On remplace le plus grand par la différence, jusqu'à ce que les deux soient égaux.

FUNCTION PGCD_Soustraction(a, b : integer) : integer;
BEGIN
  WHILE a <> b DO
    IF a > b THEN
      a := a - b
    ELSE
      b := b - a;
  PGCD_Soustraction := a;
END;

Trace pour PGCD(60, 84) : (84,60) → (24,60) → (24,36) → (24,12) → (12,12). Résultat : 12.

2. Algorithme d'Euclide (par modulo)

Bien plus rapide : PGCD(a, b) = PGCD(b, a mod b). On s'arrête quand b = 0.

DEF FN PGCD(a, b : entier) : entier
  Tant que b ≠ 0 Faire
    r ← a mod b
    a ← b
    b ← r
  FinTantQue
  PGCD ← a
Fin PGCD

DEF FN PGCD(a, b : entier) : entier
  Tant que b ≠ 0 Faire
    r ← a mod b
    a ← b
    b ← r
  FinTantQue
  PGCD ← a
Fin PGCD

FUNCTION PGCD(a, b : integer) : integer;
VAR r : integer;
BEGIN
  WHILE b <> 0 DO
  BEGIN
    r := a MOD b;
    a := b;
    b := r;
  END;
  PGCD := a;
END;

Trace pour PGCD(60, 84) — état (a, b) après chaque tour :

Résultat : PGCD = 12 en 4 tours.

3. PPCM

PPCM(a, b) = (a × b) / PGCD(a, b)

FUNCTION PPCM(a, b : integer) : integer;
BEGIN
  PPCM := (a * b) DIV PGCD(a, b);
END;

Exemple : PPCM(60, 84) = (60 × 84) / 12 = 5040 / 12 = 420.

4. Exercices

PROCEDURE Reduire(VAR n, d : integer);
VAR p : integer;
BEGIN
  p := PGCD(ABS(n), ABS(d));   { utilise valeur absolue }
  n := n DIV p;
  d := d DIV p;
END;

{ Test : 60/84 → 5/7 }

FUNCTION PGCD_Tab(T : Tab; n : integer) : integer;
VAR i, res : integer;
BEGIN
  res := T[1];
  FOR i := 2 TO n DO
    res := PGCD(res, T[i]);
  PGCD_Tab := res;
END;

5. Erreurs fréquentes au bac

• Inverser l'ordre des affectations dans Euclide : a := b; b := a MOD b; écrase a avant de calculer le mod.
• Diviser par 0 si b = 0 au départ (cas particulier à tester).
• PPCM = a × b / PGCD : risque d'overflow pour grands entiers.

6. Quiz