Maths Olympiad Prep

Library / /1 of 27

Number theory Difficulty 7.2 National olympiad, round 2 Prove it Saudi Arabia

Find all positive integers nn that have precisely n+1\sqrt{n+1} natural divisors.

Solution

First observe that n=k21n = k^2 - 1 for some positive integer kk. As nn is not a perfect square, τ(n)=k\tau(n) = k must be even, ergo nn is odd.
We now establish a bound on τ(n)\tau(n). Recall that, since nn is not a perfect square, there exists a bijective correspondence between factors of nn greater than n=k1\lfloor\sqrt{n}\rfloor = k-1 and factors of nn at most n\lfloor\sqrt{n}\rfloor. Furthermore, since nn is odd, all divisors of nn must also be odd. Therefore
k=τ(n)2{1,3,,k1}=2k2=k. k = \tau(n) \le 2 \cdot |\{1, 3, \dots, k-1\}| = 2 \cdot \frac{k}{2} = k.
Hence equality must hold, and so every odd number between 1 and k1k-1 must divide n=k21n = k^2 - 1.
In particular, k3k-3 must divide k21k^2-1; but
k21k3=k+3+8k3. \frac{k^2 - 1}{k - 3} = k + 3 + \frac{8}{k - 3}.
Therefore, k3k-3 is either 1-1 or 11, so kk equals either 22 or 44 and n{3,15}n \in \{3, 15\}, both of these work. \square

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.