Problem 927

Write $G=\operatorname{gcd}(a, b)+\operatorname{gcd}(b, c)+\operatorname{gcd}(c, a)$. Without loss of generality, we assume that $a \leq b \leq c$. Now, $\operatorname{gcd}(a, b) \leq a, \operatorname{gcd}(b, c) \leq b$ and $\operatorname{gcd}(c, a) \leq a$. Therefore,

$$G \leq a+b+a \leq a+b+c=5 n$$

If $3 \mid n$, then $G=5 n$ is achievable, namely with $a=b=c=\frac{5}{3} n$. All three gcds are then equal to $\frac{5}{3} n$, so $G=3 \cdot \frac{5}{3} n=5 n$.
Now suppose further that $3 \nmid n$. Then we know that $a, b$ and $c$ cannot all be equal. We distinguish several cases:

Case 1a: $b=c$ and $b \leq 2 n$. Since now $a \neq b$, we have $\operatorname{gcd}(a, b)=\operatorname{gcd}(a, b-a) \leq b-a$. Thus $G \leq(b-a)+b+a=2 b \leq 4 n$.

Case 1b: $b=c$ and $b>2 n$. We have $a+2 b=5 n$, so $a=5 n-2 b$, which implies that $G \leq a+b+a=10 n-4 b+b=10 n-3 b<10 n-6 n=4 n$.

Case 2a: $b \neq c$ and $c-a \geq n$. Now, $G \leq a+b+a=(a+b+c)-(c-a)=5 n-(c-a) \leq 5 n-n=4 n$.

Case 2b: $b \neq c$ and $c-a<n$. Since $a \leq b \leq c$, we also have $c-b<n$. Furthermore, $b \neq c$ and thus $a \neq c$. So $\operatorname{gcd}(c, a)=\operatorname{gcd}(c-a, a) \leq c-a<n$ and $\operatorname{gcd}(b, c)=\operatorname{gcd}(b, c-b) \leq c-b<n$. In addition, $a \leq \frac{5 n}{3}$. We conclude that $G<\frac{5 n}{3}+n+n<4 n$.

We see that in all cases $G \leq 4 n$. The value $G=4 n$ is achievable with $a=n, b=2 n$ and $c=2 n$, because then $\operatorname{gcd}(a, b)=\operatorname{gcd}(c, a)=n$ and $\operatorname{gcd}(b, c)=2 n$.
Thus, the maximum value of $G$ is $5 n$ if $3 \mid n$ and $4 n$ if $3 \nmid n$.