SAUDI ARABIAN MATHEMATICAL COMPETITIONS

We will construct (by induction on $k$) the infinite increasing sequence ${\left(n_k\right)}_{k\ge 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⩾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},\dots ,-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=2n_k$ satisfies $n^2\mid 20^n+16^n$ for any positive integer $k$, which completes the solution.