$(\frac{a}{p})=(\frac{b}{p})$ iff $\exists c: b\equiv\ c^2a\pmod p$ and $(c,p)=1$.

Question

Let $p$ be a prime. With $()$ standing for Legendre symbol, prove $(\frac{a}{p})=(\frac{b}{p})$ iff $\exists c: b\equiv\ c^2a\pmod p$ and $(c,p)=1$.

Working out the 3 possible cases $\Leftarrow)$ is trivial. In the $\Rightarrow)$ I proved the result for the cases $(\frac{a}{p})=(\frac{b}{p})=0$ or $(\frac{a}{p})=(\frac{b}{p})=1$.

I need some help for the last case $(\frac{a}{p})=(\frac{b}{p})=-1$.

Any hints or even a more clever way to prove this equivalence is appreciated.

Thank you.

Answer 1

I think a better way to prove $\Rightarrow$) is:

if $(\frac{a}{p})=(\frac{b}{p})=0$ then $b\equiv a\ mod\ p$ then we take $c=1$.

if $(\frac{a}{p})=(\frac{b}{p})\ne0$ then $a$ is invertible modulo $p$. Therefore $(\frac{b}{p})(\frac{a^{-1}}{p})=(\frac{a}{p})(\frac{a^{-1}}{p})=(\frac{1}{p})=1$, thus the existence of $c$ such that $ba^{-1}\equiv c^2\ mod\ p$.

Answer 2

Hint Let $$A=\{ x : (\frac{x}{p})=1 \} \\ B=\{ x : (\frac{x}{p})=-1 \} $$

If $(\frac{a}{p})=-1$ show that $f:A \to B, f(x)=ax$ is well defined and one to one. Deduce from here that $f$ is onto.

Therefore, there exists some $x \in A$ such that $f(x)=b$.