MatheAss 9.0 Algebra

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;

See also:

Wikipedia: Greatest common divisor
Imprint eng.matheass.eu