Competition problem — Number theory

Library / /1 of 11

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,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.