Maths Olympiad Prep

Library / /29 of 30

Number theory Difficulty 7.1 National Olympiad, round 2 Prove it Italy

Problem:

Determine all triples of strictly positive integers (a,b,c)(a, b, c) such that
- abca \leq b \leq c;
- MCD(a,b,c)=1\operatorname{MCD}(a, b, c)=1;
- aa is a divisor of b+cb+c, bb is a divisor of c+ac+a and cc is a divisor of a+ba+b.

Solution

Solution:

The only solution triples are (1,1,1)(1,1,1), (1,1,2)(1,1,2) and (1,2,3)(1,2,3).

Let us first show that a,b,ca, b, c are pairwise coprime (we only show that MCD(a,b)=1\operatorname{MCD}(a, b)=1; for the other pairs the proof is the same).
If dd is the greatest common divisor of aa and bb, then dd divides aa, which in turn divides b+cb+c, so dd divides b+cb+c; but dd divides bb, so it also divides b+cb=cb+c-b=c.
Then dd is simultaneously a divisor of a,ba, b and of cc, and hence d=1d=1, since MCD(a,b,c)=1\operatorname{MCD}(a, b, c)=1 by hypothesis.

We now note that aa divides b+cb+c by hypothesis, so aa also divides the sum (b+c)+a(b+c)+a; similarly we obtain that bb and cc also divide a+b+ca+b+c.
Since a,b,ca, b, c are pairwise coprime, the fact that each of them divides the sum a+b+ca+b+c implies that the product abca b c also divides a+b+ca+b+c.
All divisors of a natural number are less than or equal to the number itself, so a necessary condition for this to happen is that abca+b+ca b c \leq a+b+c.
Using the hypothesis abca \leq b \leq c we obtain the inequality
abca+b+c3cab3 a b c \leq a+b+c \leq 3 c \Rightarrow a b \leq 3
we therefore need to consider (since a,ba, b are positive integers) the following three cases:
- a=b=1a=b=1. Then cc is a divisor of a+b=2a+b=2, and we find the first two candidate solution triples: (a,b,c)=(1,1,1)(a, b, c)=(1,1,1) and (a,b,c)=(1,1,2)(a, b, c)=(1,1,2). Both satisfy all the conditions imposed by the problem, and are thus indeed solutions.
- a=1,b=2a=1, b=2. Then cc is a divisor of a+b=3a+b=3 greater than or equal to b=2b=2, so necessarily c=3c=3 and we find the last candidate solution triple (a,b,c)=(1,2,3)(a, b, c)=(1,2,3). Indeed 1 is a divisor of 2+3=52+3=5, 2 is a divisor of 1+3=41+3=4 and 3 is a divisor of 1+2=31+2=3, so the triple is a solution.
- a=1,b=3a=1, b=3. Then cc is a divisor of a+b=4a+b=4 greater than or equal to b=3b=3, so necessarily c=4c=4; but we would also need bb to be a divisor of a+ca+c, that is, 3 a divisor of 4+1=54+1=5, which is false. Hence the triple (1,3,4)(1,3,4) is not a solution.

By hypothesis a+ba+b is a multiple of cc, and is less than or equal to 2c2 c (since ac,bca \leq c, b \leq c). We thus distinguish the cases a+b=2ca+b=2 c and a+b=ca+b=c.
- In the first case 2c=a+bc+c=2c2 c=a+b \leq c+c=2 c, so in order to have equality we must have a=b=ca=b=c. By hypothesis a,b,ca, b, c have greatest common divisor 1, so the only possibility is a=b=c=1a=b=c=1.
- In the second case, substituting bb with cac-a in the hypothesis we obtain that aa divides b+c=2cab+c=2 c-a and that b=cab=c-a divides a+ca+c.
The first divisibility implies that 2c=ka2 c=k a for some integer kk, and since cac \geq a we know that k2k \geq 2. Moreover, since cac-a divides c+ac+a, it also divides (c+a)+(ca)=2c=ka(c+a)+(c-a)=2 c=k a. This means that the quantity
kaca=2ka2c2a=2kaka2a=2kk2=2k4+4k2=2+4k2 \frac{k a}{c-a}=\frac{2 k a}{2 c-2 a}=\frac{2 k a}{k a-2 a}=\frac{2 k}{k-2}=\frac{2 k-4+4}{k-2}=2+\frac{4}{k-2}
is an integer, so k2k-2 divides 4. We know that k2k \geq 2, so k2k-2 is a non-negative divisor of 4, and hence is necessarily one of 1,2,41,2,4.
These possibilities correspond to k=3,4,6k=3,4,6, that is, to c=3a2c=\frac{3 a}{2}, c=2ac=2 a, c=3ac=3 a and b=ca=a2b=c-a=\frac{a}{2}, b=ab=a, b=2ab=2 a.
The first possibility is excluded by the hypothesis that bb be greater than or equal to aa, while in the other two cases we find the solution triples (a,b,c)=(a,a,2a)(a, b, c)=(a, a, 2 a) and (a,2a,3a)(a, 2 a, 3 a).
From the hypothesis that the greatest common divisor of a,b,ca, b, c be exactly 1 it follows that we must take a=1a=1, so the only solution triples of this form are (1,1,2)(1,1,2) and (1,2,3)(1,2,3).

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 translated into English from it; metadata (topic, difficulty) added by this project.