G.C.F. and L.C.M.
For two or more positive integers the program determines the greatest common factor ( G.C.F. ), the least common multiple ( L.C.M. ) and their respective sets of divisors.
The G.C.F. is the largest element in the intersection of the set of divisors of a and b. In fractional arithmetic the G.C.F. of the numerator and of the denominator is the largest factor by which the fraction can be reduced.
The L.C.M. is the smallest element in the intersection of the set of multiples of a and b. In fractional arithmetic the L.C.M. of two denominators is called the least common denominator (L.C.D.).
If you have already determined the G.C.F.(a,b), the L.C.M.(a,b) is determined by the formula
L.C.M.(a,b) = a·b / G.C.F.(a,b)
Example 1:
a = 24 b = 256 Greatest Common Factor G.C.F. = 8 Least Common Multiple L.C.M. = 768 Sets of divisors: 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}
Example 2:
a = 195 b = 234 c = 273 Greatest Common Factor G.C.F. = 39 Least Common Multiple L.C.M. = 8190 Sets of divisors: 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)
Method
The greatest common factor of two numbers can be determined from their prime factorizations. However, if the prime factorization is difficult to determine for large numbers, the algorithm named after Euclid can help.
According to Euclid the G.C.F. does not change if you subtract the smaller number from the larger one. Nowadays its common to divide instead of subtracting and replace the difference of two numbers by the remainder of their quotient.
Euclid's algorithm in PASCAL:
function GreatestCommonFactor(a,b:integer):integer; var r: integer; begin repeat r := a mod b; a := b; b := r; until r=0; result := a; end;