# How many solutions does $x \equiv x^{-1} \pmod n$ have?

How many solutions does $$x \equiv x^{-1} \pmod n$$ have?

$$n$$ is defined to be a positive integer,

What I believe the solution will be is along the lines of 2 cases:

When $$n = 1$$, the set of solutions will just be $$x \in \mathbb Z$$ because $$x \equiv x^{-1} \pmod 1$$ can be rewritten as $$x - x^{-1} \equiv 0 \pmod 1$$ and mod 1 of any integer will always reduce to 0

When $$n \gt 1$$, I know we have to apply Chinese Remainder Theorem somehow, I just do not know how to approach this though. We can claim by the Fundamental Theorem of Arithmetic that $$n = p_{1}^{k_{1}}p_{2}^{k_{2}}...p_{l}^{k_{l}}$$ where $$p_{i}$$ are prime numbers. How would I continue?$$\\$$ I thought maybe multiplying both sides by $$x$$ and rearranging to get $$x^{2} \equiv 1\pmod n$$ could be of some help but I couldn't get any further.

• $x \equiv x^{-1}$ is equivalent to $x^2 - 1 \equiv (x+1)(x-1) \equiv 0$. – 0x539 Jan 18 at 23:57
• Hint: $(x\!-\!1,x\!+\!1) = (x\!-\!1,2)$ is coprime to odd primes $p,\,$ so $\,p^n\mid (x\!-\!1)(x\!+\!1)\,\Rightarrow\,p^n\mid x-1$ or $\,p^n\mid x+1\ \$ – Bill Dubuque Jan 19 at 0:28
• @0x539 how does that help? I get that part but I do not understand where to go from that. I actually went down that path but I didn't know how to pursue from there, would we could consider separate cases for $(x+1)$ and $(x-1)$? – Wallace Jan 19 at 0:32
• @Wallace First if $n$ is prime it shows that the only solution are $1, -1$. If $n$ is composite then $x+1$ and $x-1$ need to contain all prime factors of $n$. This helps somewhat, for example if $n$ is an odd prime power then the only solutions are again $1, -1$. I don't claim this will provide a full solution but it seems promising to me. – 0x539 Jan 19 at 0:40
• – J. W. Tanner Jan 20 at 17:01