How to prove that either $2^{500} + 15$ or $2^{500} + 16$ isn't a perfect square?
Short solutions: $2^{1000} + 15 \equiv 3 \pmod{4}$, $2^{1000} + 16 \equiv 2 \pmod{3}$, neither of which are quadratic residues.
More elementary solution: $2^{1000} = (2^{500})^2$. The next perfect square is $$(2^{500} + 1)^2 = 2^{1000} + 2(2^{500}) + 1$$ which is clearly more than both $2^{1000} + 15$ and $2^{1000} + 16$. Therefore, these two can't possibly be perfect squares.
Hint: think about the distance between consecutive squares.