Maths Olympiad Prep

Library / /55 of 60

Number theory Difficulty 5.9 AIME, harder Prove it South Africa

We call a divisor dd of a positive integer nn special if d+1d + 1 is also a divisor of nn. Prove: at most half the positive divisors of a positive integer can be special. Determine all positive integers for which exactly half the positive divisors are special.

Solution

We prove that no positive divisor dd of nn that is greater or equal to n\sqrt{n} can be special: if dd is special, then d+1d + 1 is also a divisor, so n/dn/d and n/(d+1)n/(d + 1) are both integers, which means that their difference is at least 1. Thus
ndnd+1+1, \frac{n}{d} \geq \frac{n}{d+1} + 1,
which is equivalent to nd(d+1)n \ge d(d+1). But since d(d+1)>d2nd(d+1) > d^2 \ge n, this is a contradiction. Thus only divisors less than n\sqrt{n} can be special. Since divisors come in pairs (aa and n/an/a) such that one of them is less than n\sqrt{n} and one greater than n\sqrt{n} (when nn is a square, n\sqrt{n} is paired with itself), this means that at most half the divisors can be special.

If precisely half the divisors are special, then nn cannot be a square, and every divisor less than n\sqrt{n} has to be special. Thus 1 has to be a special divisor, meaning that 2 is a divisor (and thus also special), so 3 is a divisor, and so on, up to the greatest integer kk that is less than n\sqrt{n}. Finally, kk is special, so k+1k + 1 has to be a divisor as well. Since kk is the greatest divisor less than n\sqrt{n} and k+1k + 1 the least divisor greater than n\sqrt{n}, their product must be nn, so n=k(k+1)=k2+kn = k(k + 1) = k^2 + k. Moreover, k1k - 1 is also a divisor of n=k2+kn = k^2 + k (unless k=1k = 1), so it also divides n(k1)(k+2)=k2+k(k2+k2)=2n - (k - 1)(k + 2) = k^2 + k - (k^2 + k - 2) = 2.

This leaves us with k=1k = 1, k=2k = 2 and k=3k = 3 as the only possibilities, giving us n=2n = 2, n=6n = 6 or n=12n = 12. In all these cases, exactly half the divisors are special.

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 and solution reproduced as published; topic and difficulty added by this site.