Maths Olympiad Prep

Library / Saudi Arabian IMO Booklet /1 of 26

Saudi Arabian IMO Booklet

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=k2−1n = 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⌋=k−1\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,…,k−1}∣=2⋅k2=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 k−1k-1 must divide n=k2−1n = k^2 - 1.
In particular, k−3k-3 must divide k2−1k^2-1; but
k2−1k−3=k+3+8k−3. \frac{k^2 - 1}{k - 3} = k + 3 + \frac{8}{k - 3}.
Therefore, k−3k-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,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

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