2021 Fall AMC 12B Problems/Problem 16

Problem

Suppose $a$ , $b$ , $c$ are positive integers such that $a+b+c=23$ and $\gcd(a,b)+\gcd(b,c)+\gcd(c,a)=9.$ What is the sum of all possible distinct values of $a^2+b^2+c^2$ ?

$(\textbf{A})\: 259\qquad(\textbf{B}) \: 438\qquad(\textbf{C}) \: 516\qquad(\textbf{D}) \: 625\qquad(\textbf{E}) \: 687$

Solution 1

Let $\gcd(a,b)=x$ , $\gcd(b,c)=y$ , $\gcd(c,a)=z$ . WLOG, let $x \le y \le z$ . We can split this off into cases:

$x=1,y=1,z=7$ : let $a=7A, c=7C,$ we can try all possibilities of $A$ and $C$ to find that $a=7, b=9, c=7$ is the only solution.

$x=1,y=2,z=6$ : No solutions. By $y$ and $z$ , we know that $a$ , $b$ , and $c$ have to all be divisible by $2$ . Therefore, $x$ cannot be equal to $1$ .

$x=1,y=3,z=5$ : C has to be both a multiple of $3$ and $5$ . Therefore, $c$ has to be a multiple of $15$ . The only solution for this is $a=5, b=3, c=15$ .

$x=1,y=4,z=4$ : No solutions. By $y$ and $z$ , we know that $a$ , $b$ , and $c$ have to all be divisible by $4$ . Therefore, $x$ cannot be equal to $1$ .

$x=2,y=2,z=5$ : No solutions. By $x$ and $y$ , we know that $a$ , $b$ , and $c$ have to all be divisible by $2$ . Therefore, $z$ cannot be equal to $5$ .

$x=2,y=3,z=4$ : No solutions. By $x$ and $z$ , we know that $a$ , $b$ , and $c$ have to all be divisible by $2$ . Therefore, $y$ cannot be equal to $3$ .

$x=3,y=3,z=3$ : No solutions. As $a$ , $b$ , and $c$ have to all be divisible by $3$ , $a+b+c$ has to be divisible by $3$ . This contradicts the sum $a+b+c=23$ .

Putting these solutions together, we have $(7^2+9^2+7^2)+(5^2+3^2+15^2)=179+259=\boxed{\textbf{(B) }438}$

-ConcaveTriangle

Solution 2

Because $a + b + c$ is odd, $a$ , $b$ , $c$ are either one odd and two evens or three odds.

$\textbf{Case 1}$ : $a$ , $b$ , $c$ have one odd and two evens.

Without loss of generality, we assume $a$ is odd and $b$ and $c$ are even.

Hence, ${\rm gcd} \left( a , b \right)$ and ${\rm gcd} \left( a , c \right)$ are odd, and ${\rm gcd} \left( b , c \right)$ is even. Hence, ${\rm gcd} \left( a , b \right) + {\rm gcd} \left( b , c \right) + {\rm gcd} \left( c , a \right)$ is even. This violates the condition given in the problem.