How to test if a polynomial is cyclotomic, i.e. divide $x^k - 1$ for some $k$?

Solution 1:

There are various algorithms known for such, based on properties of roots of unity, e.g.

See for example the following papers.

F. Beukers , C. J. Smyth. Cyclotomic Points on Curves, Proc. Milennial Conference on Number Theory, May 21–26, 2000, Urbana-Champaign, AK Peters (2001). (Section 2)

Iskander Aliev, Chris Smyth. Solving algebraic equations in roots of unity. (Section 2.1)

R. J. Bradford and J. H. Davenport, Effective tests for cyclotomic polynomials.
Symbolic and Algebraic Computation, Lecture Notes in Computer Science, 1989,
Volume 358/1989, 244-251, DOI: 10.1007/3-540-51084-2_22

Abstract (from Bradford and Davenport)

We present two efficient tests that determine if a given polynomial is cyclotomic, or is a product of cyclotomics. The first method uses the fact that all the roots of a cyclotomic polynomial are roots of unity, and the second the fact that the degree of a cyclotomic polynomial is a value of $\:\phi(n),$ for some $n$. We can also find the cyclotomic factors of any polynomial.

Here is the first method:

Solution 2:

The polynomials $x^n-1$ have as roots the complex $n$th roots of unity. They factor as $$x^n - 1 = \prod_{d|n}\Phi_d(x)$$ where $\Phi_d(x)$ is the $d$th cyclotomic polynomial. $\Phi_d(x)$ is defined as $$\Phi_d(x) = \prod(x-\omega)$$ where $\omega$ ranges over all primitive $d$th roots of unity in the complex numbers.

Since $\mathbb{Z}[x]$ is a unique factorization domain, $f(x)\in\mathbb{Z}[x]$ divides some $x^k-1$ in $\mathbb{Z}[x]$ (in fact, in $\mathbb{Q}[x]$, by Gauss's Lemma) if and only if it is a product of distinct cyclotomic polynomials.

Solution 3:

Here is the short answer: For monic $f(x)\in\mathbb{Z}[x]$, we have $f(x)|x^k-1$ for some $k$ if and only if each root of $f(x)$ is distinct, has norm $1$.

Solution 4:

You want products of the cyclotomic polynomials for the divisors of $k$.