Square root of 1 modulo N

Question

Given a positive integer N, how do we compute $card(A)$ where $A = \{x\in\mathbb{Z}, 0 < x < N \mid x^{2}\equiv1\pmod N\}$, when the prime factorization of N is known.
In other words, how many square roots of 1 modulo N exist?
We know that when N is prime, there are only two square roots -> 1 and -1 (except for N = 2, where 1 and -1 coincide).
So what what the equation for generic N looks like? A formal proof would be appreciated.
I don't need to find these roots (this task can be accomplished by using EEA on every pair of factors of N), I need only to compute their amount.

Answer 1

By chinese remainder theorem, we only need to consider the case where $N = p^r$ is a prime power.

If $p$ is odd, then there are exactly two square roots of $1$. This can be seen from Hensel's lemma or the fact that $\Bbb Z/N\Bbb Z$ is cyclic in this case.

If $p = 2$, then it depends on the value of $r$.

$r = 1$: there is $1$ root ($1$).

$r = 2$: there are $2$ roots ($1, 3$).

$r \geq 3$: there are $4$ roots, congruent to $1, 2^{r - 1} - 1, 2^{r - 1} + 1, 2^r - 1$ mod $2^r$, respectively.

This again is an exercise of Hensel's lemma.

Answer 2

In @WhatsUp's analysis the case of $p = 2$ has a small error for $r \ge 3$. It is true that there are four roots, but they are $1$, $(2^{r-1} - 1)$, $(2^{r-1}+1)$ and $(2^r - 1)$.