Number theoryDifficulty 7.4National Olympiad, round 2Prove itHong Kong
Let m,n be distinct positive integers not exceeding 2013 and d be their greatest common divisor. Suppose d2 divides 3(m−n). Find the greatest possible value of d(m+n).
Solution
The greatest possible value of d(m+n) is 166635. Let m=da and n=db so that (a,b)=1. The condition becomes d∣3(a−b). WLOG assume m>n. Let N=d(m+n)=d2(a+b). If 3∤d, then d∣a−b. This implies d≤a−b. Also, we have a=dm≤d2013. This yields N=d2(a+b)≤d2(2a−d)≤4026d−d3.
By differentiation, the maximum value of 4026d−d3 is attained at d=34026. Thus, N≤34026(4026−34026)<40⋅3000=120000. If 3∣d, then d≤3(a−b). Also, we have a≤⌊d2013⌋. This yields N=d2(a+b)≤d2(2a−3d)≤d2(2⌊d2013⌋−3d). * For d≤54, we have N≤4026d−3d3≤4026(54)−3(54)3=164916 since f(d)=4026d−3d3 is increasing for d≤54 (again by differentiation). * For d=57, we have N≤(57)2(2⌊572013⌋−357)=165699. * For d=60, we have N≤(60)2(2⌊602013⌋−360)=165600. * For d=63, we have N≤(63)2(2⌊632013⌋−363)=162729. * For d=66, we have N≤(66)2(2⌊662013⌋−366)=165528. * For d=69, we have N≤(69)2(2⌊692013⌋−369)=166635. * For d≥72, we have N≤4026d−3d3≤4026(72)−3(72)3=165456 since f(d) is decreasing for d≥54. To conclude, we have N≤166635. Equality holds when d=69, a=29 and b=6. This means (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.