How to find positive integers where the multiplicative modular inverse is equal to itself for mod n?

Question

This a question sparked from Project Euler Question. I really devoted so much time to search an efficient solution however no output. What are some possibles theorems or formulas that are useful in that problem? I thought Euler's Totient function should have some role but no way to come up for me. Would you enlight me a bit if you know some trick?

I recently realized that for the formula $f(N)= x$ such that $x^2 \equiv 1$ $ mod(N)$ then if $N=2^e \mid e>2$ then we have recursive formula like $f(2^e)=2*f(2^{(e-2)})-1$. However there other numbers that are not exact composites of 2.

For example $f(8)=5$ and $f(16)=(f(8)*2)-1$ and $f(32)=(f(16)*2)-1$

Answer 1

Given $n$, I take it you are looking for $x$ such that $$ x^{2} \equiv 1 \pmod{n}. $$

1. First use the Chinese Remainder Theorem to reduce to the case when $n = p^{e}$ is a power of a prime $p$.
2. If $p = 2$, you only have $x = 1$ for $2^{e} = 2$, $x = \pm 1$ if $2^{e} = 4$, and in general $4$ solutions when $2^{e} \ge 8$, and these are $\pm 1, \pm 1 + 2^{e-1}$.
3. If $p$ is odd, there are the two solutions $\pm 1$.