Maths Olympiad Prep

Library / /93 of 377

Number theory Difficulty 4.8 AIME Prove it United States

Problem:
Find the largest positive integer nn such that 1+2+3++n21+2+3+\cdots+n^{2} is divisible by 1+2+3++n1+2+3+\cdots+n.

Solution

Solution:
The statement is
n(n+1)2n2(n2+1)2n+1n(n2+1)=n3+n. \frac{n(n+1)}{2} \mid \frac{n^{2}(n^{2}+1)}{2} \Leftrightarrow n+1 \mid n(n^{2}+1) = n^{3}+n.
But n+1n+1 also divides (n+1)(n2n+2)=n3+n+2(n+1)(n^{2}-n+2) = n^{3}+n+2, so n+1n+1 must divide 22. Hence, nn cannot be greater than 11. And n=1n=1 clearly works, so that is the answer.

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.