2
$\begingroup$

Let $a$, $b$, $c$ be three positive integers such that $$\mathrm{lcm}(a,b)\cdot\mathrm{lcm}(b,c)\cdot\mathrm{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$.

So, I was able to find that $ \gcd(a,b)\cdot\gcd(b,c)\cdot\gcd(a,c)\cdot\gcd(a,b,c)=abc $ but I wasn't quite sure how to continue on. Some help would be great. Thanks!

$\endgroup$
1
$\begingroup$

Let's suppose we have

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

and look at a prime $p$ dividing at least one of $a,b,c$.

Suppose $p$ divides at most two of the three, say $p\nmid c$, and $a = p^\alpha\cdot a'$, $b = p^\beta\cdot b'$ with $p\nmid a'b'$. Then on the left hand side, $p$ does only occur in $\gcd(a,b)$, with exponent $\min\{\alpha,\beta\}$. But on the right hand side, it occurs with exponent $\alpha+\beta = \min\{\alpha,\beta\} + \max\{\alpha,\beta\}$, and since the exponents must be equal, it follows that $\max\{\alpha,\beta\} = 0$, contradicting the assumption that $p$ divides at least one of $a,b,c$.

So every prime dividing at least one of $a,b,c$ must divide all three. Let the exponents of $p$ be $\alpha \leqslant \beta \leqslant \gamma$. Then on the left hand side, $p$ occurs with the exponent

$$\alpha + \beta + \alpha + \alpha = 3\alpha + \beta,$$

and on the right it occurs with the exponent $\alpha + \beta + \gamma$. It follows that $\gamma = 2\alpha$.

Furthermore, the condition that none of $a,b,c$ shall be an integer multiple of any other implies that for each pair $(x,y)$ of two of the numbers, there is at least one prime $p_{xy}$ that occurs with a larger exponent in the prime factorisation of $x$ than it occurs in the prime factorisation of $y$.

Any prime that is not one of the $p_{xy}$ can be removed from all of $a,b,c$, and leads to a solution with smaller numbers, and smaller $a+b+c$, so the primes involved in the minimal solution are precisely the

$$\{p_{ab},p_{ac},p_{ba},p_{bc},p_{ca},p_{cb}\}.$$

That set must contain at least two primes, and it contains at most six. It is clear that for the minimal solution, the set must contain the $k$ smallest primes, $2 \leqslant k \leqslant 6$.

Finding the minimal solution is then a small amount of work even brute-forcing.

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