21
$\begingroup$

If I know the GCD of 20 numbers, and know the 20 numbers, is there a formula such that I input the 20 numbers and input their GCD, and it outputs their LCM? I know that $$\frac{\left| a\cdot b\right|}{\gcd(a,b)} = \text{lcm}(a,b).$$ So is it$$\frac{\left| a\cdot b\cdot c\cdot d\cdot e\cdot f\right|}{\gcd(a,b,c,d,e,f)}?$$If not, what is it?

$\endgroup$

8 Answers 8

28
$\begingroup$

There can be no formula that computes $\text{lcm}(a,b,c)$ using only the values of $abc$ and $\gcd(a,b,c)$ as input: that's because $(a,b,c) = (1,2,2)$ and $(a,b,c) = (1,1,4)$ both have $abc=4$, $\gcd(a,b,c)=1$, but they don't have the same lcm.

However, there is a straightforward generalization of the $2$-variable formula. For instance, $$\text{lcm}(a,b,c,d) = \frac{abcd}{\gcd(abc,abd,acd,bcd)}.$$

The correct gcd to take is not of the individual terms $a,b,c,d$ but the products of all the complementary terms (which looks the same in the two-variable case).

$\endgroup$
1
  • 1
    $\begingroup$ See my answer for a simple proof. $\endgroup$
    – Math Gems
    Mar 3, 2013 at 18:56
24
$\begingroup$

As mentioned, it does not generalize like that. But there do exist generalizations. For example, using the standard gcd notation $\rm\ (x,y,\ldots)\, :=\, gcd(x,y,\ldots),\:$ we have

Theorem $\rm\ \ lcm(a,b,c)\, =\, \dfrac{abc}{(bc,ca,ab)}$

$\!\begin{align}{\bf Proof}\qquad\qquad\rm\ a,b,c&\mid\rm\ n\\ \iff\quad\rm abc&\mid \rm\,\ nbc,nca,nab\\ \iff\quad\rm abc&\mid \rm (nbc,nca,nab)\, =\, n(bc,ca,ab)\\ \iff\rm \ \dfrac{abc}{(bc,ca,ab)} &\:\Bigg| \rm\,\ n\end{align}$

Hence the claimed equality follows by the (universal) definition of lcm. $\ \ $ QED

Remark $\ $ The penultimate equivalence in the proof uses said (universal) definition of gcd, followed by the gcd distributive law. An analogous proof works for any number of arguments.

$\endgroup$
2
  • $\begingroup$ This was fine as posted: $(a,b,c)$ is a standard notation for the greatest common divisor of $a,b$, and $c$. $\endgroup$ Mar 3, 2013 at 19:03
  • $\begingroup$ You just proved that $\frac{abc}{(ab,bc,ca)}|n$. How does that prove that $\frac{abc}{(ab,bc,ca)}=\text{lcm}(a,b,c)$? $\endgroup$
    – Confuse
    Aug 14, 2016 at 11:35
15
$\begingroup$

$$\operatorname{lcm}(a,b)=\frac{a\cdot b}{\operatorname{gcd}(a,b)};$$ $$\operatorname{lcm}(a,b,c)=\frac{a\cdot b\cdot c\cdot \operatorname{gcd}(a,b,c)}{\operatorname{gcd}(a,b)\cdot \operatorname{gcd}(a,c)\cdot \operatorname{gcd}(b,c)};$$ $$\operatorname{lcm}(a,b,c,d)=\frac{a\cdot b\cdot c\cdot d\cdot\operatorname{gcd}(a,b,c)\cdot\operatorname{gcd}(a,b,d)\cdot\operatorname{gcd}(a,c,d)\cdot\operatorname{gcd}(b,c,d)}{\operatorname{gcd}(a,b)\cdot\operatorname{gcd}(a,c)\cdot\operatorname{gcd}(a,d)\cdot\operatorname{gcd}(b,c)\cdot\operatorname{gcd}(b,d)\cdot\operatorname{gcd}(c,d)\cdot\operatorname{gcd}(a,b,c,d)};$$ etc. This is because $$\max(a,b)=a+b-\min(a,b);$$ $$\max(a,b,c)=a+b+c-\min(a,b)-\min(a,c)-\min(b,c)+\min(a,b,c);$$ $$\max(a,b,c,d)=a+b+c+d-\min(a,b)-\min(a,c)-\min(a,d)-\min(b,c)-\min(b,d)-\min(c,d)+\min(a,b,c)+\min(a,b,d)+\min(a,c,d)+\min(b,c,d)-\min(a,b,c,d);$$ etc. This is the "in-and-out" principle, aka "The Principle of Inclusion and Exclusion".

$\endgroup$
3
$\begingroup$

It certainly doesn't work like that. Consider that $\gcd(1, 2, 2) = 1$, $\text{lcm}(1, 2, 2) = 2$ and $1 \times 2 \times 2 = 4$.

A good way to think of this is to consider a natural number $n$ as a vector which has $x$ for $i$th component if $x$ is the largest power of $i$th prime, dividing $n$. For example, $50 = 2\times 5^2$ would be $(1, 0, 2, 0, 0 \dots)$. Then $\gcd$ is a componentwise $\min$, $\text{lcm}$ is a componentwise $\max$ and $\times$ is a componentwise $+$. It just so happens that for two numbers, $\min(a, b) + \max(a, b) = a+b$. Same is not true for three or more numbers.

Using the same interpretation, you can construct many other similar formulas though. For example, $\text{lcm}(a, b, c, \dots) = \text{lcm}(a, \text{lcm}(b, \text{lcm}(c, \dots)))$.

$\endgroup$
0
$\begingroup$

If you are asking whether the identity $\dfrac{|a_1a_2\cdots a_n|}{\gcd(a_1,a_2,\ldots,a_n)}=\text{lcm}(a_1,a_2,\ldots,a_n)$ is true for $n>2$ then the answer is no.
Take for example $n=3, a_1=2, a_2=4,a_3=3$.

$\endgroup$
0
$\begingroup$

$LCM(a,b,c,d, \dots)$ depends on the prime factors of each of $a,b,c,d, \dots$ You can't determine that from $abcd\dots$ and $GCD(a,b,c,d \dots)$.

Example:
$a,b,c=(p_1p_2),(p_1p_3),(p_1p_2p_3) abc=(p_1^3)(p_2^2)(p_3^2), GCD=p_1, LCM=(p_1)(p_2)(p_3)$

$a,b,c=(p+1),(p_1p_2),(p_1p_2p_3^2) abc=(p_1^3)(p_2^2)(p_3^2), GCD=p_1, LCM=(p_1)(p_2)(p_3^2)$

$p_1$, $p_2$, $p_3$, $\dots$ are prime

$\endgroup$
1
  • $\begingroup$ This doesn't appear the way I typed it, which was clearer. Don't know how to correct it. $\endgroup$
    – hartlw
    Apr 3, 2015 at 5:40
-1
$\begingroup$

LCM can be calculated using:
$\text{GCD}(a,b)\cdot \text{LCM}(a,b)=ab$ and
$\text{LCM}(a,b,c,d,...n)=\text{LCM}(\text{LCM}(a,b),c,d,...,n)$

Example
$\text{LCM}(2,4,5,7)=\text{LCM}(4,5,7)=\text{LCM}(20,7)=140$

or more concisely $$ \begin{align} 2&,4,5,7 \\ 4&,5,7 \\ 20&,7 \\ 140& \end{align} $$

http://mathhelpforum.com/peer-math-review/229498-lcm-b-c-abc.html

$\endgroup$
2
  • $\begingroup$ LCM(a,b,c,d...)=LCM(LCM(a,b),c,d,...) $\endgroup$
    – hartlw
    Apr 2, 2015 at 17:57
  • $\begingroup$ The previous comment is incomplete because as soon as I hit enter to start a new line my comment is submitted, incomplete. $\endgroup$
    – hartlw
    Apr 2, 2015 at 18:07
-1
$\begingroup$

LCM(a,b,c,d,...)=LCM(LCM(a,b),c,d,..)

Proof. Every CM of a,b,c,d,.. is a CM of LCM(a,b),c,d,.. and every CM of LCM(a,b),c,d,.. is a CM of a,b,c,d,..

The same proof holds for any grouping like LCM(a,b,c,d,e)=LCM(LCM(a,b,c),LCM(d,e)).

Examples: LCM(a,b,c,d)=LCM(e,f)
e=LCM(a,b), f=LCM(c,d), and LCM(e,f)=ef/GCD(e,f)

LCM(2,4,5,7)=LCM(4,5,7)=LCM(20,7)=140

LCM(a,b,c,d)=LCM(LCM(a,b,c),d)
LCM(a,b,c)=LCM(LCM(a,b),c)
If you substitute you get
LCM(a,b,c,d)=LCM(LCM(LCM(a,b),c),d) given in calculatorsoup.com, in case you were wondering.

$\endgroup$
1
  • $\begingroup$ This doesn’t really answer the question. $\endgroup$
    – Erick Wong
    Mar 24, 2021 at 20:35

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .