2021 AMC 12B Fall Problem 16

Question

Suppose

a,

b,

c

are positive integers such that

a + b + c = 23

and

\begin{aligned} &\gcd(a, b) + \gcd(b, c) \\ &\quad {}+ \gcd(c, a) = 9. \end{aligned}

What is the sum of all possible distinct values of

a^2 + b^2 + c^2?

259

438

516

625

687

By symmetry assume

a\le b\le c;

then

a\le7

and

c=23-a-b

Use

\gcd(b,c)=\gcd(b,23-a)

and check the short range

a\le b\le\frac{23-a}{2}

The condition is symmetric, so assume

a\le b\le c.

Then

a\le7,

and for each fixed

a

we have

a\le b\le\lfloor\frac{23-a}{2}\rfloor

and

c=23-a-b.

The gcd sum can be evaluated as

\begin{aligned} &\gcd(a,b)+\gcd(b,23-a) \\ &\quad {}+\gcd(a,23-b). \end{aligned}

Checking these short ranges, the possible gcd sums for

a=1,2,\ldots,7

are, respectively,

\{3,4,13\},

\{4,6,10\},

\{3,5,6,8,9,12\},

\{4,6\},

\{3,7,8,11\},

\{4,6,8\},

and

\{9,10\}.

The value

9

occurs only at

(a,b,c)=(3,5,15)

and

(7,7,9).

The triple

(7, 7, 9)

has

\gcd

sum

7 + 1 + 1 = 9

and

a^2 + b^2 + c^2 = 49 + 49 + 81

= 179.

The triple

(3, 5, 15)

has

\gcd

sum

1 + 5 + 3 = 9

and

a^2 + b^2 + c^2 = 9 + 25

+ 225 = 259.

The sum of the distinct values is

179 + 259 = 438.

Thus, the correct answer is B.

Problem 16 in other years