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;