
N7. Find all perfect squares $n$ such that if the positive integer $a \geqslant 15$ is some divisor of $n$ then $a+15$ is a prime power.


Solution. We call positive a integer $a$ "nice" if $a+15$ is a prime power.

From the definition, the numbers $n=1,4,9$ satisfy the required property. Suppose that for some $t \in \mathbb{Z}^{+}$, the number $n=t^{2} \geqslant 15$ also satisfies the required property. We have two cases:

1. If $n$ is a power of 2 , then $n \in\{16,64\}$ since

$$
2^{4}+15=31, \quad 2^{5}+15=47, \quad \text { and } \quad 2^{6}+15=79
$$

are prime, and $2^{7}+15=143=11 \cdot 13$ is not a prime power. (Thus $2^{7}$ does not divide $n$ and therefore no higher power of 2 satisfies the required property.)

2. Suppose $n$ has some odd prime divisor $p$. If $p>3$ then $p^{2} \mid n$ and $p^{2}>15$ which imply that $p^{2}$ must be a nice number. Hence

$$
p^{2}+15=q^{m}
$$

for some prime $q$ and some $m \in \mathbb{Z}^{+}$. Since $p$ is odd, then $p^{2}+15$ is even, thus we can conclude that $q=2$. I.e.

$$
p^{2}+15=2^{m}
$$

Considering the above modulo 3 , we can see that $p^{2}+15 \equiv 0,1 \bmod 3$, so $2^{m} \equiv$ $1 \bmod 3$, and so $m$ is even. Suppose $m=2 k$ for some $k \in \mathbb{Z}^{+}$. So we have $\left(2^{k}-p\right)\left(2^{k}+p\right)=15$ and $\left(2^{k}+p\right)-\left(2^{k}-p\right)=2 p \geqslant 10$. Thus

$$
2^{k}-p=1 \quad \text { and } \quad 2^{k}+p=15
$$

giving $p=7$ and $k=3$. Thus we can write $n=4^{x} \cdot 9^{y} \cdot 49^{z}$ for some non-negative integers $x, y, z$.

Note that 27 is not nice, so $27 \nmid n$ and therefore $y \leqslant 1$. The numbers 18 and 21 are also not nice, so similarly, $x, y$ and $y, z$ cannot both positive. Hence, we just need to consider $n=4^{x} \cdot 49^{z}$ with $z \geqslant 1$.

Note that $7^{3}$ is not nice, so $z=1$. By checking directly, we can see that $7^{2}+15=$ $2^{6}, 2 \cdot 7^{2}+15=113,4 \cdot 7^{2}+15=211$ are nice, but $8 \cdot 7^{2}$ is not nice, so only $n=49,196$ satisfy the required property.

Therefore, the numbers $n$ which satisfy the required property are $1,4,9,16,49,64$ and 196 .

Remark by PSC. One can get rid of the case $3 \mid n$ by noting that in that case, we have $9 \mid n$. But then $n^{2}+15$ is a multiple of 3 but not a multiple of 9 which is impossible. This simplifies a little bit the second case.

