Square root of 1 modulo N

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.

• Welcome to Mathematics Stack Exchange. For $2^n$ with $n\ge3$, it's $4$. Generally, it depends how many factors $N$ has Jul 2 '20 at 18:29
• Maybe define $A=\{x \in \{1,2, \cdots, N-1\} : x^2\equiv 1 (mod \ N)\}$ because if $x\in \mathbb{Z}$, then there are infinitely many such $x$, of the form $Nk\pm 1$, where $k\in \mathbb{Z}$ in which case, maybe you would be interested in the natural density of the set of such $x$. Jul 2 '20 at 18:33
• @Fawkes4494d3 later in the question OP says they want distinct square roots modulo $N$ Jul 2 '20 at 18:35
• Jul 2 '20 at 22:00

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, 3, 5, 7$$ mod $$8$$, respectively.

This again is an exercise of Hensel's lemma.