Prove that lcma b abgcda b for any positive integers a b wi

Prove that lcm(a, b) = ab/gcd(a, b) for any positive integers a, b without using prime factorization.

Solution

Let us assume that gcd of a and b is d . Then there exist some x and y which are coprime to each other such that a=dx and b=dy

Thus ab÷gcd(a,b) = (dx)(dy) ÷ d = dxy .

Thus now we just need to show that lcm of ab is dxy and we are done .

As it is obvious by the definition of lcm that dxy is a common multiple of a and b , we just need to prove that it is the least common multiple .

Let m be the multiple of a , then m=ka for some integer k

Thus m=kdx (by putting value of a) . But b divides m as m being the multiple .

Thus yd divides kdx and hence y divides kx .

But as x and y are coprime i.e their gcd is 1 , it implies y divides k .

And hence we have dxy is the least common multiple of a and b .

Thus lcm(a,b) = ab/gcd(a,b)