3
$\begingroup$

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.

$\endgroup$
4
  • $\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, 2020 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, 2020 at 18:33
  • $\begingroup$ @Fawkes4494d3 later in the question OP says they want distinct square roots modulo $N$ $\endgroup$ Jul 2, 2020 at 18:35
  • $\begingroup$ Cf. this question $\endgroup$ Jul 2, 2020 at 22:00

2 Answers 2

4
$\begingroup$

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.

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

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

$\endgroup$
2
  • 1
    $\begingroup$ 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 $\endgroup$ Nov 18, 2023 at 12:38
  • $\begingroup$ Welcome to MSE! Thank you for pointing this out. I will fix the above answer. I think your answer will probably be deleted as that seems to be the consensus among the reviewers. I personally think you have answered the question, but in future your post might be better received if you don't write anything about how you wanted to comment, and perhaps give a slightly more detailed answer. (even though your answer is really no less detailed than the accepted answer above... sometimes that's the way the cookie crumbles) $\endgroup$ Nov 18, 2023 at 15:20

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .