5
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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$.

$\endgroup$
1
$\begingroup$

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

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.