MatheAss 10.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}

Example 3:

In addition, the sum of all divisors σ(n) and the sum of the proper divisors σ*(n) are determined.
Numbers that are equal to the sum of their proper divisors are called perfect numbers.

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

Greatest Common Factor      G.C.F. =  2
Least Common Multiple        L.C.M. = 1,21993659586792E25

Sets of divisors: 
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 }

Sums of divisors :  
σ(a) = 12                     σ*(a) = 6                           perfect number
σ(b) = 56                     σ*(b) = 28                         perfect number
σ(c) = 992                   σ*(c) = 496                       perfect number
σ(d) = 16256               σ*(d) = 8128                     perfect number
σ(e) = 67100672         σ*(e) = 33550336             perfect number
σ(f) =  17179738112    σ*(f) = 8589869056          perfect number
σ(g) = 274877382656  σ*(g) = 137438691328     perfect number

The first half of the divider set obviously always forms the sequence of the powers of 2.
(See also Prime Factorization)

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