# 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, 2020 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, 2020 at 18:33
• @Fawkes4494d3 later in the question OP says they want distinct square roots modulo $N$ Jul 2, 2020 at 18:35
• Jul 2, 2020 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, 2^{r - 1} - 1, 2^{r - 1} + 1, 2^r - 1$$ mod $$2^r$$, respectively.

This again is an exercise of Hensel's lemma.

• How do you combine the individual results of CRT at prime powers to the result for $n$? Dec 18, 2022 at 9:35

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)$$.

• This does not provide an answer to the question. Once you have sufficient reputation you will be able to comment on any post; instead, provide answers that don't require clarification from the asker. - From Review Nov 18, 2023 at 12:38