# Number Theory GCD/LCM Problem

The following is from a problem set:

Let $a,b,c$ be three positive integers such that $$\text{lcm}(a,b) \cdot \text{lcm}(b,c) \cdot \text{lcm}(c,a) = a \cdot b \cdot c \cdot \gcd(a,b,c).$$ Given that none of $a,b,c$ is an integer multiple of any other of $a,b,c$, find the minimum possible value of $a+b+c$.

I turned this into

$$abc=\text{gcd}(a,b,c) \cdot \text{gcd}(a,b) \cdot \text{gcd}(b,c)\cdot\text{gcd}(c,a)$$

and I don't know where to go from here. Can anyone walk me through this problem? Thanks.

Rewriting the LCMs as GCDs is a good first step. We finish by removing these GCD constraints. Define $k_0 = \gcd(a,b,c)$. Then we can write $a=k_0a'$, $b=k_0b'$, and $c=k_0c'$ for integers $a'$, $b'$, and $c'$. Substituting and cancelling factors of $k_0$ gives us $$a'b'c'=k_0\gcd(a',b')\gcd(b',c')\gcd(c',a').$$ Now let $k_1=\gcd(a',b')$, $k_2=\gcd(b',c')$ and $k_3=\gcd(c',a')$. We can write $a'=a''k_1k_3$, $b'=b''k_1k_2$ and $c'=c''k_2k_3$, since $\gcd(a',b',c')=1$. (Note that $a''$, $b''$, and $c''$ are integers.) Substituting and cancelling again, we have $$k_1k_2k_3a''b''c''=k_0,$$

where $a''$, $b''$, and $c''$ are pairwise coprime. Assume without loss of generality that $a''\le b''\le c''$.

Case 1: $a''\neq 1$

We then have $a''\ge 2$, $b''\ge 3$, and $c''\ge 5$. Furthermore, our answer is monotonically increasing in each of the $k_i$. Thus we obtain our minimal solution when we set $a''=2$, $b''=3$, $c''=5$, and all the $k_i=1$: $$a+b+c = k_0(k_1k_3a'' + k_1k_2b'' + k_2k_3c'') = 300.$$

Case 2: $a''=1$. Then $b''\ge 2$, $c''\ge 3$. Because none of $a,b,c$ divide each other, $k_1,k_3\ge 2$. Plugging in these inequalities, we have: $$a + b + c\ge 336.$$

Thus the first case gives $300$ as our answer.

Hint: Let $x,y,z$ be real numbers. Then, $$\max\{y,z\}+\max\{z,x\}+\max\{x,y\}=x+y+z+\min\{x,y,z\}$$ if and only if $$\max\{x,y,z\}=2\,\min\{x,y,z\}\,.$$ The answer is $60+90+150=300$.

Hint $\$ By the first equation here, your second equation is equivalent to

$${\rm lcm}(a,b,c)\, =\, \gcd(a,b,c)^2$$