Track / Stage 5 / 95 of 400 #1175 of 2444

Problem 1175

AIME late

Number theory Difficulty 5.1 Prove it Ukrainian National Mathematical Olympiad, Third Round, Second Tour · Ukraine

Find all triples of positive integers $a$ , $b$ , $c$ , such that
$a + (a, b) = b + (b, c) = c + (c, a),$
where by $(x, y)$ we denote the largest common divisor of integers $x$ , $y$ .

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official solution

If numbers $a$ , $b$ , $c$ have a common divisor, we can divide by it and get a triple of integers $a_1$ , $b_1$ , $c_1$ , whose largest common divisor is $1$ . As $a_1 + (a_1, b_1) = b_1 + (b_1, c_1)$ , $(b_1, c_1)$ is divisible by $(a_1, b_1)$ . But $((a_1, b_1), (b_1, c_1)) = 1$ , as explained above, so $(a_1, b_1) = 1$ . Similarly we get that our numbers are pairwise coprime, so $a_1 + 1 = b_1 + 1 = c_1 + 1$ , implying $a = b = c$ .

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty, ordering) added by this project.