9
$\begingroup$

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?

$\endgroup$
2

1 Answer 1

13
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ thank you for idea to use CRT. Though some your calculations are incorrect ($3^2\equiv 1(mod\ 2^3)$), I appreciate your help. $\endgroup$ Feb 2, 2012 at 15:21
  • $\begingroup$ @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. $\endgroup$
    – Myself
    Feb 2, 2012 at 15:28

You must log in to answer this question.

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