G.C.F. and L.C.M.

The program determines for two or more numbers the greatest common factor ( G.C.F. ), the lowest common multiple ( L.C.M. ) and their respective set of divisors.

The G.C.F. is the biggest 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 biggest number by which the fraction may 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)


a = 24
b = 256

Greatest Common Factor      G.C.F. = 8
Least Common Multiple       L.C.M. = 768

Sets of factors :
T(a) = { 1 2 3 4 6 8 12 24}
T(b) = { 1 2 4 8 16 32 64 128 256}


The greatest common factor of two numbers can be determined out of their prime factorizations. If the numbers are too big the Algorithm of Euclid gives a solution.

After Euclid the G.C.F. did not change if you subtract the smaller number from the greater one. Nowadays its usual to divide instead of subtract and substitute the difference of the two numbers by the remainder of their quotient.

Algorithm of Euclid in PASCAL:

function GreatestCommonFactor(a,b:integer):integer;
    r: integer;		
      r := a mod b;
      a := b;
      b := r;
    until r=0;
    result := a;

See also:

Wikipedia: Greatest common divisor