Solvability of congruence.

Question

Suppose that the congruence $x^2\equiv-1\pmod{p}$ is solvable, where $p$ is a prime. Then show that the congruence $x^2\equiv-1\pmod{p^s}$ is solvable for any $s\geq2$. (Hint: Use induction argument.)

What I have done is that : $2$, $4$, $p^k$, $2p^k$ where $p$ is odd prime, has primitive root. So let's suppose $p$ is odd prime and primitive root of $p^s$ is $g$, then $g^{{p^{s-1}(p-1)}/2} \equiv -1 \pmod {p^{s}} $. I tried to find $x$ but I think I am on the wrong track. So I want to restart this problem, but I don't know how to start in a different way.

Answer 1

If $b^2\equiv a\pmod{p^k},$ i.e., $b^2=a+Ap^k$

If $p|A,$ we are done

Else

$(b+rp^s)^2=b^2+2brp^s+(rp^s)^2\equiv a+(A+2br)p^k\pmod{p^{k+1}}$ for $2k\ge k+1\iff k\ge1$

So, we need $A+2br\equiv0\pmod p$

As $(A,p)=(b,p)=1, $ we can always find $r\equiv-A(2b)^{-1}\pmod p$

Answer 2

The congruence $x^2\equiv-1\pmod{p^s}$ is solvable if and only if $(\Bbb{Z}/p^s\Bbb{Z})^{\times}$ has an element of order $4$.

If $p$ is an odd prime then the map $$(\Bbb{Z}/p^s\Bbb{Z})^{\times}\ \longrightarrow\ (\Bbb{Z}/p\Bbb{Z})^{\times}:\ x\ \longmapsto\ x^{p^{s-1}},$$ is a surjective group homomorphism. For $p=2$ the same is true for the map $$(\Bbb{Z}/2^s\Bbb{Z})^{\times}\ \longrightarrow\ (\Bbb{Z}/2^2\Bbb{Z})^{\times}:\ x\ \longmapsto\ x^{s^{s-2}}.$$

Answer 3

The base case: $x^2\equiv-1\pmod {p^1}$ is solvable is our hypothesis. So assume the equation is solvable modulo $p^s,$ and consider $x^2\equiv-1\pmod{p^{s+1}}.$
Let $n$ be an integer with $n^2\equiv-1\pmod{p^s}.$ And we try to find a solution to $x^2\equiv-1\pmod{p^{s+1}}$ in $n+p^sk$ for $k\in\mathbb Z.$ Then we see $(n+p^sk)^2\equiv n^2+2knp^s+p^{2s}k^2\equiv n^2+2knp^s\pmod{p^{s+1}}$ when $s\gt1.$ If $n^2\equiv-1\pmod{p^{s+1}},$ then let $k=0$ and we find a solution; otherwise, let $k\equiv\frac{(n^2+1)}{p^s}\cdot (2n)^{-1}\pmod p$ where $(2n)^{-1}$ is the inverse of $2n$ modulo $p.$ The $k$ as defined above satisfies our condition, and the induction is complete.

Hope this helps.