Maths Olympiad Prep

Library / /17 of 136

Number theory Difficulty 7.4 National Olympiad, round 2 Prove it Hong Kong

Let m,nm, n be distinct positive integers not exceeding 20132013 and dd be their greatest common divisor. Suppose d2d^2 divides 3(mn)3(m-n). Find the greatest possible value of d(m+n)d(m+n).

Solution

The greatest possible value of d(m+n)d(m+n) is 166635166635.
Let m=dam = da and n=dbn = db so that (a,b)=1(a, b) = 1. The condition becomes d3(ab)d \mid 3(a - b). WLOG assume m>nm > n. Let N=d(m+n)=d2(a+b)N = d(m + n) = d^2(a + b).
If 3d3 \nmid d, then dabd \mid a-b. This implies dabd \le a-b. Also, we have a=md2013da = \frac{m}{d} \le \frac{2013}{d}. This yields
N=d2(a+b)d2(2ad)4026dd3. N = d^2(a + b) \le d^2(2a - d) \le 4026d - d^3.

By differentiation, the maximum value of 4026dd34026d - d^3 is attained at d=40263d = \sqrt{\frac{4026}{3}}.
Thus,
N40263(402640263)<403000=120000. N \le \sqrt{\frac{4026}{3}} \left(4026 - \frac{4026}{3}\right) < 40 \cdot 3000 = 120000.
If 3d3 \mid d, then d3(ab)d \le 3(a-b). Also, we have a2013da \le \lfloor \frac{2013}{d} \rfloor. This yields
N=d2(a+b)d2(2ad3)d2(22013dd3). N = d^2(a+b) \le d^2 \left( 2a - \frac{d}{3} \right) \le d^2 \left( 2 \lfloor \frac{2013}{d} \rfloor - \frac{d}{3} \right).
* For d54d \le 54, we have N4026dd334026(54)(54)33=164916N \le 4026d - \frac{d^3}{3} \le 4026(54) - \frac{(54)^3}{3} = 164916 since f(d)=4026dd33f(d) = 4026d - \frac{d^3}{3} is increasing for d54d \le 54 (again by differentiation).
* For d=57d = 57, we have N(57)2(2201357573)=165699N \le (57)^2 \left(2 \lfloor \frac{2013}{57} \rfloor - \frac{57}{3}\right) = 165699.
* For d=60d = 60, we have N(60)2(2201360603)=165600N \le (60)^2 \left(2 \lfloor \frac{2013}{60} \rfloor - \frac{60}{3}\right) = 165600.
* For d=63d = 63, we have N(63)2(2201363633)=162729N \le (63)^2 \left(2 \lfloor \frac{2013}{63} \rfloor - \frac{63}{3}\right) = 162729.
* For d=66d = 66, we have N(66)2(2201366663)=165528N \le (66)^2 \left(2 \lfloor \frac{2013}{66} \rfloor - \frac{66}{3}\right) = 165528.
* For d=69d = 69, we have N(69)2(2201369693)=166635N \le (69)^2 \left(2 \lfloor \frac{2013}{69} \rfloor - \frac{69}{3}\right) = 166635.
* For d72d \ge 72, we have N4026dd334026(72)(72)33=165456N \le 4026d - \frac{d^3}{3} \le 4026(72) - \frac{(72)^3}{3} = 165456 since f(d)f(d) is decreasing for d54d \ge 54.
To conclude, we have N166635N \le 166635. Equality holds when d=69d = 69, a=29a = 29 and b=6b = 6. This means (m,n)=(2001,414)(m, n) = (2001, 414).

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.