Exercise 3.3.10 (Solvability of $x^2 \equiv k \pmod 4$)

Proof. If $k$ is odd, the congruence $x^2\equiv 1(\mathit{mod}2)$ has exactly one solution, since $0^2\equiv 0\not\equiv k,1^2\equiv 1\equiv k(\mathit{mod}2)$.

Suppose that $x^2\equiv k(\mathit{mod}{2}^2)$ is solvable. Since $k$ is odd, and $2\mid x^2-k$, $x$ is also odd, so $x=2l+1$ for some integer $l$. Therefore $k\equiv x^2={(2k+1)}^2=4k^2+4k+1\equiv 1(\mathit{mod}4)$, so $k\equiv 1(4)$.

Conversely, if $k\equiv 1(\mathit{mod}4)$, the congruence $x^2\equiv k(\mathit{mod}{2}^2)$ is equivalent to $x^2\equiv 1(\mathit{mod}4)$. Since $0^1\equiv 0,1^2\equiv 1,2^2\equiv 0,3^2\equiv 1(\mathit{mod}4)$, the solutions are $1,3$.

The congruence $x^2\equiv k(\mathit{mod}{2}^2)$ is solvable if and only if $k\equiv 1(\mathit{mod}4)$, in which case there are two solutions. □