Is it possible for $x^2=a \pmod p$ and $x^2=b \pmod p$ do not have solutions, but $x^2=ab \pmod p$ has a solution.

Question

Is this possible? Examples are appreciated

Answer 1

Do you know Legendre symbol? If $x^2\equiv a \pmod p$ for some $x$ we write $\Big({a\over p}\Big)=1$ else it is $-1$. There is a theorem $$\Big({a\over p}\Big)\Big({b\over p}\Big) =\Big({ab\over p}\Big) $$ and thus a conclusion.

Answer 2

We start by noting that, since the integers $\pmod p$ form a field, and since $p$ is odd, then there are exactly $\frac {p-1}2$ non-zero squares $\pmod p$. Hence there are the same number of non-zero non-squares.

Let $N$ denote a non-zero non-square $\pmod p$ . If we let $\{a_i\}_{i=1}^{(p-1)/2}$ run through the non-zero residues we remark that each of the products $N\times a_i$ must be distinct $\pmod p$. If $a_1$, say, is a square then $N\times a_1$ can not also be a square since in that case we'd have $N\times a^2\equiv b^2\implies N\equiv \left(ba^{-1}\right)^2$. Since there are $\frac {p-1}2$ squares we get all the $\frac {p-1}2$ non-squares as $N\times a^2$ for some $a$. If $N'$ is a non-square (possibly equal to $N$) Then $N\times N'$ can not be a non-square, since all the non-squares are accounted for. Hence it must be a square, and we are done.