Maths Olympiad Prep

Track / Stage 5 / 223 of 400 #1463 of 2604

Problem 1463

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+1∣d2+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+1∣d2+n2d n + 1 \mid d^2 + n^2 can be written as ad2+1∣d2+a2d2a d^2 + 1 \mid d^2 + a^2 d^2.
Then ad2+1a d^2 + 1 divides d2+a2d2−a⋅(ad2+1)=d2−ad^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 d2−ad^2 - a.
If d2−a>0d^2 - a > 0, then it must be d2−a≥ad2+1d^2 - a \ge a d^2 + 1 (multiple is greater than or equal to divisor). Since aa is positive, we have d2≥ad2+a+1>d2d^2 \ge a d^2 + a + 1 > d^2, which is impossible.

If d2−a<0d^2 - a < 0, then a−d2>0a - d^2 > 0. Then it must be a−d2≥ad2+1a - d^2 \ge a d^2 + 1. Since dd is positive, we have a≥ad2+1+d2>aa \ge a d^2 + 1 + d^2 > a, which is also impossible.
Hence, the only possibility is d2−a=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.