¿Soluciones de la ecuación de $X^n-1\equiv 0$ (mod $m$)?

Question

¿Cuántas soluciones hace la ecuación $X^n-1\equiv 0$ (mod $m$) tiene? Es obvio eso si $m$ y $n$ son primos con $n|m-1$ entonces existen soluciones de $n$, de lo contrario sólo hay uno ($X=1$). ¿Hay alguna similar resultado arbitrario $m,n\in\mathbb{Z}$?

Para solucionar esto, creo que sería útil saber un resultado que es una consecuencia inmediata de la CRT, es decir: Si $m=p_1^{\alpha_1}\cdots p_r^{\alpha_r}$, entonces el $X^n-1\equiv 0$ (mod $m$) iff $X^n-1\equiv 0$ (mod $p_i^{\alpha_i}$) para cada $i=1\cdots r$.

Answer 1

Para el primefactors de $m$ es una función multiplicativa.

Considere la función $f_b(n) = b^n-1$ con algunas fijo determinado $b$ y la variación de $n$ y, a continuación, la divisibilidad $f_b(n) \equiv 0 \pmod p$ donde $p$ es un primer e $\gcd(b,p)=1$. Entonces sabemos de Fermat y Euler que este es periódica con $n$ por cada base $b$ y primefactor $p$ donde $\gcd(b,p)=1$. Si el sistema modular de la base es $m$ y no principales, pero compuesto, esto requiere un poco difícil notación para introducir un puñado de métodos de representación de los accesos directos.

Algunos métodos de representación de las utilidades
Así que vamos a definir una función: $$\lambda_b(p) = \text{least $n \gt 0$ such that $f_b(n)$ is divisible by $p$ }$$ Por ejemplo $\lambda_2(7) = 3$ porque en $2^n-1 = 2^3-1 = 7$ el más pequeño $n$ haciendo que la expresión divisible por $7$$n=3$.
Para más compacto notación que introducir alwo dos "operadores": $$\begin{array}{}[a:b] &= \left\{ \begin{array}{} 1 & \text{if $b$ divides $$} \\ 0 & \text{if $b$ does not divide $$} \end{array} \right. \\ \{a,p\} &= \text{exponente en la mayor potencia de p que divide a} \end{array}$$ (El último es a veces, por ejemplo en el Pari/GP-software, llamado el (padic)-"valoración")
Por ejemplo, $\{2^{21}-1,7\} = 2$ porque $2^{21}-1$ es divisible por $7^2$.

La próxima vamos a denotar el exponente, a lo que el primer $p$ se produce en $f_b(n)$ donde $n$ es el mínimo valor de: $$\alpha_b(p) = \{b^{\lambda_b(p)}-1,p\}$$ Así, por ejemplo, $\alpha_2(7) = \{2^3 - 1, 7\} = 1$ pero $\alpha_3(11) = \{3^5 - 1, 11\} = 2$ también $\alpha_2(1093) = \{2^{\lambda_2(1093)} - 1, 1093\} = 2$, la última ecuación se refiere a la llamada "Wieferich-prime" $p=1093$.

A continuación, puede ser demostrado, que para los impares primos $p \gt 2$ $$\{b^n -1, p\}= [n:\lambda_b(p)]\left(\alpha_b(p) + \{ n, p \} \right) \tag 1$$

---

Una versión de su fórmula, $m$ impar, $\gcd(X,m)=1$ .

Después de eso, es fácil encontrar una expresión para la su $X$ e (impar) $m$ medida de lo $\gcd(X,m)=1$. Vamos a escribir $m$ en su canónica primer factor de la descomposición: $$m =p_1^{w_1} \cdot p_2^{w_2} \cdot ... \cdot p_h^{w_h} \tag {2.1}$$ Por otro lado, mediante la canónica primefactor-descomposición de $f_b(n)$ hemos $$X^n-1 = p_1^{u_1} \cdot p_2^{u_2} \cdot ... \cdot p_h^{u_h} \\ \qquad = p_1^{[n:\lambda_X(p_1)] \cdot( \alpha_X(p_1) + \{n,p_1\})} \cdot p_2^{[n:\lambda_X(p_2)] \cdot( \alpha_X(p_2) + \{n,p_2\})} \cdot ... \cdot p_h^{[...](...)} \tag {2.2}$$ Por lo $n$ debe, primero, ser un múltiplo del mínimo común múltiplo de los $\lambda$'s $$n = t \cdot \text{lcm} (\lambda_X(p_1), \lambda_X(p_2), ... ,\lambda_X(p_h)) \tag 3$$

Vamos a suponer, que este está dado por algunos adecuado $n$.
Luego por otra parte $n$ también debe contener la primefactors $p_1$ $p_h$a dichos poderes, que los exponentes $w_1,w_2,w_3,...,w_h$ de la primefactors en $m$ también son, al menos, igualar el $u_1,u_2,u_3,...,u_h$. Así, para cada primefactor $p_k$ debemos tener: $u_k \ge w_k$ y de $$u_k = [n : \lambda_X(p_k)] \cdot ( \alpha_X(p_k) + \{n,p_k\} ) \tag 4$$ obtenemos la desigualdad $$\{n,p_k \} \ge w_k -\alpha_X(p_k) \tag 5$$

Ejemplo. Deje $m=2835 = 3^4 \cdot 5 \cdot 7$ $X = 26$ $m$ tenemos: $$\begin{array} {} w_1 = 4 & w_2 = 2 & w_3 = 1 \end{de la matriz} \\ $$ La expresión $X^n-1$ debe contener (al menos) el mismo primer factores. Así, tenemos: $$\begin{array} {} p_1=3 & \lambda_X(3)=2 & \alpha_X(3)=3 \\ p_2=5 & \lambda_X(5)=1 & \alpha_X(5)=2 \\ p_3=7 & \lambda_X(7)=6 & \alpha_X(7)=1 \\ \end{array}$$ Por lo $n$ debe ser (un múltiplo de) el lcm de todo lo que $\lambda$'s: $$n = t \cdot \text{lcm}(2,1,6)=6$$ De esto sabemos, que $n$ debe ser un múltiplo de $6$.

A continuación, debemos asegurarnos de que $n$ es tal que el primefactors se llevará a cabo en (al menos) la multiplicidades: $$\begin{array} {} u_1 \ge w_1=4 & \to & 3+\{n,3\} \ge 4 & \to & \{n,3\} \ge 1 \\ u_2 \ge w_2=2 & \to & 2+\{n,5\} \ge 2 & \to & \{n,5\} \ge 0 \\ u_3 \ge w_3=1 & \to & 1+\{n,7\} \ge 1 & \to & \{n,7\} \ge 0 \\ \end{array}$$ Desde la primera línea del último bloque tenemos que $n$ también debe contener la primefactor $3$, pero esto ya está dado por la hipótesis previa. El primefactors $5$ $7$ son automáticamente de suficiente exponentes, por lo que el ejemplo modular ecuación es válida para un mínimo de $n=6$ y obtenemos hecho $$\{26^6 - 1 , 2835\} = 1$$ que $X^n -1$ es divisible por $m$.

---

Incluso para $m$ (que contiene el primefactor 2) esto requiere una pequeña modificación con una extensión.

---

P. s. He hecho esto en un pequeño estudio; por desgracia, el texto aún no está muy bien terminado, pero podría ser útil para comprender lo anterior. Ver aquí

Answer 2

Si $m,n$ son primos y $X$ no es un múltiplo de $n$ puede utilizar el poco de Fermat teorema $$X^{k(n-1)}-1\equiv 0 \pmod n $m=k(n-1)$ no creo que existe una fórmula general.

Answer 3

A continuación todos los grupos son finitos y abelian. Para un anillo de $R$ grupo de invertir en elementos que denotan $R^*$. Para cualquier $n\in\mathbb{Z}$ y el grupo de $G$ denotamos $e_n(G):=\{g\in G:g^n=1\}$. Es evidente, que el $e_n(G)\leq G$ e si $G\simeq G_1\times\ldots\times G_l$ para algunos grupos de $G_1,\ldots,G_l$,$e_n(G)\simeq e_n(G_1)\times\ldots\times e_n(G_l)$. Desde $\mathbb{Z}_m=\mathbb{Z}_{-m}$, es suficiente para considerar el caso de $m>0$. Más $n\in\mathbb Z$.

Lema. Deje $n\in\mathbb Z$ $G$ ser finito cíclico grupo. A continuación,$|e_n(G)|=\gcd(n,|G|)$.

Prueba. Denotar $d=\gcd(n,|G|)$, $E=e_n(G)$. Como sabemos, $E\leq G$. Desde $G$ es cíclica y, a continuación, $E$ es cíclica, por lo tanto, $E=\langle a\rangle$ algunos $a\in G$$|E|=|a|$. Desde $a\in E$,$a^n=1$, por lo tanto $|a|\shortmid n$. Desde $a\in G$,$a^{|G|}=1$, por lo tanto $|a|\shortmid |G|$. Por lo tanto,$|a|\shortmid\gcd(n,|G|)$. Desde $G$ es cíclico y $d\shortmid |G|$, entonces existe subgrupo $E'\leq G$ orden $d$. Si $g\in E'$,$1=g^{|E'|}=g^d$, por lo tanto $g^n=1$$d\shortmid n$. Vamos a ver, que $E'\leq E$, por lo tanto $d=|E'|\shortmid|E|=|a|$. Por lo $|a|\shortmid d$$d\shortmid |a|$, lo que $|E|=|a|=d$ $\Box$.

Tenga en cuenta que el número de soluciones de la ecuación de $x^n\equiv 1\pmod m$ es igual a $|e_n(\mathbb{Z}_m^*)|$. Deje $m=p_1^{\alpha_1}\ldots p_l^{\alpha_l}$ donde $p_i$ - distintos números primos, $p_1=2$, $\alpha_i\in \mathbb{Z}_{\geq 0}$. Por el teorema del resto chino $\mathbb{Z}_m\simeq\mathbb{Z}_{p_1^{\alpha_1}}\times\ldots\times\mathbb{Z}_{p_l^{\alpha_l}}$, por lo tanto $\mathbb{Z}_m^*\simeq\mathbb{Z}_{p_1^{\alpha_1}}^*\times\ldots\times\mathbb{Z}_{p_l^{\alpha_l}}^*$$e_n(\mathbb{Z}_m^*)\simeq e_n(\mathbb{Z}_{p_1^{\alpha_1}}^*)\times\ldots\times e_n(\mathbb{Z}_{p_l^{\alpha_l}}^*)$. De tal manera $|e_n(\mathbb{Z}_m^*)|=\prod_{i=1}^l |e_n(\mathbb{Z}_{p_i^{\alpha_i}}^*)|$. Queda por encontrar $|e_n(\mathbb{Z}_{p_i^{\alpha_i}}^*)|$ todos los $i$. Si $p_i\neq 2$, entonces el grupo de $\mathbb{Z}_{p_i^{\alpha_i}}^*$ es cíclica, por lo tanto $$|e_n(\mathbb{Z}_{p_i^{\alpha_i}}^*)|=\gcd(n,|\mathbb{Z}_{p_i^{\alpha_i}}^*|)=\gcd(n,\phi(p_i^{\alpha_i})).$$ Deje $p_i=2$, es decir,$i=1$. Si $\alpha_1\in\{0,1\}$,$\mathbb{Z}_{2^{\alpha_1}}^*=\{1\}$$|e_n(\mathbb{Z}_{2^{\alpha_1}}^*)|=1$. Si $\alpha_1=2$, $\mathbb{Z}_{2^{\alpha_i}}^*$ es un grupo cíclico de orden $2$, por lo tanto $|e_n(\mathbb{Z}_{2^{\alpha_i}}^*)|=\gcd(n,2)$. Si $\alpha_i\geq 3$, $\mathbb{Z}_{2^{\alpha_i}}^*\simeq\mathbb{Z}_2\times\mathbb{Z}_{2^{\alpha_i-2}}$ y $$|e_n(\mathbb{Z}_{2^{\alpha_i}}^*)|=|e_n(\mathbb{Z}_2)| |e_n(\mathbb{Z}_{2^{\alpha_i-2}})|=\gcd(n,2)\gcd(n,2^{\alpha_i-2}).$$

Hemos demostrado el siguiente instrucción: Número de soluciones de la ecuación de $x^n\equiv 1\pmod m$ es igual a $c\prod_{i=2}^l \gcd(n,\phi(p_i^{\alpha_i}))$ donde $c=1$ si $\alpha_1\in\{0,1\}$, $c=\gcd(n,2)$ si $\alpha_1=2$ $c=\gcd(n,2)\gcd(n,2^{\alpha_1-2})$ si $\alpha_1\geq 3$.