If $a$ is a solution to this equation, then we must have $p \not\mid a$. This is because if $p\mid a$, then $a^2 + 1\equiv 1\pmod{p}$

By Thue's Theorem (# 4186), there exist positive integers $x$ and $y$ not exceeding $\lfloor{\sqrt{p}}\rfloor$ such that $$ax\equiv \pm y\pmod{p}\implies a^2x^2\equiv y^2\pmod{p}$$

Now multiplying $a^2 + 1\equiv 0\pmod{p}$ by $x^2$ gives $$0\equiv a^2x^2 + x^2 \equiv x^2 + y^2\pmod{p}$$

This means $x^2 + y^2 = kp$ where $k$ is a positive integer. If we can show $k=1$, then $p$ is a sum of two squares. This is indeed the case because $$x, y \le \lfloor{\sqrt{p}}\rfloor \implies x^2 + y^2 < 2p \implies k < 2$$