Calculate the square roots of 1 modulo 4, 8 and 16.

Observe that $\varphi(4), \varphi(8)$ and $\varphi(16)$ can be calculated using Theorem 2.10 of Shoup: Let $p$ be a prime and $e$ be a positive integer. Then

$$\begin{aligned} \varphi(p^e) &= p^{e-1}(p-1) \\ \end{aligned}$$

In particular,

$$\begin{aligned} \varphi(2^2) &= 2^{2-1}(2-1) = 2 \\ \varphi(2^3) &= 2^{3-1}(2-1) = 4 \\ \varphi(2^4) &= 2^{4-1}(2-1) = 8 \\ \end{aligned}$$

However, note that the general formula for calculating

$\displaystyle\lvert (\mathbb{Z_n^*})^2 \rvert = \prod_{i=1}^{r}(\varphi(p_i^{e_i})/2) = \varphi(n)/2^r$

cannot be applied to this problem, for Theorem 2.26 of Shoup is only applicable when $p$ is odd.

In any case, it turns out the square roots are $\{1\}$ for modulo $4$, $\{1, 3, 5, 7\}$ for modulo $8$ and $\{1, 7, 9, 15\}$ for modulo $16$, as can be verified below.

for n in [4, 8, 16]:
    for i in xrange(1,n):
        r = i**2 % n
        if r == 1:
            print '%2d^2 &\equiv %d \pmod{%2d} \\\\' % (i, r, n)

Output:

$$\begin{aligned} 1^2 &\equiv 1 \pmod{ 4} \\ 3^2 &\equiv 1 \pmod{ 4} \\ 1^2 &\equiv 1 \pmod{ 8} \\ 3^2 &\equiv 1 \pmod{ 8} \\ 5^2 &\equiv 1 \pmod{ 8} \\ 7^2 &\equiv 1 \pmod{ 8} \\ 1^2 &\equiv 1 \pmod{16} \\ 7^2 &\equiv 1 \pmod{16} \\ 9^2 &\equiv 1 \pmod{16} \\ 15^2 &\equiv 1 \pmod{16} \\ \end{aligned}$$