# Knowing prime factorization of $n$ determine number of solutions to $x^2 \equiv 1\ (\textrm{mod}\ n)$ [closed]

How to determine number of solutions to $x^2 \equiv 1\ (\textrm{mod}\ n)$, when I know prime factorization of $n$?

-

## closed as off-topic by Bruno Joyal, user1337, Hagen von Eitzen, Jyrki Lahtonen♦, T. Bongers Nov 5 '13 at 22:50

This question appears to be off-topic. The users who voted to close gave this specific reason:

• "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – Bruno Joyal, user1337, Hagen von Eitzen
If this question can be reworded to fit the rules in the help center, please edit the question.

I assume the first step is to rewrite this as $n|(x+1)(x-1)$. –  Mike Nov 2 '13 at 14:39
Hi @Machiawliczny, could you please give some more context? For example, do you know about the Chinese Remainder Theorem? –  Johannes Kloos Nov 2 '13 at 18:01
possible duplicate of Roots of $x^2 -1$ in $\mathbb{Z}\_m$ with $m$ not a prime number. To tell you the truth I was surprised not to find an older dup. –  Jyrki Lahtonen Nov 3 '13 at 10:19

Assume $n=2^ap_1^{a_1}\dots p_m^{a_m}$. Then the number of solutions are $2^m$ if $a=0$ or if $a=1$; $2^{m+1}$ if $a=2$ and $2^{m+2}$ if $a\geq 3$.

Proving this takes a chapter in Vinogradov's book.

-

Let me see if I can expand on my comment and try to prove Ivan's answer. As I said in the comment, if

$$x^2\equiv1\pmod n$$ $$x^2-1=(x+1)(x-1)\equiv0 \pmod n$$ $$n|(x+1)(x-1)$$

For each prime power factor $p_m^{a_m},p\ne2$, either $p_m^{a_m}|x-1$ or $p_m^{a_m}|x+1$. If $n$ is odd, there are $2$ choices for each prime power. Each set of choices gives $1$ solution $\pmod n$ by the Chinese remainder theorem, so there are $2^m$ possibilities.

$2$ is different since $x-1\equiv x+1\pmod 2$. If $2^a|p$ and $a=1, x\equiv 1\pmod2$ is our only choice. If $a=2$, then either $x-1$ or $x+1$ is divisible by $4$, so $2$ choices for $x\pmod4$. If $a>2$, since $\gcd(x-1,x+1)|2$ we have either

$$2^{a-1}|x-1$$ $$x\equiv1\pmod{2^{a-1}}$$ $$x\equiv1,2^{a-1}+1\pmod{2^a}$$ $$\text{or}$$ $$2^{a-1}|x+1$$ $$x\equiv-1\pmod{2^{a-1}}$$ $$x\equiv-1,2^{a-1}-1\pmod{2^a}$$

so $4$ choices for $x\pmod{2^a}$.

-
All primes are odd except 2, which is the oddest of all. – D.E.Knuth. –  lhf Dec 10 '13 at 4:43