Prove: The LCM of two integers a and b equals ab divided by the GCF of a and b?

Question

please provide a written proof explaining how the statement is true.. not a numerical proof or induction. thanks!!

Answer 1

if integer a has factors c d e
and integer b has factors c r e then:
LCM a&b = cder
ab = cde * cre
GCF = ce

take a*b/ GCF a&b=
cde * cre / ce = cder
and this result matches the LCM above.

Answer 2

GCF (A,B) = F So, write A = A' F and B=B' F where
A' and B' have only the common factor 1. Now you can prove
your result :

AB = ( A' F)(B ' F) = ( A' B' F) F = LCM(A,B) GCF(A,B).

Therefore, LCM (A,B) = (AB) / GCF(A,B) as required.

Answer 3

Suppose c is a common multiple of a and b. By the fundamental theorem of arithmetic, a, b, and c have prime factorizations. Thus, for a to divide c, every prime factor of a must be a prime factor of c, and likewise for b to divide c, every prime factor of b must be a prime factor of c. Thus, if c is the least common multiple of a and b, its prime factorization must be the smallest multiset of primes that contains the prime factorizations of a and b. Now, if a = p_1*p_2... p_n and b=q_1*q_2... q_m have no prime factors in common, then the smallest prime factorization that contains all the primes from both is simply p_1*p_2... p_n*q_1*q_2... q_m, which when multiplied out is simply a*b. However, suppose that a and b have some prime factors in common, say, r_1, r_2... r_k. Then each of the r_i will be listed twice in a*b, so to obtain the smallest factorization, the redundant elements must be removed by dividing them out. Thus, LCM(a, b) = p_1*p_2... p_n*q_1*q_2... q_m / (r_1*r_2...r_k) = a*b/(r_1*r_2...r_k) , where r_1, r_2... r_k are the prime factors that a and b have in common. Now, since all the primes r_1, r_2... r_k are in the prime factorization of a, (r_1*r_2...r_k) divides a and likewise it divides b. Further, since the prime factorization of any other common divisor must consist only of those prime factors a and b have in common, it must be a subset of the r_i, and thus any other common divisor of a and b must divide (r_1*r_2...r_k). It follows that (r_1*r_2...r_k) is the greatest common divisor of a and b, so we have that LCM (a, b) = a*b/(r_1*r_2...r_k) = a*b/GCD(a, b). Q.E.D.

Answer 4

It is suffidient to show that the prime decompositions are the same. Write out the general form of a prime decomposition for each of a and b eg a=p1^n1*p2^n2...... and b =p1^m1*p2^m2......

The LCM=p1^max(n1,m1)*p2^(max(n2.m2)...
The GCD=p1^min(n1,m1)*p2^min(n2,m2)...

ab/GCF=p1^(n1+m1-min(n1,m1))*p2^(n2+m2-min(n2,m2)...

For each of these powers, you will subtract the smaller of the m,n terms which will leave the max of the two terms. This leaves the prime decomposition of the LCM as required.

You can tidy this up by writing each prime decomposition as an infinite sum i.e. sum from i=1 to infinity of pi^ni.