How to find the solutions for the n-th root of unity in modular arithmetic where moduli $m$ is odd but not prime?

Question

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.

Answer 1

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).