Maths Olympiad Prep

Track / Stage 5 / 223 of 400 #1303 of 2444

Problem 1303

AIME late
Number theory Difficulty 5.5 Prove it Croatia Mathematical Competitions · Croatia

Determine all positive integers nn for which there exists a divisor dd of nn such that
dn+1d2+n2. dn + 1 \mid d^2 + n^2.

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Next problem →

Official solution

Let us put n=adn = a d. The condition dn+1d2+n2d n + 1 \mid d^2 + n^2 can be written as ad2+1d2+a2d2a d^2 + 1 \mid d^2 + a^2 d^2.
Then ad2+1a d^2 + 1 divides d2+a2d2a(ad2+1)=d2ad^2 + a^2 d^2 - a \cdot (a d^2 + 1) = d^2 - a as well.
Let us consider all possible signs of the number d2ad^2 - a.
If d2a>0d^2 - a > 0, then it must be d2aad2+1d^2 - a \ge a d^2 + 1 (multiple is greater than or equal to divisor). Since aa is positive, we have d2ad2+a+1>d2d^2 \ge a d^2 + a + 1 > d^2, which is impossible.

If d2a<0d^2 - a < 0, then ad2>0a - d^2 > 0. Then it must be ad2ad2+1a - d^2 \ge a d^2 + 1. Since dd is positive, we have aad2+1+d2>aa \ge a d^2 + 1 + d^2 > a, which is also impossible.
Hence, the only possibility is d2a=0d^2 - a = 0, which gives a=d2a = d^2 and n=d3n = d^3. In that case d4+1d^4 + 1 divides d2+d6=d2(d4+1)d^2 + d^6 = d^2(d^4 + 1), so all possible numbers nn are cubes of positive integers.

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