Maths Olympiad Prep

Library / /5 of 11

Number theory Difficulty 5.7 AIME, harder Prove it Estonia

Find all solutions of the equation a+b+c=61a + b + c = 61 in natural numbers that satisfy gcd(a,b)=2\text{gcd}(a, b) = 2, gcd(b,c)=3\text{gcd}(b, c) = 3, and gcd(c,a)=5\text{gcd}(c, a) = 5.

Solution

As gcd(a,b)=2\text{gcd}(a, b) = 2, gcd(b,c)=3\text{gcd}(b, c) = 3 and gcd(c,a)=5\text{gcd}(c, a) = 5, the number aa is divisible by both 22 and 55, the number bb is divisible by both 22 and 33, and the number cc is divisible by both 33 and 55. Hence aa is divisible by 1010, bb is divisible by 66 and cc is divisible by 1515. As 6161 gives remainder 11 when divided by each of 22, 33 and 55, the numbers a,ba, b and cc must give remainder 11 when divided by 33, 55 and 22, respectively. Since a,b,c61a, b, c \le 61, the possibilities are a=10a = 10 or a=40a = 40, b=6b = 6 or b=36b = 36, and c=15c = 15 or c=45c = 45. The sum 6161 appears in three cases: a=10,b=6,c=45a = 10, b = 6, c = 45; a=10,b=36,c=15a = 10, b = 36, c = 15; a=40,b=6,c=15a = 40, b = 6, c = 15. A straightforward check shows that the conditions gcd(a,b)=2\text{gcd}(a, b) = 2, gcd(b,c)=3\text{gcd}(b, c) = 3 and gcd(c,a)=5\text{gcd}(c, a) = 5 are also met in all these cases.

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: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.