Suppose that gcd($a,p$) = gcd($b,p$) = 1, and neither of the congruences $x^2 \equiv a$ mod $p$ or $x^2 \equiv b$ mod $p$ has a solution. Show that $x^2 \equiv ab$ mod $p$ does have a solution.
- Having a tough time with this problem, went to my professor for some advice and he hinted at utilizing quadratic reciprocity and Lengendre symbol. I understand the formula for quadratic reciprocity but don't understand how this ties in with Legendre and helps solve this problem. Any help is greatly appreciated, thank you in advance.
You can avoid quadratic reciprocity and use Euler's criterion: $$ a^{\frac{p-1}{2}} \equiv -1, \quad b^{\frac{p-1}{2}} \equiv -1 \implies (ab)^{\frac{p-1}{2}} \equiv (-1)(-1)=1 \bmod p $$ and so $ab$ is a quadratic residue.