Maths Olympiad Prep

Library / /462 of 860

Number theory Difficulty 5.2 AIME, harder Find the answer

Given that a,b,ca, b, c are positive integers satisfying a+b+c=gcd(a,b)+gcd(b,c)+gcd(c,a)+120a+b+c=\operatorname{gcd}(a, b)+\operatorname{gcd}(b, c)+\operatorname{gcd}(c, a)+120 determine the maximum possible value of aa.

A number or a short expression. Spacing and $ signs are ignored.

Solution

240. Notice that (a,b,c)=(240,120,120)(a, b, c)=(240,120,120) achieves a value of 240. To see that this is maximal, first suppose that a>ba>b. Notice that a+b+c=gcd(a,b)+gcd(b,c)+a+b+c=\operatorname{gcd}(a, b)+\operatorname{gcd}(b, c)+ gcd(c,a)+120gcd(a,b)+b+c+120\operatorname{gcd}(c, a)+120 \leq \operatorname{gcd}(a, b)+b+c+120, or agcd(a,b)+120a \leq \operatorname{gcd}(a, b)+120. However, gcd(a,b)\operatorname{gcd}(a, b) is a proper divisor of aa, so a2gcd(a,b)a \geq 2 \cdot \operatorname{gcd}(a, b). Thus, a120gcd(a,b)a/2a-120 \leq \operatorname{gcd}(a, b) \leq a / 2, yielding a240a \leq 240. Now, if instead aba \leq b, then either b>cb>c and the same logic shows that b240a240b \leq 240 \Rightarrow a \leq 240, or bc,c>ab \leq c, c>a (since a,b,ca, b, c cannot all be equal) and then c240abc240c \leq 240 \Rightarrow a \leq b \leq c \leq 240.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.