Maths Olympiad Prep

Library / IMO Hk TST /15 of 119

IMO Hk TST

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(m−n)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 d∣3(a−b)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 3∤d3 \nmid d, then d∣a−bd \mid a-b. This implies d≤a−bd \le a-b. Also, we have a=md≤2013da = \frac{m}{d} \le \frac{2013}{d}. This yields
N=d2(a+b)≤d2(2a−d)≤4026d−d3. N = d^2(a + b) \le d^2(2a - d) \le 4026d - d^3.

By differentiation, the maximum value of 4026d−d34026d - d^3 is attained at d=40263d = \sqrt{\frac{4026}{3}}.
Thus,
N≤40263(4026−40263)<40⋅3000=120000. N \le \sqrt{\frac{4026}{3}} \left(4026 - \frac{4026}{3}\right) < 40 \cdot 3000 = 120000.
If 3∣d3 \mid d, then d≤3(a−b)d \le 3(a-b). Also, we have a≤⌊2013d⌋a \le \lfloor \frac{2013}{d} \rfloor. This yields
N=d2(a+b)≤d2(2a−d3)≤d2(2⌊2013d⌋−d3). 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 d≤54d \le 54, we have N≤4026d−d33≤4026(54)−(54)33=164916N \le 4026d - \frac{d^3}{3} \le 4026(54) - \frac{(54)^3}{3} = 164916 since f(d)=4026d−d33f(d) = 4026d - \frac{d^3}{3} is increasing for d≤54d \le 54 (again by differentiation).
* For d=57d = 57, we have N≤(57)2(2⌊201357⌋−573)=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(2⌊201360⌋−603)=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(2⌊201363⌋−633)=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(2⌊201366⌋−663)=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(2⌊201369⌋−693)=166635N \le (69)^2 \left(2 \lfloor \frac{2013}{69} \rfloor - \frac{69}{3}\right) = 166635.
* For d≥72d \ge 72, we have N≤4026d−d33≤4026(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 d≥54d \ge 54.
To conclude, we have N≤166635N \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,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.