Решение сравнения, количество решений

[myf]

Если какой-нибудь способ решения сравнения $x^n = 1 (\mod m)$. $n$ и $m$ любые числа. И можно ли как-то узнать число его решений, не решая его. Заранее спасибо!

[maxal]

Решения можно найти рассмотрением сравнения по степеням простых, входящих в разложение m на простые. Решения по модулю степени простого проще искать, используя факт существования примитивного корня. А решения по различным модулям комбинируются с помощью китайской теоремы об остатках.

Общее число различных решений равно $\prod_{i=1}^r$ НОД$(n,(p_i-1) p_i^{k_i-1})$, где $m=p_1^{k_1}\dots p_r^{k_r}$ - разложение m на простые.

[myf]

Большое спасибо за помощь!