Olympiad Maths Prep

Track / Stage 7 / 157 of 300 #1557 of 2000

Problem 1557

National olympiad second round; IMO P1/P4
Number theory Difficulty 7.3 Prove it

Let a,b,cZ+a,b,c\in\mathbb{Z^{+}} such that
(a21,b21,c21)=1(a^2-1, b^2-1, c^2-1)=1
Prove that
(ab+c,bc+a,ca+b)=(a,b,c)(ab+c, bc+a, ca+b)=(a,b,c)
(As usual, (x,y,z)(x,y,z) means the greatest common divisor of numbers x,y,zx,y,z)

[I]Proposed by A. Golovanov[/i]

This one wants a proof. Work it on paper, read the official solution, then mark yourself honestly — the ladder only means something if the record is true.

Official solution

1. Initial Setup and Assumptions:
Given a,b,cZ+a, b, c \in \mathbb{Z}^+ such that (a21,b21,c21)=1(a^2 - 1, b^2 - 1, c^2 - 1) = 1, we need to prove that (ab+c,bc+a,ca+b)=(a,b,c)(ab + c, bc + a, ca + b) = (a, b, c).

2. Divisibility in One Direction:
Clearly, (a,b,c)(ab+c,bc+a,ca+b)(a, b, c) \mid (ab + c, bc + a, ca + b). This is because any common divisor of a,b,ca, b, c will also divide any linear combination of these terms.

3. **Defining dd:**
Let d=(ab+c,bc+a,ca+b)d = (ab + c, bc + a, ca + b). We need to show that d(a,b,c)d \mid (a, b, c).

4. Divisibility by Linear Combinations:
We have:
d(a+1)(b+c),d(b+1)(c+a),d(c+1)(a+b) d \mid (a+1)(b+c), \quad d \mid (b+1)(c+a), \quad d \mid (c+1)(a+b)
We aim to show that d(a+b),(b+c),(c+a)d \mid (a+b), (b+c), (c+a).

5. Prime Divisor Analysis:
Assume dd has a prime divisor pp. Consider pa+1p \mid a+1. If pb+1p \mid b+1 and pc+1p \mid c+1, then (a+1,b+1,c+1)p>1(a+1, b+1, c+1) \geq p > 1, which contradicts (a21,b21,c21)=1(a^2 - 1, b^2 - 1, c^2 - 1) = 1.

6. Case Analysis:
- If pa+1p \mid a+1 but pb+1p \nmid b+1 and pc+1p \nmid c+1, then pa+bp \mid a+b and pa+cp \mid a+c.
- Using ab1(modp)a \equiv b \equiv -1 \pmod{p}, we get p=2p = 2. Thus, aa and bb are odd, making cc even, which contradicts pab+cp \nmid ab + c.

7. Contradiction and Conclusion:
- If pa+1p \mid a+1, then pb+1p \nmid b+1 and pc+1p \nmid c+1, leading to pa+bp \mid a+b and pa+cp \mid a+c.
- This implies p(a+1,b1,c1)p \mid (a+1, b-1, c-1), another contradiction.

8. No Prime Divisor:
Therefore, no prime pp divides a+1,b+1,c+1a+1, b+1, c+1, and thus da+b,b+c,c+ad \mid a+b, b+c, c+a.

9. Further Divisibility:
- dab+c    dabb=a(b1)d \mid ab + c \implies d \mid ab - b = a(b-1)
- Similarly, db(c1)d \mid b(c-1) and dc(a1)d \mid c(a-1)

10. Prime Divisor Analysis Again:
- Assume pa1p \mid a-1. Since (a,a1)=1(a, a-1) = 1, pda(b1)p \mid d \mid a(b-1) implies db1d \mid b-1.
- Similarly, dc1d \mid c-1, contradicting (a21,b21,c21)=1(a^2 - 1, b^2 - 1, c^2 - 1) = 1.

11. Final Conclusion:
No such prime pp exists, so da,b,cd \mid a, b, c. Hence, d(a,b,c)d \mid (a, b, c), and therefore (ab+c,bc+a,ca+b)(a,b,c)(ab + c, bc + a, ca + b) \mid (a, b, c).

The final answer is (a,b,c) \boxed{ (a, b, c) } .

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