# What are the solutions to $x+x^{-1}\bmod{n}\equiv2\bmod{n}$?

I've been playing around with this equation, and I don't have any solid footing to prove this is the case, but I do know the following.

• $$1$$ is always a solution.
• $$n-1$$ will only be a solution when $$n=4$$ because by definition $$(n-1)^{-1}\bmod{n}\equiv n-1\bmod{n}$$, and $$2(n-1)\bmod{n}\equiv n-2\bmod{n}$$. And, as we can see, $$3+3\bmod{4}\equiv2\bmod{4}$$.
• In a similar vein, $$2$$ will never be a solution because $$2^{-1}\bmod{n}\equiv\frac{n+1}{2}\bmod{n}$$. Then, $$2+\frac{n+1}{2}\bmod{n}\equiv\frac{n+5}{2}\bmod{n}$$, and setting $$\frac{n+5}{2}\bmod{n}\equiv2\bmod{n}$$ gives us $$n+5\bmod{n}\equiv5\bmod{n}\equiv4\bmod{n}$$. From here, it is plain to see that there are no non-trivial solutions for $$n$$.

Where can I go from here? Is my logic sound to begin with? Any help would be appreciated. Thank you!

• Note that multiplying both sides by $x$ would make your equation imply that $(x-1)^2\equiv 0 \pmod n$
– lulu
Commented Apr 4, 2022 at 14:08
• How would you solve $x + \frac1x = 2$ in other contexts? Try to do things as similarly as possible. Take care about whether the algebraic rules you're relying on apply in the "mod n" context. Commented Apr 4, 2022 at 14:10
• The occurence of "mod n" twice is confusing. Do you just mean $x+x^{-1}\equiv 2\mod n$ ? Commented Apr 4, 2022 at 16:00
• @Peter that is what I meant, sorry Commented Apr 4, 2022 at 17:16
• @AKemats Instead of apologizing in a comment, edit the question to correct it. Commented Aug 17, 2022 at 11:21

For $$1/x$$ mod $$n$$ to exist, we require $$x$$ relatively prime to $$n$$. Then "multiply by $$x$$" is bijective on the integers mod $$n$$. Follow Jaimie's hint; deduce \begin{align} x+\frac{1}{x} \equiv 2 \pmod{n} &\quad\Longleftrightarrow\quad x^2+1 \equiv 2x \pmod{n} \\& \quad\Longleftrightarrow\quad (x-1)^2 \equiv 0 \pmod{n} \end{align} If $$n$$ is square-free, this means $$x \equiv 1 \pmod{n}$$.
If $$n$$ is not square-free, then there are other solutions as well.
For example: if $$n=12 = 2^2\cdot 3$$, then we can take $$x-1 \equiv 0$$ or $$6$$, so $$x\equiv 1$$ or $$7\pmod{12}$$.
If $$n=216 = 2^3 3^3$$, then $$x-1 \equiv$$ one of $$2^3 3^3, 2^2 3^2, 2^3 3^2, 2^2 3^3$$, so $$x \equiv$$ one of $$1, 37, 73, 109$$.