Let $M \geq 1$ be a real number. Determine all natural numbers $n$ for which there exist distinct natural numbers $a$, $b$, $c > M$, such that $n = (a,b) \cdot (b,c) + (b,c) \cdot (c,a) + (c,a) \cdot (a,b)$ (where $(x,y)$ denotes the greatest common divisor of natural numbers $x$ and $y$).
Problem
Source: Romania JBMO tst 2023 day2 p4
Tags: number theory
30.04.2023 13:17
Call such a positive integer $n$ good. I claim that the good positive integers $n$ are only the ones such that $v_2(n)$ is even and $n$ is not a power of $4$ (including $1$). Let $K=\gcd(a,b)\gcd(b,c)+\gcd(b,c)\gcd(c,a)+\gcd(c,a)\gcd(a,b)$. We have the following 2 crucial Claims: Claim 1: $n$ is good if and only if $4n$ is. Proof: If $n$ is good, then we infer that $4n$ is, too, by taking $(2a,2b,2c)$ instead of $(a,b,c)$. Now, if $4n$ is good, then we claim that $a,b,c$ are all even. If $a,b,c$ are all odd, then $K$ is odd, absurd. Now, if $a$ is odd and $b,c$ are even, then all $\gcd$'s are odd and so $K$ is odd, absurd. Lastly, if $a,b$ are even and $c$ is odd, then $K$ is again odd, absurd. Thus, all $a,b,c$ must be even, as desired. Hence, we have a representation of $n$ in the desired form, although we don't know whether $\dfrac{a}{2},\dfrac{b}{2},\dfrac{c}{2}$ are greater than $M$. This is easily resolved, though, by multiplying these numbers by $p_1,p_2,p_3$ with the $p_i$ being sufficiently large primes so that the new numbers are $>M$, and such that the $p_i$ do not divide any of $a,b,c$, so that the $\gcd$'s remain the same. $\blacksquare$ Claim 2: If $n \equiv 2 \pmod 4$, then $n$ is not good. Proof: Assume it is, and prove that $a,b,c$ must all be even (and so $n$ is a multiple of $4$, absurd), replicating the corresponding part of Claim 1 $\blacksquare$ Now, if $n$ is such that $v_2(n)$ is odd then if $v_2(n)=1$ we have a contradiction by Claim 1, and if $v_2(n) \geq 3$ then using Claim 1 we may assume that $v_2(n)=1$, and we again obtain a contradiction. Furthermore, if $n=4$ is good, then by Claim 1 $n=1$ is good, a contradiction. On the other hand, assume that $v_2(n)$ is even and $n$ is not a power of $4$. Then, if $v_2(n)=0$ that is $n$ is odd, then we may use the following construction: take $a=nk, b=n(k+1),c=p$ with $k>M$ and $p$ a prime such that $p>n(k+1)$. Then $\gcd(a,c)=\gcd(b,c)=1$ and $\gcd(a,b)=n$, and so $\gcd(a,b)\gcd(b,c)+\gcd(b,c)\gcd(c,a)+\gcd(c,a)\gcd(a,b)=n+1+n=2n+1$. Now, if $v_2(n) \geq 2$, by Claim 1 we may assume that $v_2(n)=0$, that is $n$ is odd, and since $n$ is not a power of $4$ we may assume that $n \neq 1$, and so we return to the previous case. To sum up, the good numbers are only these such that $v_2(n)$ is even, and $n$ is not a power of $4$ (including $1$).