# GCD and LCM using Prime Factorization

I saw in a book that we can find the LCM and GCD of three numbers using prime factorization . That was really cool :) I'll explain what i saw and will let you know my doubt in the end!

Three numbers 12,15,18

LCM = Highest power of the all the factors

GCD = Lowest power of the shared factor

12 can be prime factorized as 3 * 2^2

15 can be prime factorized as 3 * 5

21 can be prime factorized as 2 * 3^2

So GCD =3 since that is the only number common in three number factorizations.

LCM = 2^2 * 3 * 5 = 60

And the answer looks good !!

My doubt is how this gives the correct answer(proof of correctness) ?

I am expecting a simple explanation with example so that i can understand easily :)

Just note that you can check if a number divides the other by comparing the prime exponents: If and only all exponents in $a$ are $\le$ the corresponding exponent in $b$, then $a$ divides $b$. As a consequence, the GCD as produced above by combining the minimal prime exponents is both a divisor of all (because the minimum is always $\le$ any of its constituents) and is the greatest possible (because increasing any exponent would break the divisor property for atleast one of the arguments).

The argument for the lcm is dual to this.

LCM take highest exponent of prim factors in above case it is 3^2 × 2^2 × 5^1 = 9 × 4 × 5 = 180

and not 60 as you have shown

see if this helps you LCM = GCD × product of un common factors

factorization using combined method

2]12 15 18

3]06 15 09

1]02 05 03

after this there is no common divisor, 2, 5, 3 are un common factors

so GCD = 2 × 3 = 6 uncommon factors = 2 × 5 × 3 = 30

and LCM = GCD × product of un common factors

LCM = 6 × 30 = 180