0
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ $x \equiv x^{-1}$ is equivalent to $x^2 - 1 \equiv (x+1)(x-1) \equiv 0$. $\endgroup$ – 0x539 Jan 18 at 23:57
  • $\begingroup$ 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\ \ $ $\endgroup$ – Bill Dubuque Jan 19 at 0:28
  • $\begingroup$ @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)$? $\endgroup$ – Wallace Jan 19 at 0:32
  • $\begingroup$ @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. $\endgroup$ – 0x539 Jan 19 at 0:40
  • 1
    $\begingroup$ Cf. this question $\endgroup$ – J. W. Tanner Jan 20 at 17:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.