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} \]