Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question

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

2 Answers 2

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

Taken from Vinogradov.

Proving this takes a chapter in Vinogradov's book.

share|improve this answer

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

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

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