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}
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;