Cuando hace un polinomio se divide $x^k - 1$ algunos $k$?

Question

Dado un monic polinomio $f\in\mathbb{Z}[x]$, ¿cómo puedo determinar si hay un $k\in\mathbb{Z}^+$ tal que $f|(x^k-1)$?

Por ejemplo, $x^2-x+1$ divide $x^6-1$, pero $x^2-x-1$ no dividir cualquier $x^k-1$ (a menos que yo pierda mi marca!).

Yo también estaría interesado en encontrar la manera de responder a esta para otros con parámetros familias de polinomios, o el trabajo de más de $\mathbb{Q}[x]$—espero que el anterior para ser duro y el último sencillo.

Answer 1

Hay varios algoritmos conocidos por tales, basado en las propiedades de las raíces de la unidad, por ejemplo,

Véase, por ejemplo, los siguientes documentos.

F. Beukers , C. J. Smyth. Cyclotomic Puntos en las Curvas, Proc. Milennial Conferencia sobre la Teoría de números, Mayo 21-26, 2000, Urbana-Champaign, AK Peters (2001). (Sección 2)

Iskander Aliev, Chris Smyth. La resolución de ecuaciones algebraicas en las raíces de la unidad. (Sección 2.1)

R. J. Bradford y J. H. Davenport, Eficaz pruebas para cyclotomic polinomios.
Simbólico y Algebraico de Computación, Lecture Notes in Computer Science, 1989,
Volumen 358/1989, 244-251, DOI: 10.1007/3-540-51084-2_22

Resumen (de Bradford y Davenport)

Se presentan dos eficiente de las pruebas que determinan si un polinomio es cyclotomic, o es un producto de cyclotomics. El primer método utiliza el hecho de que todas las raíces de un cyclotomic polinomio son las raíces de la unidad, y el segundo, el hecho de que el grado de un cyclotomic polinomio es un valor de $\:\phi(n),$ algunos $n$. También podemos encontrar la cyclotomic los factores de cualquier polinomio.

Aquí está el primer método:

Answer 2

Los polinomios $x^n-1$ tiene como raíces de la compleja $n$th raíces de la unidad. Que, el factor de $$x^n - 1 = \prod_{d|n}\Phi_d(x)$$ donde $\Phi_d(x)$ es el $d$th cyclotomic polinomio. $\Phi_d(x)$ se define como $$\Phi_d(x) = \prod(x-\omega)$$ donde $\omega$ rangos de todas las primitivas $d$th raíces de la unidad en los números complejos.

Desde $\mathbb{Z}[x]$ es una única factorización de dominio, $f(x)\in\mathbb{Z}[x]$ divide algunos $x^k-1$ $\mathbb{Z}[x]$ (de hecho, en $\mathbb{Q}[x]$, por el Lema de Gauss,) si y sólo si es un producto de distintas cyclotomic polinomios.

Answer 3

Aquí está la respuesta corta: Para monic $f(x)\in\mathbb{Z}[x]$, $f(x)|x^k-1$ algunos $k$ si y sólo si cada raíz de $f(x)$ es distinta, tiene norma $1$.

Answer 4

Quieres productos de la cyclotomic polinomios para los divisores de $k$.