Assuming that the prime factorisations of \(l\) and \(m\) are as follow,

\[l=2^{a_1}\times3^{a_2}\times...\times P^{a_n}\]

\[m=2^{b_1}\times3^{b_2}\times...\times P^{b_n}\]

where \(\left \{ a_n \right \}\in \mathbb{N}\cup \left \{ 0 \right \}\), \(\left \{ b_n \right \}\in \mathbb{N}\cup \left \{ 0 \right \}\) and \(P\) is a prime.

WLOG, assuming that \(a_1\leq b_1, a_2\leq b_2,...,a_n\leq b_n\),

The \(\operatorname{lcm}(l,m)\) can be obtained by choosing the highest power of each prime factor from either of the numbers.
\[\operatorname{lcm} (l,m)=2^{b_1}\times 3^{b_2}\times...P^{b_n}\]

On the other hand, the \(\gcd (l,m)\) is obtained by choosing the smallest power of each prime factor from either of the numbers.

I may have made some mistakes in my proof. Please do correct me if you spotted any.
–
Ho Wei Haw
·
3 years, 11 months ago

Log in to reply

You can refer to the GCD/LCM writeup in the Olympiad section.

This is a basic interesting fact which relates these two.

Is there a similar equation for the three variable case? Why, or why not?
–
Calvin Lin
Staff
·
3 years, 11 months ago

Log in to reply

See http://www.proofwiki.org/wiki/ProductofGCDandLCM for a much neater, albeit trickier, proof of the above.
–
Siddharth Prasad
·
3 years, 11 months ago

## Comments

Sort by:

TopNewestAssuming that the prime factorisations of \(l\) and \(m\) are as follow,

\[l=2^{a_1}\times3^{a_2}\times...\times P^{a_n}\]

\[m=2^{b_1}\times3^{b_2}\times...\times P^{b_n}\]

where \(\left \{ a_n \right \}\in \mathbb{N}\cup \left \{ 0 \right \}\), \(\left \{ b_n \right \}\in \mathbb{N}\cup \left \{ 0 \right \}\) and \(P\) is a prime.

WLOG, assuming that \(a_1\leq b_1, a_2\leq b_2,...,a_n\leq b_n\),

The \(\operatorname{lcm}(l,m)\) can be obtained by choosing the highest power of each prime factor from either of the numbers. \[\operatorname{lcm} (l,m)=2^{b_1}\times 3^{b_2}\times...P^{b_n}\]

On the other hand, the \(\gcd (l,m)\) is obtained by choosing the smallest power of each prime factor from either of the numbers.

\[\gcd (l,m)=2^{a_1}\times3^{a_2}\times...\times P^{a_n}\]

Notice that

\[\gcd (l,m)\times \operatorname {lcm}(l,m)= 2^{a_1+b_1}\times 3^{a_2+b_2}\times ... \times P^{a_n+b_n}\]

which is equivalent to

\[l \times m=2^{a_1+b_1}\times 3^{a_2+b_2}\times...\times P^{a_n+b_n}\]

\[\therefore\gcd(l,m)\times \operatorname {lcm}(l,m)=l\times m\]

I may have made some mistakes in my proof. Please do correct me if you spotted any. – Ho Wei Haw · 3 years, 11 months ago

Log in to reply

You can refer to the GCD/LCM writeup in the Olympiad section.

This is a basic interesting fact which relates these two.

Is there a similar equation for the three variable case? Why, or why not? – Calvin Lin Staff · 3 years, 11 months ago

Log in to reply

See http://www.proofwiki.org/wiki/Product

ofGCDandLCM for a much neater, albeit trickier, proof of the above. – Siddharth Prasad · 3 years, 11 months agoLog in to reply