G.C.F. and L.C.M.
The program determines for two or more positive integers the greatest common factor ( G.C.F. ), the least 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 greatest factor 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)
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 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;
var
r: integer;
begin
repeat
r := a mod b;
a := b;
b := r;
until r=0;
result := a;
end;