Library / National Olympiad Final Round /1 of 10

National Olympiad Final Round

Number theory Difficulty 5.3 AIME, harder Prove it Estonia

Find the least positive integer $n$ for which there exists a positive integer $a$ such that both $a$ and $a+735$ have exactly $n$ positive divisors.

Solution

If numbers $a$ and $a+735$ had exactly $2$ divisors, they would be primes. These numbers are of different parity, whence one of them is even. But if $a=2$ then $a+735 = 737 = 11 \cdot 67$ .
If numbers $a$ and $a+735$ had exactly $3$ divisors, each of them would be a square of a prime. Similarly to the previous case, we get $a = 4$ . But then $a+735 = 739$ , and $739$ is not a perfect square.
On the other hand, numbers $10$ and $10+735$ have exactly $4$ divisors.

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.