This interactive page has been made possible by the consent
of Waterloo Maple. The current version of the program are written using
Maple 8 and are being run on a SUN Ultra 1 workstation
(using solaris 2.5.1) in the
University of South Carolina.
We express our gratitude to the staff
of Waterloo Maple who graciously aided in improvements to the interface.
A Maplet interface to the algorithms is currently under development.
A prototype will soon be available via our
server at the URL
If you experience any problems with this Maplet, please send e-mail to
This page can be used to determine whether a given polynomial with
integer coefficients has a cyclotomic divisor.
To begin the program, choose one of the options "user-specified" or
"randomly-selected" below. If you choose "user-specified," type in
a user-defined polynomial to replace the example
indicated. If you choose the "randomly-selected" option, indicate
a bound for the number of non-zero terms, a bound for the degree,
and a bound for the absolute value of the coefficients. These
will be used to select a random polynomial (based on MAPLE's built-in
randpoly command) with non-zero constant term. The value of the
polynomial will be displayed in the output and not on this page.
To determine if the polynomial (user-specified or randomly-selected)
has a cyclotomic factor, click on the "Perform Test" button and
wait for the output.
How does one interpret the output?
The value "true" will be returned if the polynomial, say f(x), does have a
cyclotomic factor. The value "false" will be returned otherwise.
In the case of a true value, a statement will be given indicating
an integer m such that f(x) is divisible by the mth
cyclotomic polynomial. If f(x) is divisible by more than one cyclotomic
polynomial, only one such m is given; it will NOT necessarily
be the least such m.
What kind of polynomial can the algorithm handle?
The program will work for any polynomial f(x) with integer coefficients.
As indicated in the example below, f(x) can have large degree. In
general, the greater the degree of f(x) is, the longer the running time
will be; however, the degree does not affect the running time much
(whatever that means). Similarly, the size of the coefficients of
f(x) will affect the running time only slightly. The greatest
contribution to the running time comes from the number of non-zero terms
in f(x). The algorithm can easily handle polynomials with
100 non-zero terms and say degree 1000000 and coefficients with
absolute value bounded by 1000000 (this typically takes between 2
and 2.5 MAPLE CPU minutes).
This interactive page was developed by
Michael Filaseta and
The algorithm used here is based on work in progress by Filaseta and
where it is shown how to determine
whether a polynomial with integer coefficients has a cyclotomic
factor. The algorithm described in  is itself based largely
on a paper of Mann . Though a running version
of the program apparently exists, further improvements are being pursued
prior to public release of the code.
We anticipate making the code available at this location shortly.
As we are using the MAPLE language, access to MAPLE will be
necessary to run the downloaded programs.
The following includes references and current downloadable programs.
Presently there are no downloads. More will be listed as it
becomes available (and complete).
 M. Filaseta and A. Schinzel,
On testing the divisibility of lacunary polynomials by
 H. B. Mann,
On linear relations between roots of unity,
Mathematika, 12 (1965), 107-117.
Another Interactive Page:
Test the Irreducibility of 0-1 Polynomials