Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Given a monic polynomial $f\in\mathbb{Z}[x]$, how can I determine whether there is a $k\in\mathbb{Z}^+$ such that $f|(x^k-1)$?

For example, $x^2-x+1$ divides $x^6-1$, but $x^2-x-1$ does not divide any such $x^k-1$ (unless I miss my mark!).

I would also be interested in finding how to answer this for other parameterized families of polynomials, or working over $\mathbb{Q}[x]$—I expect the former to be hard and the latter easy.

share|cite|improve this question
This holds iff the roots of $f$ are distinct roots of unity, iff $f$ is a product of distinct cyclotomic polynomials. Are you looking for something more algorithmic than this? – Pete L. Clark Jun 2 '11 at 20:21
@Pete L. Clark: Yes, if possible: f might be large. – Charles Jun 2 '11 at 20:28
I've edited the question to specify that f must be monic to resolve these issues. – Charles Jun 2 '11 at 20:34
Good decision! I'll remove that previous comment now. – Eric Naslund Jun 2 '11 at 20:39
@Eric Naslund: If the answer's wrong, change the question. :) – Charles Jun 2 '11 at 21:49
up vote 15 down vote accepted

There are various algorithms known for such, based on properties of roots of unity, e.g.
enter image description here
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:

enter image description here enter image description here

share|cite|improve this answer
That's really great. I've coded up the Bradford & Davenport graeffe approach in a few versions. Question: is there a good way to determine the minimal n when the algorithm reports that f is a product of distinct cyclotomics? – Charles Jun 9 '11 at 3:54
B&D call this "easily computed" on the sentence straddling pp. 248-249 but I don't see how. – Charles Jun 9 '11 at 14:59

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.

share|cite|improve this answer

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$.

share|cite|improve this answer
Untrue. Dumb counterexample $2x-2$. You need the leading coefficient to be $\pm 1$. – David Speyer Jun 2 '11 at 20:25
More interesting point: Working in $\mathbb{Q}[x]$, the statement is untrue. Look at $x^2-(6/5)x+1$, whose roots are $(3 \pm 4i)/5$. These have norm $1$, but are not root of unity. The fact that "integer coefficients, monic, all roots have norm 1" implies "roots are roots of unity" IS true; this is a theorem of Kronecker. – David Speyer Jun 2 '11 at 20:27
@David: I like that second point! As I wrote, this was the "short answer" :) – Eric Naslund Jun 2 '11 at 20:29

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.