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.
How can I use this to prove the formula? Please help.
Katy.
Yes, to write the GCD and LCM using prime factorisations;
if a = ( ^ )( ^ ).....( ^ )
and
b = ( ^ )( ^ ).....( ^ )
Then LCM[a,b] = ( ^ )( ^ ).....( ^ )
Where = max{ , }
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
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
but from above nr=(a,b) mr=(b,c) or=(a,c) so
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
ok
[a,b,c] how you can find it for example let
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 =
n = similar primes from a,b but without the r =
m= similar primes from b,c without r = g (k)
o = similar primes from a,c without r = 1
x = a/nor =
y= b/nmr =
u= c/mor =
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