MatheAss 9.0 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 dans l'intersection des ensembles diviseurs de a et b. Dans le calcul de fraction, le PGCD du numérateur et du dénominateur est le plus grand nombre avec lequel la fraction peut être réduite.

Le PPCM est le plus petit élément dans l'intersection 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 1:

a = 24    b = 256

Le plus grand commun diviseur   PGCD = 8
Le plus petit commun multiple     PPCM = 768

Les ensembles des diviseurs:
T(a) = { 1 2 3 4 6 8 12 24}
T(b) = { 1 2 4 8 16 32 64 128 256}

T(a) ∩ T(b) = { 1 2 4 8}

Exemple 2:

a = 195
b = 234
c = 273

Le plus grand commun diviseur   PGCD = 39
Le plus petit commun multiple     PPCM = 8190

Les ensembles des diviseurs: 
T(a) = { 1 3 5 13 15 39 65 195}
T(b) = { 1 2 3 6 9 13 18 26 39 78 117 234}
T(c) = { 1 3 7 13 21 39 91 273}

T(a) ∩ T(b) ∩ T(c) = { 1 3 13 39}

Exemple 3:

De plus, la somme de tous les diviseurs σ(n) et la somme des diviseurs propres σ*(n) sont déterminées.
Les nombres qui sont égaux à la somme de leurs propres diviseurs sont appelés nombres parfaits.

a = 6
b = 28
c = 496
d = 8128
e = 33550336
f  = 8589869056
g = 137438691328

Le plus grand commun diviseur   PGCD =  2
Le plus petit commun multiple     PPCM = 1,21993659586792E25

Les ensembles des diviseurs: 
T(a) = { 1 2 3 6 }
T(b) = { 1 2 4 7 14 28 }
T(c) = { 1 2 4 8 16 31 62 124 248 496 }
T(d) = { 1 2 4 8 16 32 64 127 254 508 1016 2032 4064 8128 }
T(e) = { 1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8191 16382 32764 65528 131056 262112 524224 ... }
T(f) =  { 1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131071 262142 524284 ... }
T(g) = { 1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 262144 524287 ... }

T(a) n T(b) n T(c) n T(d) n T(e) n T(f) n T(g) = { 1 2 }

Les sommes des diviseurs :  
σ(a) = 12                     σ*(a) = 6                           Entier parfait
σ(b) = 56                     σ*(b) = 28                         Entier parfait
σ(c) = 992                   σ*(c) = 496                       Entier parfait
σ(d) = 16256               σ*(d) = 8128                     Entier parfait
σ(e) = 67100672         σ*(e) = 33550336             Entier parfait
σ(f) =  17179738112    σ*(f) = 8589869056          Entier parfait
σ(g) = 274877382656  σ*(g) = 137438691328     Entier parfait

La première moitié de l'ensemble diviseur forme évidemment toujours la suite des puissances de 2.
(Voir aussi Décomposition en facteurs premiers)

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.

Euclide a utilisé le fait que le PGCD de deux nombres ne change pas lorsqu'on soustrait le plus petit du plus grand. Aujourd'hui, au lieu de l'algorithme de soustraction, on utilise généralement l'algorithme de division, plus rapide, dans lequel la différence entre les nombres est remplacée par le reste lors de la division entière.

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
Mentions légales fra.matheass.eu