TOPICS

# Cyclotomic Polynomial

A polynomial given by

 (1)

where are the roots of unity in given by

 (2)

and runs over integers relatively prime to . The prime may be dropped if the product is instead taken over primitive roots of unity, so that

 (3)

The notation is also frequently encountered. Dickson et al. (1923) and Apostol (1975) give extensive bibliographies for cyclotomic polynomials.

The cyclotomic polynomial for can also be defined as

 (4)

where is the Möbius function and the product is taken over the divisors of (Vardi 1991, p. 225).

is an integer polynomial and an irreducible polynomial with polynomial degree , where is the totient function. Cyclotomic polynomials are returned by the Wolfram Language command Cyclotomic[n, x]. The roots of cyclotomic polynomials lie on the unit circle in the complex plane, as illustrated above for the first few cyclotomic polynomials.

The first few cyclotomic polynomials are

 (5) (6) (7) (8) (9) (10) (11) (12) (13) (14)

The cyclotomic polynomial is illustrated above in the complex plane.

On any line through the origin, the value of a cyclotomic polynomial is strictly increasing outside the unit disk.

If is an odd prime, then

 (15) (16) (17) (18) (19) (20)

(Riesel 1994, p. 306). Similarly, for again an odd prime,

 (21) (22) (23)

For the first few remaining values of ,

 (24) (25) (26) (27) (28) (29) (30) (31)

(Riesel 1994, p. 307).

For a prime relatively prime to ,

 (32)

but if ,

 (33)

(Nagell 1951, p. 160).

An explicit equation for for squarefree is given by

 (34)

where is the totient function and is calculated using the recurrence relation

 (35)

with , where is the Möbius function and is the greatest common divisor of and .

The polynomial can be factored as

 (36)

Furthermore,

 (37) (38)

The coefficients of the inverse of the cyclotomic polynomial

 (39) (40)

can also be computed from

 (41) (42) (43)

where is the floor function.

For prime,

 (44)

i.e., the coefficients are all 1. The first cyclotomic polynomial to have a coefficient other than and 0 is , which has coefficients of for and . This is true because 105 is the first number to have three distinct odd prime factors, i.e., (McClellan and Rader 1979, Schroeder 1997). The smallest values of for which has one or more coefficients , , , ... are 0, 105, 385, 1365, 1785, 2805, 3135, 6545, 6545, 10465, 10465, 10465, 10465, 10465, 11305, ... (OEIS A013594).

It appears to be true that, for , if factors, then the factors contain a cyclotomic polynomial. For example,

 (45) (46)

This observation has been checked up to (Nicol 2000). If and are prime, then is irreducible.

Migotti (1883) showed that coefficients of for and distinct primes can be only 0, . Lam and Leung (1996) considered

 (47)

for prime. Write the totient function as

 (48)

and let

 (49)

then

1. iff for some and ,

2. iff for and ,

3. otherwise .

The number of terms having is , and the number of terms having is . Furthermore, assume , then the middle coefficient of is .

Resultants of cyclotomic polynomials have been computed by Lehmer (1936), Diederichsen (1940), and Apostol (1970). It is known that if , i.e., and are relatively prime (Apostol 1975). Apostol (1975) showed that for positive integers and and arbitrary nonzero complex numbers and ,

 (50)

where is the greatest common divisor of and , is the totient function, is the Möbius function, and the product is over the divisors of . If and are distinct primes and , then (50) simplifies to

 (51)

The following table gives the resultants , (OEIS A054372).

 1 2 3 4 5 6 7 1 0 2 2 0 3 3 1 0 4 2 2 1 0 5 5 1 1 1 0 6 1 3 4 1 1 0 7 7 1 1 1 1 1 0

The numbers of 1s in successive rows of this table are given by 0, 0, 1, 1, 3, 3, 5, 4, 6, 7, 9, ... (OEIS A075795).

The cyclotomic polynomial has the particularly nice Maclaurin series

 (52)

whose coefficients 1, 0, , , 0, 1, 1, 0, , , ... (OEIS A010892) are given by solving the recurrence equation

 (53)

with (Wolfram 2002, p. 128), giving the explicit form

 (54)

Interestingly, any sequence satisfying the linear recurrence equation

 (55)

can be written as

 (56)

Aurifeuillean Factorization, Gauss's Cyclotomic Formula, Lucas's Theorem, Möbius Inversion Formula, Primitive Root of Unity, Root of Unity

## Related Wolfram sites

http://functions.wolfram.com/Polynomials/Cyclotomic/

## References

Apostol, T. M. "Resultants of Cyclotomic Polynomials." Proc. Amer. Math. Soc. 24, 457-462, 1970.Apostol, T. M. "The Resultant of the Cyclotomic Polynomials and ." Math. Comput. 29, 1-6, 1975.Beiter, M. "The Midterm Coefficient of the Cyclotomic Polynomial ." Amer. Math. Monthly 71, 769-770, 1964.Beiter, M. "Magnitude of the Coefficients of the Cyclotomic Polynomial ." Amer. Math. Monthly 75, 370-372, 1968.Bloom, D. M. "On the Coefficients of the Cyclotomic Polynomials." Amer. Math. Monthly 75, 372-377, 1968.Brent, R. P. "On Computing Factors of Cyclotomic Polynomials." Math. Comput. 61, 131-149, 1993.Carlitz, L. "The Number of Terms in the Cyclotomic Polynomial ." Amer. Math. Monthly 73, 979-981, 1966.Conway, J. H. and Guy, R. K. The Book of Numbers. New York: Springer-Verlag, 1996.de Bruijn, N. G. "On the Factorization of Cyclic Groups." Indag. Math. 15, 370-377, 1953.Dickson, L. E.; Mitchell, H. H.; Vandiver, H. S.; and Wahlin, G. E. Algebraic Numbers. Bull Nat. Res. Council, Vol. 5, Part 3, No. 28. Washington, DC: National Acad. Sci., 1923.Diederichsen, F.-E. "Über die Ausreduktion ganzzahliger Gruppendarstellungen bei arithmetischer Äquivalenz." Abh. Math. Sem. Hanisches Univ. 13, 357-412, 1940.Lam, T. Y. and Leung, K. H. "On the Cyclotomic Polynomial ." Amer. Math. Monthly 103, 562-564, 1996.Lehmer, E. "On the Magnitude of the Coefficients of the Cyclotomic Polynomial." Bull. Amer. Math. Soc. 42, 389-392, 1936.McClellan, J. H. and Rader, C. Number Theory in Digital Signal Processing. Englewood Cliffs, NJ: Prentice-Hall, 1979.Migotti, A. "Zur Theorie der Kreisteilungsgleichung." Sitzber. Math.-Naturwiss. Classe der Kaiser. Akad. der Wiss., Wien 87, 7-14, 1883.Nagell, T. "The Cyclotomic Polynomials" and "The Prime Divisors of the Cyclotomic Polynomial." §46 and 48 in Introduction to Number Theory. New York: Wiley, pp. 158-160 and 164-168, 1951.Nicol, C. "Sums of Cyclotomic Polynomials." Apr. 26, 2000. http://listserv.nodak.edu/cgi-bin/wa.exe?A2=ind0004&L=nmbrthry&T=0&F=&S=&P=2317.Riesel, H. "The Cyclotomic Polynomials" in Appendix 6. Prime Numbers and Computer Methods for Factorization, 2nd ed. Boston, MA: Birkhäuser, pp. 305-308, 1994.Schroeder, M. R. Number Theory in Science and Communication: With Applications in Cryptography, Physics, Digital Information, Computing, and Self-Similarity, 3rd ed. New York: Springer-Verlag, p. 245, 1997.Séroul, R. "Cyclotomic Polynomials." §10.8 in Programming for Mathematicians. Berlin: Springer-Verlag, pp. 265-269, 2000.Sloane, N. J. A. Sequences A013594, A010892, A054372, and A075795 in "The On-Line Encyclopedia of Integer Sequences."Trott, M. "The Mathematica Guidebooks Additional Material: Graphics of the Argument of Cyclotomic Polynomials." http://www.mathematicaguidebooks.org/additions.shtml#N_2_03.Vardi, I. Computational Recreations in Mathematica. Redwood City, CA: Addison-Wesley, pp. 8 and 224-225, 1991.Wolfram, S. A New Kind of Science. Champaign, IL: Wolfram Media, 2002.

## Referenced on Wolfram|Alpha

Cyclotomic Polynomial

## Cite this as:

Weisstein, Eric W. "Cyclotomic Polynomial." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/CyclotomicPolynomial.html