If $x^2\equiv b\pmod{p}$ is solvable, then $x^2\equiv b\pmod{p^2}$ is solvable?

68 Views Asked by At

If $x^2\equiv b\pmod{p}$ has a solution, does this imply $x^2\equiv b\pmod{p^2}$ has a solution too?

Assume $p$ is an odd prime.

1

There are 1 best solutions below

1
On

Yes, if $b\not\equiv 0\pmod{p}$. Proof:

$$\left(x^2-b\right)^2=\left(x^2+b\right)^2-b(2x)^2$$

So if $x^2\equiv b\pmod{p}$, then $\left(x^2+b\right)^2\equiv b(2x)^2\pmod{p^2}$. Since $\gcd(2x,p)=1$ (because $p$ is odd and $b\not\equiv 0\pmod{p}$), $\left(\left(x^2-b\right)\left(2x\right)^{-1}\right)^2\equiv b\pmod{p^2}$.


This way we can also get $x^2\equiv b\pmod{p^n}$ is solvable for all $n\ge 1$.

This also implies: if $p$ is an odd prime and $b\not\equiv 0\pmod{p}$, then if $x^2\equiv b\pmod{p^k}$ has a solution, then $x^2\equiv b\pmod{p^{n+k}}$ has a solution for all $n\ge 0$.