What is the relationship between GCD, LCM, and relatively prime numbers?

  • Thread starter Thread starter 1+1=1
  • Start date Start date
  • Tags Tags
    Gcd
1+1=1
Messages
93
Reaction score
0
Let a, b, and c be positive integers.

I need to prove two items...

1. abc = GCD(a,b,c) * LCM(ab,bc,ac)
2. abc = GCD(ab,ac,bc) * LCM(a,b,c)

where the GCD is the Greatest Common Divisor and the LCM is the Least Common Multiple.

Could I go ahead and say that (a,b,c)=1, that is relatively prime? Am I wrong in saying this part? If so, what could I say to make it right?
 
Physics news on Phys.org
1+1=1 said:
Let a, b, and c be positive integers.

Could I go ahead and say that (a,b,c)=1, that is relatively prime? Am I wrong in saying this part? If so, what could I say to make it right?

They have to be pairwise prime. We might have a case like (5,5,1) =1.
 
Look here:

http://mathworld.wolfram.com/LeastCommonMultiple.html

If we prime factorize a, b, and c as follows:

a = p_1^{a_1} \dots p_n^{a_n}

b = p_1^{b_1} \dots p_n^{b_n}

c = p_1^{c_1} \dots p_n^{c_n}

Where p_n is the greatest prime occurring in at least one of the prime factorizations of a, b, and c, and where a_i = 0 if p_i doesn't occur in the prime factorization of a (and similar things go for b and c), then:

LCM(ab, bc, ca) = \prod _{i = 1} ^n p_i^{\max \{a_i + b_i, b_i + c_i, c_i + a_i \}}

See the page on the same site about the GCD, and we can say:

GCD(a, b, c) = \prod _{i = 1} ^n p_i^{\min \{a_i, b_i, c_i \}}

Multiplying the two, we get:

\prod _{i = 1} ^n p_i^{\min \{a_i, b_i, c_i \} + \min \{a_i + b_i, b_i + c_i, c_i + a_i\}} = \prod _{i = 1} ^n p_i^{a_i + b_i + c_i} = abc

as required. Something similar can be done for the other proposition. I think, however, that you might want to prove that LCM and GCD can be expressed as such products (which I doubt will be too difficult).
 
Last edited:
Edited: to note that i just saw AGK did the exact same thing.

I need to prove two items...

1. abc = GCD(a,b,c) * LCM(ab,bc,ac)
2. abc = GCD(ab,ac,bc) * LCM(a,b,c)

where the GCD is the Greatest Common Divisor and the LCM is the Least Common Multiple.

let fp:N->Union(N,{0}) (N the set of natural numbers {1,2,...})
s.t. fp(n)=k=>k is the largest whole number for which p^k|n
we can assume p is prime though we need not

lemma:
fp(n)=fp(m) for all p in P (P the set of prime numbers)=> n=m
(proof obvious by unique prime factorization)

fp has some useful properties
fp(n*m)=fp(n)+fp(m)
fp(GCD(a(1),...,a(n))=min({fp(a(1),...,fp(a(n))})
fp(LCD(a(1),...,a(n))=max({fp(a(1),...,fp(a(n))})

so using this on (1)
fp(abc)=fp(a)+fp(b)+fp(c)
fp(GCD(a,b,c) * LCM(ab,bc,ac))=fp(GCD(a,b,c))+fp(LCM(ab,bc,ac))
=min({fp(a),fp(b),fp(c)})+max({fp(ab),fp(bc),fp(ac)}
=min({fp(a),fp(b),fp(c)})+max({fp(a)+fp(b),fp(b)+fp(c),fp(a)+fp(c)}
=min({fp(a),fp(b),fp(c)})+max({fp(a)+fp(b)+fp(c)-fp(c),fp(a)+fp(b)+fp(c)-fp(a),fp(a)+fp(b)+fp(c)-fp(b)}
=min({fp(a),fp(b),fp(c)})+max({fp(a)+fp(b)+fp(c)-fp(a),fp(a)+fp(b)+fp(c)-fp(b),fp(a)+fp(b)+fp(c)-fp(c)}
=min({fp(a),fp(b),fp(c)})+fp(a)+fp(b)+fp(c)-min({fp(a),fp(b),fp(c)}
fp(GCD(a,b,c) * LCM(ab,bc,ac))=fp(a)+fp(b)+fp(c)
thus
fp(abc)=fp(GCD(a,b,c) * LCM(ab,bc,ac))
p was arbitrary so
abc=GCD(a,b,c) * LCM(ab,bc,ac)

(2) can be do by the same method.
 
Last edited:
Back
Top