If $3x^2\equiv1\bmod p$ then 3 is a quadratic residue

44 Views Asked by At

Unsure of how this implication has occurred. I know that if 3 is a QR then there exists $x^2\equiv3\bmod p$. However, how does this become $3x^2\equiv1\bmod p$?

2

There are 2 best solutions below

0
On

Since $\gcd(3,p) = 1$, 3 has a unique multiplicative inverse modulo $p$, say, it is $3^{-1}$. Then original congruence becomes $$ 3^{-1} \cdot 3 x^2 \equiv 3^{-1} \bmod p.$$ So $3^{-1}$ is a quadratic residue. Then apply $$ 1 = \left( \frac{1}p\right) = \left( \frac{3}p\right) \left( \frac{3^{-1}}p\right) $$ to get $\left( \frac{3}p\right) = 1$, i.e., 3 is a qudratic residue modulo $p$.

0
On

(Franz Lemmermeyer gave this away in the comments) $$3x^2\equiv1\bmod p$$ $$(3x)^2\equiv3\bmod p$$