How to find the solutions for the n-th root of unity in modular arithmetic where moduli $m$ is odd but not prime? I am about to solve the following congruence for $x$:
$$\begin{align*}
x^n\equiv x&\pmod m\quad(1)\end{align*}$$
Where $n\in\mathbb{N},$ and $n$ is coprime to $m$ and $x\in \{0,1,2\dots,m-1\}$.
Another question here, which is almost similar to this one, has already answers for $m\in\text{Primes}$. But I would like to consider a wider case where $m$ can be any odd number which is coprime to $n$. Please guide me if you know of methods for solving this congruence. I think I have to start with checking to see if a solution exists for a given $m$ and $n$.
Examining all possible $x$ is not an option because $m$ is supposedly very big integer.
As a small integer illustration I have calculated (programmatically) $x=69, 70, 91, 92$ for the following congruence (total 4 solutions):
$$\begin{align*}
x^{158}\equiv x&\pmod {161}\quad(2)\end{align*}$$
please note that we cannot reduce $(2)$ to the following form:
$$\begin{align*}
x^{157}\equiv 1&\pmod {161}\quad(3)\end{align*}$$
because it seemingly has no solutions because solutions above have no modular inverse modulo $161$.
#EDIT 1:
Using chinese remainder theorem is not an option here. Because $p$, as I have mentioned above, is supposed to be a very large integer for which we don't know the factors.
 A: As $161 = 7 \cdot 23$, a modular equation modulo $161$ can be determined (by the Chinese Remainder Theorem) from its behavior mod $7$ and mod $23$.
The theme is that you solve this for each prime separately and then combine the answers together.
For your particular example, solving $x^{158} \equiv x \bmod 161$ reduces to solving
$$\begin{align}
x^{158} &\equiv x \bmod 7, \\
x^{158} &\equiv x \bmod 23.
\end{align}$$
By Fermat's Little Theorem, these are equivalent to
$$\begin{align}
x^{2} &\equiv x \bmod 7, \\
x^{4} &\equiv x \bmod 23.
\end{align}$$
Using your preferred methods (possibly using the ideas in this question and its answers), you can see that the answers to these are
$$\begin{align}
x &\equiv 0, 1 \bmod 7, \\
x &\equiv 0, 1 \bmod 23.
\end{align}$$
As $4 \cdot 23 \equiv 1 \bmod 7$ and $10 \cdot 7 \equiv 1 \bmod 23$, the Chinese Remainder Theorem indicates that the solutions to these pair of congruences take the form
$$ a \cdot 7 \cdot 10 + b \cdot 23 \cdot 4 \bmod 161,$$
where $a, b \in \{0, 1\}$. These are
$$0, 1, 70, 92.$$
(I'll note that your solutions $69$ and $91$ are not actually solutions to the congruence).
