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

by PerelMan   Last Updated September 12, 2019 04:20 AM

Let $p$ be a prime. With $()$ standing for Legendre symbol, prove $(\frac{a}{p})=(\frac{b}{p})$ iff $\exists c: b\equiv\ c^2a\ mod\ 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.



Related Questions


Finding $n$-th root of $p_1$ modulo $p_2$

Updated October 12, 2017 08:20 AM

Find pseudo-square mod $n$

Updated October 18, 2017 02:20 AM

Factoring out Kloosterman Sum

Updated February 22, 2019 08:20 AM

Jacobi symbol properties

Updated December 06, 2017 05:20 AM