Saudi Arabian Mathematical Competitions

We will construct (by induction on $k$) the infinite increasing sequence $\left(n_{k}\right)_{k \geq 1}$ of odd positive integers such that any $n_{k}$ satisfies $4^{n_{k}}+5^{n_{k}}$ is divisible by $n_{k}^{2}$.

We take $n_{1}=1$ and $n_{2}=3$.

Assume we already have $n_{k}$, that is $4^{n_{k}}+5^{n_{k}}=a n_{k}^{2}$ for some positive integer $a$ which must be odd, and greater than 1 (since $n_{k} \geqslant n_{2}=3$, it follows that $4^{n_{k}}+5^{n_{k}}>n_{k}^{2}$).

Take $p$ an odd prime divisor of $a$. Substitute $4^{n_{k}}$ by $x$ and $5^{n_{k}}$ by $y$. Then, obviously
$$x^{p}+y^{p}=(x+y)\left(x^{p-1}-y x^{p-2}+\cdots-y^{p-2} x+y^{p-1}\right)$$
is divisible by $p n_{k}^{2}$. Furthermore, it is clear that
$$x^{p-1},-y x^{p-2}, \ldots,-y^{p-2} x, y^{p-1}$$
are congruent to each other modulo $p$, and the number of them is $p$.

So, $x^{p-1}-y x^{p-2}+\cdots-y^{p-2} x+y^{p-1}$ must be divisible by $p$. It follows that $x^{p}+y^{p}$ is divisible by $\left(p n_{k}\right)^{2}$.

Now we take $n_{k+1}=p n_{k}$. As $p>1, n_{k+1}>n_{k}$, and $4^{n_{k+1}}+5^{n_{k+1}}$ is divisible by $n_{k+1}^{2}$.

Finally, it is clear that the number $n=2 n_{k}$ satisfies $n^{2} \mid 20^{n}+16^{n}$ for any positive integer $k$, which completes the solution.