Olympiad Maths Prep

Library / /7 of 33

Number theory Difficulty 5.7 AIME, harder Prove it Belarus

Find all pairs of positive integers (a;b)(a; b), aba \le b, satisfying the equality a3+b3=1911aba^3 + b^3 = 1911ab.

Solution

Answer: (756;1008)(756; 1008), (600;960)(600; 960).

Let dd denote the greatest common divisor of aa and bb, i.e., a=da1a = da_1, b=db1b = db_1, where gcd(a1,b1)=1\gcd(a_1, b_1) = 1. Then the given equality can be presented in the form
d(a13+b13)=1911a1b1. d(a_1^3 + b_1^3) = 1911a_1b_1.
It follows that da13:b1d a_1^3 : b_1, and, since a1a_1 and b1b_1 are coprime, d:b1d : b_1. Similarly, d:a1d : a_1. Hence, d:a1b1d : a_1b_1 because a1a_1 and b1b_1 are coprime. Let d=d1a1b1d = d_1 a_1 b_1, then the equation can be presented in the form
d1(a13+b13)=1911,a1b1.(1) d_1(a_1^3 + b_1^3) = 1911, \quad a_1 \le b_1. \qquad (1)
Note that a13+b13(a1+b1)3/4a_1^3 + b_1^3 \ge (a_1 + b_1)^3/4, whence 41911d1(a1+b1)34 \cdot 1911 \ge d_1 \cdot (a_1 + b_1)^3; therefore, 8000>(a1+b1)38000 > (a_1 + b_1)^3, or a1+b1<20a_1 + b_1 < 20.

Further, a13+b13=(a1+b1)33a1b1(a1+b1)a_1^3 + b_1^3 = (a_1 + b_1)^3 - 3 a_1 b_1 (a_1 + b_1), and (1) can be rewritten as
d1(a1+b1)((a1+b1)23a1b1)=1911.(2) d_1(a_1 + b_1)((a_1 + b_1)^2 - 3 a_1 b_1) = 1911. \qquad (2)
We see that a1+b1a_1 + b_1 is a divisor (less than 20) of 1911=372131911 = 3 \cdot 7^2 \cdot 13. Hence exactly three cases are possible.

1. a1+b1=3a_1 + b_1 = 3, a1=1a_1 = 1, b1=2b_1 = 2. Then d13(96)=1911d_1 \cdot 3 \cdot (9 - 6) = 1911, but 99 is not a divisor of 19111911.

2. a1+b1=7a_1 + b_1 = 7. If a1=1a_1 = 1, b1=6b_1 = 6, then d17(4918)=1911d_1 \cdot 7 \cdot (49 - 18) = 1911, but 4918=3149 - 18 = 31 is not a divisor of 19111911.
If a1=2a_1 = 2, b1=5b_1 = 5, we have d17(4930)=1911d_1 \cdot 7 \cdot (49 - 30) = 1911, but 4930=1949 - 30 = 19 is not a divisor of 19111911.
Finally, if a1=3a_1 = 3, b1=4b_1 = 4, then d17(4936)=1911d_1 \cdot 7 \cdot (49 - 36) = 1911, which gives d1=21d_1 = 21, whence d=2134=252d = 21 \cdot 3 \cdot 4 = 252, i.e., the pair a=756a = 756, b=1008b = 1008 is a solution.

3. a1+b1=13a_1 + b_1 = 13. If a1=1a_1 = 1, b1=12b_1 = 12, then d113(16936)=1911d_1 \cdot 13 \cdot (169 - 36) = 1911, but 16936=133169 - 36 = 133 does not divide 19111911.
If a1=2a_1 = 2, b1=11b_1 = 11, then d113(16966)=13d1103d_1 \cdot 13 \cdot (169 - 66) = 13 d_1 \cdot 103 does not divide 19111911.
If a1=3a_1 = 3, b1=10b_1 = 10, then d113(16990)=13d179d_1 \cdot 13 \cdot (169 - 90) = 13 d_1 \cdot 79 does not divide 19111911.
If a1=5a_1 = 5, b1=8b_1 = 8, then d113(169120)=d11349=1911d_1 \cdot 13 \cdot (169 - 120) = d_1 \cdot 13 \cdot 49 = 1911, which gives d1=3d_1 = 3, whence d=358=120d = 3 \cdot 5 \cdot 8 = 120, i.e., the pair a=600a = 600, b=960b = 960 is a solution.
Finally, if a1=6a_1 = 6, b1=7b_1 = 7, then d113(169126)=13d143d_1 \cdot 13 \cdot (169 - 126) = 13 d_1 \cdot 43 does not divide 19111911.

Thus, the equation has two solutions mentioned above.

Looking for a route rather than 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.