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;