Olympiad Maths Prep

Library / /6 of 22

Number theory Difficulty 5.1 AIME, harder Prove it Belarus

A positive integer n>10n > 10 has two different positive integer divisors aa and bb such that n=a2+bn = a^2 + b.
Prove that strictly between the numbers aa and bb there is at least one another divisor of nn.

Solution

From the equality n=a2+bn = a^2 + b it follows that bb is divisible by aa, since aa divides both nn and a2a^2. Let b=mab = ma, where m>1m > 1. Then n=a2+ma=a(a+m)n = a^2 + ma = a(a + m), so a+ma + m divides nn. Let us show that a<a+m<ba < a + m < b. Suppose a+mba + m \ge b, then
a+mma    amam+11    (a1)(m1)1. a + m \ge ma \iff am - a - m + 1 \le 1 \iff (a - 1)(m - 1) \le 1.
The latter inequality holds only if a=m=2a = m = 2 whence b=4b = 4, but then n=24=8<10n = 2 \cdot 4 = 8 < 10, which contradicts with the conditions of the problem. Therefore, a+ma + m is the required divisor of nn, located between aa and bb.

Looking for a route rather than 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 and solution reproduced as published; topic and difficulty added by this site.