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.

  • $\begingroup$ Welcome to Mathematics Stack Exchange. For $2^n$ with $n\ge3$, it's $4$. Generally, it depends how many factors $N$ has $\endgroup$ Jul 2 '20 at 18:29
  • $\begingroup$ 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$. $\endgroup$ Jul 2 '20 at 18:33
  • $\begingroup$ @Fawkes4494d3 later in the question OP says they want distinct square roots modulo $N$ $\endgroup$ Jul 2 '20 at 18:35
  • $\begingroup$ Cf. this question $\endgroup$ 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.