Encontrar el número de factores irreducibles de $x^{63} - 1$

Question

Tengo que encontrar el número de factores irreducibles de $x^{63} - 1$ $\mathbb{F}_2$ utilizando el $2$-ciclotómicas cojunto modulo $63$.

¿Existe una manera de ver cuántos la ciclotómicas cosets son y cuál es su cardinalidad, que es más rápido que el cómputo directo?

Gracias.

Answer 1

Directo de cálculo es bastante rápido en este caso.

El poli. $x^{63} -1 $ factores como cyclotomic polys $\Phi_d$$d \mid 63$, por lo que $d = 1, 3, 9, 7, 21, 63.$

Los correspondientes grados de $\Phi_d$ $\phi(d)$: $1, 2, 6, 6, 12, 36$.

Para calcular cómo $\Phi_d$ factores $\mathbb F_2$, usted tiene que calcular el subgrupo de $(\mathbb Z/d)^{\times}$ generado por $2$; su índice es el número de factores.

Ya que todas las $d$ brecha $63$, e $2^6 = 64 \equiv 1 \bmod 63$, estos grupos, y los índices correspondientes, son bastante rápidos para calcular.

En última instancia, se encuentra $13$ factores (como ya estaba registrado en ALGEAN la respuesta).

Answer 2

Nota que $x^{p^n}-x\in\mathbb{Z}_p[x]$ es igual al producto de todos los factores irreducibles de grado $d$ tal que $d|n$. Supongamos que $w_p(d)$ es el número de factores irreducibles de grado $d$ $\mathbb{Z}_p$, entonces tenemos $$p^n=\sum_{d|n}dw_p(d)$ $ ahora utilizar la Fórmula de inversión de Mobius para obtener $$w_p(n)=\frac1{n}\sum_{d|n}\mu(\frac{n}{d})p^d.$ $ utilizar encima de identidad para obtener $$w_p(1)=p$ $ $$w_p(q)=\frac{p^q-p}{q}$ $ % $ de $$w_p(rs)=\frac{p^{rs}-p^r-p^s+p}{rs}$donde $q$ es un número primo y $r,s$ distintos números primeros .

Ahora es necesario calcular $w_2(1)+w_2(2)+w_2(3)+w_2(6)\color{#ff0000}{-{1}}$. Utilizando por encima de fórmulas se puede ver que la respuesta final es $13$.