Maths Olympiad Prep

Library / /31 of 46

, 2015

Number theory Difficulty 6.5 National Olympiad Prove it Japan

Suppose positive integers aa, bb, cc satisfy the following four conditions:
\bullet gcd{a,b,c}=1\text{gcd}\{a, b, c\} = 1.
gcd(a,b+c)>1\text{gcd}(a, b + c) > 1.
gcd(b,c+a)>1\text{gcd}(b, c + a) > 1.
gcd(c,a+b)>1\text{gcd}(c, a + b) > 1.
Here we denote by gcd{}\text{gcd}\{ \} the greatest common divisor of the numbers in {}\{ \}.
Determine the minimum possible value the sum a+b+ca + b + c can take.

Solution

30\boxed{30}

Let g1=gcd{a,b+c}g_1 = \text{gcd}\{a, b+c\}, g2=gcd{b,c+a}g_2 = \text{gcd}\{b, c+a\}, g3=gcd{c,a+b}g_3 = \text{gcd}\{c, a+b\}. If there exists a prime pp which divides both g1g_1 and g2g_2, then pp must divide both aa and bb. Furthermore, since pp divides b+cb+c as well, cc must be divisible by pp, but this contradicts the assumption that gcd{a,b,c}=1\text{gcd}\{a, b, c\} = 1. Therefore, we conclude that g1g_1 and g2g_2 are relatively prime. Similarly, g2g_2 and g3g_3 are relatively prime and so are g3g_3 and g1g_1. Combining these facts with the assumption that g1g_1, g2g_2, g3g_3 are all greater than 11, we get g1g2g3235=30g_1g_2g_3 \ge 2 \cdot 3 \cdot 5 = 30.

Furthermore, since g1g_1 divides both aa and b+cb+c, it divides a+b+ca+b+c as well. Similarly, both g2g_2 and g3g_3 divide a+b+ca+b+c. Therefore, we conclude that the product g1g2g3g_1g_2g_3 divides a+b+ca+b+c also, and this implies that a+b+cg1g2g330a+b+c \ge g_1g_2g_3 \ge 30 must hold.

On the other hand, we see that the triple (a,b,c)=(2,3,25)(a, b, c) = (2, 3, 25) satisfies all the conditions of the problem and that a+b+c=30a + b + c = 30 is satisfied. Therefore, we conclude that 3030 is the minimum value we seek.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.