# Proving with GCD and LCM

1. Oct 27, 2004

### 1+1=1

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?

2. Oct 28, 2004

### robert Ihnot

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

3. Oct 28, 2004

### AKG

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 occuring 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: Oct 28, 2004
4. Nov 13, 2004

### lurflurf

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: Nov 13, 2004