PGCD & PPCM (Plus Grand Commun Diviseur et Plus Petit Commun Multiple)


Téléchargez le programme exemple (3.31 Ko)

L'ensemble des diviseurs communs à deux nombres entiers A et B (voir La décomposition en Facteurs Premiers) possède un plus grand élément, appelé le Plus Grand Commun Diviseur, ou PGCD de A et de B.

Prenons par exemple la décomposition des nombre 12 et 4, on a les égalités suivantes:

12 = 1 * 2 * 2 * 3
4 = 1 * 2 * 2



On en déduit que: 

12 est divisible par {1, 2, 3, 4, 6 et 12} 
4 est divisible par {1, 2, et 4} 

4 est donc le Plus Grand Commun Diviseur à 12 et à 4. On note : 
4 = PGCD(12, 4)





La recherche du Plus Petit Commun multiple de deux nombres entiers A et B passe aussi par la La décomposition en Facteurs Premiers de ces 2 nombres. C'est en analysant la liste des facteurs que l'on peut calculer le plus petit commun multiple multiple ou PPCM de A et de B.

Prenons par exemple la décomposition des nombre 12 et 42, on a les égalités suivantes:

12 = 2 * 2 * 3
42 = 2 * 3 * 7



Le PPCM est égal au produit du produit des facteurs communs et des facteurs restants:

PPCM(12, 42) = 2 * 3 * 2 * 7



Le PPCM et le PGCD possèdent aussi une étonnante liaison, qui permet de les calculer plus rapidement une fois qu'on en connait un:

PPCM(A, B) * PGCD(A, B) = A * B



Calcul

Il y a plusieurs manières de calculer le PGCD et le PPCM:

La méthode qui nécessite le plus de calculs, mais la plus rapide pour l'ordinateur car elle n'utilise que des soustractions (présentée ici dans une version lisible) :

Méthode rapide

var
  a, x, y: integer;
begin
  Memo.Lines.Clear;
  x := abs(StrToInt(Edit1.Text));
  y := abs(StrToInt(Edit2.Text));
  while x <> y do
    begin
      if (x > y) then x := x - y;
      if (x < y) then y := y - x;
    end;
  Memo.Lines.Add('PGCD(' + Edit1.Text + ', ' + Edit2.Text + ') = ' + IntToStr(x));
  a := x;
  x := abs(StrToInt(Edit1.Text));
  y := abs(StrToInt(Edit2.Text));
  Memo.Lines.Add('PPCM(' + Edit1.Text + ', ' + Edit2.Text + ') = ' + IntToStr((x * y) div a));
end;



Ou l'algorithme d'Euclide, qui utilise la division (présenté ici dans une version lisible) :

Algorithme d'Euclide

var
  a, b, r: integer;
begin
  Memo.Lines.Clear;
  a := abs(StrToInt(Edit1.Text));
  b := abs(StrToInt(Edit2.Text));
  r := a mod b;
  while (r <> 0) do
    begin
      a := b;
      b := r;
      r := a mod b;
    end;
  Memo.Lines.Add('PGCD(' + Edit1.Text + ', ' + Edit2.Text + ') = ' + IntToStr(b));
  r := b;
  a := abs(StrToInt(Edit1.Text));
  b := abs(StrToInt(Edit2.Text));
  Memo.Lines.Add('PPCM(' + Edit1.Text + ', ' + Edit2.Text + ') = ' + IntToStr((a * b) div r));
end;



3 requête(s) SQL executée(s) en 0.001 Secs - Temps total de génération de la page : 0.007 Secs