Mathematica competitions in Croatia

If $p=q=2$ we have $p^{q+1}+q^{p+1}=2^3+2^3=16$, so that is one solution of the problem.

Now, without loss of generality assume that $p$ is odd and let $p^{q+1}+q^{p+1}=x^2$, where $x\in \mathbb{N}$. Thus $p+1$ is even and $$p^{q+1}=\left(x-q^{\frac{p+1}{2}}\right)\left(x+q^{\frac{p+1}{2}}\right).$$ Denote the greatest common divisor of the two factors on the right-hand side by $d$. If $d>1$ we have that $d$ is a power of $p$ and $d$ is also a factor of $2x$. It is easy to see that $p\mid q$, i.e. $p=q$. Thus $2p^{p+1}=x^2$, which is impossible.

Therefore $d=1$, $x-q^{\frac{p+1}{2}}=1$, $x+q^{\frac{p+1}{2}}=p^{q+1}$ and hence $$2q^{\frac{p+1}{2}}=p^{q+1}-1.$$ The above equation is impossible for $q$ odd because $2q^{\frac{p+1}{2}}\equiv 2(\mathrm{mod}4)$ and $p^{q+1}-1\equiv 0(\mathrm{mod}4)$. We conclude that $q=2$ and $$2^{\frac{p+3}{2}}=p^3-1=(p-1)(p^2+p+1).$$ Since $\gcd (p-1,p^2+p+1)=1$ we conclude that $p-1=1$, what is a contradiction.