# Thread: Proof: Formula connecting GCD and LCM for 3 integers

1. ## Proof: Formula connecting GCD and LCM for 3 integers

Hi, I need some help proving that the below formula is true.

It says: Use the Fundamental Theorem of Arithmetic to prove the following formula connecting GCD and LCM for three integers.

[a, b, c] = abc(a, b, c) / (b, c)(c, a)(a, b)

Now I know that FTA says that any integer has a unique decomposition of primes. And I know you can write any two integers as a decomposition of the same primes, with some powers that possibly equal 0.

Katy.

2. Originally Posted by harkapobi
Hi, I need some help proving that the below formula is true.

It says: Use the Fundamental Theorem of Arithmetic to prove the following formula connecting GCD and LCM for three integers.

[a, b, c] = abc(a, b, c) / (b, c)(c, a)(a, b)

Now I know that FTA says that any integer has a unique decomposition of primes. And I know you can write any two integers as a decomposition of the same primes, with some powers that possibly equal 0.

Katy.
If you are given prime factorization of a,b - would you know how to write GCD, LCM from the prime factorization?
This equations seems like a direct application of that concept.

Best is to take specific numbers and try it out to get a feel. Then you can generalize.

3. Yes, to write the GCD and LCM using prime factorisations;

if a = ( $p_1$^ $n_1$)( $p_2$^ $n_2$).....( $p_s$^ $n_s$)
and
b = ( $p_1$^ $m_1$)( $p_2$^ $m_2$).....( $p_s$^ $m_s$)

Then LCM[a,b] = ( $p_1$^ $t_1$)( $p_2$^ $t_2$).....( $p_s$^ $t_s$)

Where $t_i$ = max{ $n_i$, $m_i$}

Is that right? And similar for GCD but with min instead of max. I've tried writing all this down on paper and I still can't see how it helps me prove the formula.

4. Originally Posted by harkapobi
Yes, to write the GCD and LCM using prime factorisations;

if a = ( $p_1$^ $n_1$)( $p_2$^ $n_2$).....( $p_s$^ $n_s$)
and
b = ( $p_1$^ $m_1$)( $p_2$^ $m_2$).....( $p_s$^ $m_s$)

Then LCM[a,b] = ( $p_1$^ $t_1$)( $p_2$^ $t_2$).....( $p_s$^ $t_s$)

Where $t_i$ = max{ $n_i$, $m_i$}

Is that right? And similar for GCD but with min instead of max. I've tried writing all this down on paper and I still can't see how it helps me prove the formula.
I have not tried it myself. First check of the equation actually is true. Take any 3 numbers and do a quick check.

If it does, to prove, argue as follows
Consider any prime p
power of p in a,b,c be n1,n2,n3
consider three cases
- all three n1,n2,n3 differed, assume n1>n2>n3 (without loss of generality)
- 2 of n1,n2,n3 same. Then either n1=n2>n3 or n1=n2<n3
- all 3 same

for each of the cases above show the power of p in LHS and RHS is same
as p is any prime hence equality holds

most probably it should work
thanks

5. So a=p^n1, b=p^n2 and c=p^n3?

I see how to prove these work in the formula. Is substituting these into the formula for all 3 cases enough to prove that it works? Does this cover the cases where a,b or c are composed of more than one prime?

6. Originally Posted by harkapobi
So a=p^n1, b=p^n2 and c=p^n3?

I see how to prove these work in the formula. Is substituting these into the formula for all 3 cases enough to prove that it works? Does this cover the cases where a,b or c are composed of more than one prime?
Note we have proved for 'any' prime not a specific prime. Combined with Fundamental Theorem of Arithmetic, it is sufficient.

I checked - the above logic works and is a valid proof. Why do you doubt?

7. Ok, thanks for your help

I just like to be sure that I've done enough to prove it. I just have difficulty getting my head around these proofs

8. Originally Posted by harkapobi
Hi, I need some help proving that the below formula is true.

It says: Use the Fundamental Theorem of Arithmetic to prove the following formula connecting GCD and LCM for three integers.

[a, b, c] = abc(a, b, c) / (b, c)(c, a)(a, b)

Now I know that FTA says that any integer has a unique decomposition of primes. And I know you can write any two integers as a decomposition of the same primes, with some powers that possibly equal 0.

Katy.

it is long

let

r = the product of the similar primes from a,b,c and this equal =(a,b,c)

n = the product of the similar primes from a,b except r =(a,b)/r

m = the product of the similar primes from b,c except r =(b,c)/r

o = the product of the similar primes from a,c except r =(a,c)/r

[a,b] = ab/(a,b)

we can say that :

x= the product of the primes of a without n(o)r = a/n(o)r

y= the product of the primes of b without n(m)r = b/n(m)r

u = the product of the primes of c without m(o)r = c/m(o)r

[a,b,c] = the product of the all primes in a,b,c but without taking the similar primes twice

[a,b,c] = rmnoxyu sub the x,y,u values

$[a,b,c] =r\cdot n\cdot m\cdot o \frac{a}{nor}\cdot \frac{b}{nmr}\cdot \frac{c}{mor}$

$[a,b,c] = r\cdot \frac{a}{nr} \cdot \frac{b}{mr} \cdot \frac{c}{or}$

but from above nr=(a,b) mr=(b,c) or=(a,c) so

$[a,b,c] = \frac{r \cdot a \cdot b \cdot c}{(a,b)(b,c)(a,c)}$

$[a,b,c] = \frac{(a,b,c)abc}{(a,b)(b,c)(a,c)}$

I wish it is clear

I made a picture it present a,b,c like a set the intersection between a and b present the similar primes of a,b

and I made a name for every part in the pic and [a,b,c] is the whole picture (i.e the product of all parts in the picture)

it is like the union and intersection of sets but here present the product of the similar primes of the two sets

9. wow, thats difficult to get my head around. The picture helps tho Thanks.

But I dont understand why [a, b, c] = rmnoxyu ? I get lost somewhere at that point.

10. ok

[a,b,c] how you can find it for example let

$a=p^4\times q^5\times g^2\times h^2$

$b=p^3\times q^8 \times g^3\times k$

$c=p^2\times q^4 \times g^4 \times k^2 \times l$

$[a,b,c] = p^4 \times q^8 \times g^4 \times k^2 \times h^2 \times l$

p,q,g,h,l is prime numbers

to find [a,b,c] what I do is let

r = similar primes from a,b,c = $p^2 \times q^4 \times g^2$

n = similar primes from a,b but without the r = $p \times q$

m= similar primes from b,c without r = g (k)

o = similar primes from a,c without r = 1

x = a/nor = $p \times h^2$

y= b/nmr = $q^3$

u= c/mor = $g^3 \times k \times l$

the product of rmnoxyu is [a,b,c]

what I did was covering all the possibilities for the primes and I avoid to repeat anyone of them

this idea came to my head from the picture that I painted it is like sets
but here the union of two sets (consider a,b,c sets containing prime number ) for example

a union b = [a,b] = ab/(a,b) but in sets (a union b = a+b - a intersect b)

(a,b) is the intersection

and

a union b union c = [a,b,c] since it contains all the primes without taking the same prime from two different set more than once

is there anything is not clear

Remark: in sets element repeated is not allowed but here there is a repeated elements

11. No, thats fantastic. The example made it much clearer. Thank you very much for your help

12. Originally Posted by harkapobi
No, thats fantastic. The example made it much clearer. Thank you very much for your help

That gives me great pleasure . . .