Algèbre

PGCD et PPCM

Donner deux nombres a et b le plus grand commun diviseur, le plus petit commun multiple et les ensembles des diviseurs sont calculés.

Le PGCD est le plus gros élément d'insertion des ensembles diviseurs de a et b. Dans le calcul de fraction, le PGCD de numérateur et dénominateur est le plus grand nombre avec lequel la fraction peut être réduire.

Le PPCM est le plus petit élément d'insertion des ensembles de multiple de a et b. Dans le calcul de fraction, le PPCM des deux dénominateurs est le dénominateur commun.

Si on a déjà calculé le PGCD(a,b), le PPCM(a,b) est calculé avec la formule.

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

Exemple:

a = 1001    b = 3575

Le plus grand commun diviseur   PGCD = 143
Le plus petit commun multiple   PPCM = 25025

T(a) = { 1 7 11 13 77 91 143 1001 }
T(b) = { 1 5 11 13 25 55 65 143 275 325 715 3575 }

Méthode

Le PGCD de deux nombres peut être déterminée par la décomposition en facteurs premiers. Si les nombres sont tros grands, l'algorithme d'Euclide peut aider.

L'algorithme d'Euclide en PASCAL:

function PGCD(a,b:integer):integer;
  var 
    r: integer;		
  begin 
    repeat
      r := a mod b;
      a := b;
      b := r;
    until r=0;
    result := a;
  end;
      

Voir aussi:

Wikipedia: Plus grand commun diviseur
fra.matheass.eu