Next is what I have worked out to the moment.

$1$ and $-1$ are roots for all $n$.

$x \in \mathbb{Z}/n\mathbb{Z},\ $ $x^2\equiv1 \Leftrightarrow (x-1)(x+1)\equiv0 \Leftrightarrow \exists k \in \mathbb{Z}/n\mathbb{Z}: k(k+2)\equiv0 $. But how can it be applied to find other roots?

up vote 7 down vote accepted

(I'd have to check the details in the following but it provides some rough ideas.)

Write $n = \prod_i p_i^{\nu_i}$ and use the Chinese remainder theorem to obtain a system of equations

$$ x^2 \equiv 1 \pmod{p_i^{\nu_i}}$$ Of course, for every $p_i$, $x=\pm 1$ provides a solution. Based on some quick calculations, I think that:

  • If $p_i>2$, these are the only solutions.
  • If $p_i=2$ and $\nu_2 \geq 3$, then there are 4 solutions.
  • If $p_i=2$ and $\nu_2 = 2$, then $x=\pm 1$ are solutions.
  • If $p_i=2$ and $\nu_2 = 1$, there is $1$ solution, because $+1 = -1$.

To confirm this: investigate when a prime power can divide two numbers that differ by $2$, i.e when $p_i^{\nu_i} \mid (x+1)(x-1)$.

We may then use the Chinese remainder theorem to reassemble the solutions to find solutions mod $n$: each combination of solutions modulo the prime-powers will uniquely determine a solution mod $n$.

So the number of solutions is (where $\omega(n)$ is the number of distinct prime factors of $n$):

  • $2^{\omega(n)}$ if $n$ is odd or $\nu_2 = 2$.
  • $2^{\omega(n)+1}$ if $\nu_2 \geq 3$
  • $2^{\omega(n)-1}$ if $\nu_2 = 1$

A proof of the above can be based on theorem 4.19 and 4.20 in Basic Algebra vol 1, by N. Jacobson, discussing the structure of $U_{p^\nu}$, this is the group of units in $\mathbb Z/p^\nu \mathbb Z$: it is cyclic if $p>3$, $p^\nu=2$ or $p^\nu=4$ and isomorphic to $C_2\times C_{2^{\nu-2}}$ if $p=2$ and $\nu\geq 3$.

  • thank you for idea to use CRT. Though some your calculations are incorrect ($3^2\equiv 1(mod\ 2^3)$), I appreciate your help. – Sergey Filkin Feb 2 '12 at 15:21
  • @Sergey Filkin: Yes, this is the case where $p_i=2$ and $\nu_i\geq 3$, there are 4 solutions in this case: $\pm 1$ and $p_i^{\nu_i-1} \pm 1$. There were some mistakes in the initial post but I hope my edit fixed it. – Myself Feb 2 '12 at 15:28

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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