$(\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.

Tags :

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