SAUDI ARABIAN MATHEMATICAL COMPETITIONS

The case $p=2$ works with solutions $(0,0)$ and $(1,1)$ if $a$ is even; $(0,0)$ and $(0,1)$ if $a$ is odd.

We claim that any odd prime divisor $p$ of $a$ also works. Of course for $0\le x,y\le p-1$, the congruence $y^2\equiv x^3(\mathrm{mod}p)$ implies that $x=0$ if and only if $y=0$. For any $0<x\le p-1$, it's clear that $x^3=x^2\cdot x$ is a quadratic residue modulo $p$ if and only if $x$ is.

Therefore, if $x$ is not a quadratic residue then we cannot find any $y$ such that $y^2\equiv x^3(\mathrm{mod}p)$ and if $x$ is a quadratic residue the congruence $y^2\equiv x^3(\mathrm{mod}p)$ has exactly 2 solutions in the set $\{1,2,\dots ,p-1\}$ (the condition $p$ is odd ensures that 2 solutions are distinct).

Since there are $(p-1)/2$ quadratic residues, the number of $(x,y)$ with the required property is $$1+2\cdot (p-1)/2=p.$$ If $p\equiv 3(\mathrm{mod}4)$ then $-1$ is not a quadratic residue, so if $x^3+a^{2}x\ne 0$, then exactly one of $x^3+a^{2}x$ and $-x^3-a^{2}x$ is a square and it gives two solutions. Together with $(0,0)$, it gives us exactly $p$ solutions.

If $p\equiv 1(\mathrm{mod}4)$, let $i$ be a square root of $-1(\mathrm{mod}p)$, i.e. $i^2=-1$. Then we have $$y^2\equiv x(x+ai)(x-ai)(\mathrm{mod}p).$$ For $x=0,ai,-ai$, we have one choice of $y=0$. For other choices of $x$, we have either 0 or 2 choices of $y$. Replacing $x$ by $-x$, since $-1$ is a quadratic residue, we also have two choices for $y$. Hence, the total number of pairs is $3(\mathrm{mod}4)$, which cannot be exactly $p$.

Thus, the answer is $p=2$, all the odd prime divisors of $a$ and $p\equiv 3(\mathrm{mod}4)$.