View source for Cyclotomic polynomial

{{short description|Irreducible polynomial whose roots are nth roots of unity}}
In [[mathematics]], the''' ''n''th cyclotomic polynomial''', for any [[positive integer]] ''n'', is the unique [[irreducible polynomial]] with integer [[Coefficient|coefficients]] that is a [[divisor]] of <math>x^n-1</math> and is not a divisor of <math>x^k-1</math> for any {{nowrap|''k'' < ''n''.}} Its [[root of a function|roots]] are all ''n''th [[primitive root of unity|primitive roots of unity]] 
<math>
e^{2i\pi\frac{k}{n}}
</math>, where ''k'' runs over the positive integers less than ''n'' and [[coprime integers|coprime]] to ''n'' (and ''i'' is the [[imaginary unit]]). In other words, the ''n''th cyclotomic polynomial is equal to
:<math>
\Phi_n(x) =
\prod_\stackrel{1\le k\le n}{\gcd(k,n)=1}
\left(x-e^{2i\pi\frac{k}{n}}\right).
</math>

It may also be defined as the [[monic polynomial]] with integer coefficients that is the [[minimal polynomial (field theory)|minimal polynomial]] over the [[Field (mathematics)|field]] of the [[rational number]]s of any [[Primitive root of unity|primitive ''n''th-root of unity]] (<math> e^{2i\pi/n} </math> is an example of such a root).

An important [[Relation (mathematics)|relation]] linking cyclotomic polynomials and primitive roots of unity is
:<math>\prod_{d\mid n}\Phi_d(x) = x^n - 1,</math>
showing that <math>x</math> is a root of <math>x^n - 1</math> if and only if it is a ''d''{{space|hair}}th primitive root of unity for some ''d'' that divides ''n''.<ref>{{citation
| last=Roman 
| first=Stephen
| title=Advanced Linear Algebra | edition=Third 
| series=[[Graduate Texts in Mathematics]] | publisher  = Springer 
| date=2008| pages= 
| isbn=978-0-387-72828-5 
| at = p. 465 §18
|author-link=Steven Roman}}</ref>

==Examples==

If ''n'' is a [[prime number]], then 
:<math>\Phi_n(x) = 1+x+x^2+\cdots+x^{n-1}=\sum_{k=0}^{n-1} x^k.</math>
If ''n'' = 2''p'' where ''p'' is a [[prime number]] other than 2, then
:<math>\Phi_{2p}(x) = 1-x+x^2-\cdots+x^{p-1}=\sum_{k=0}^{p-1} (-x)^k.</math>

For ''n'' up to 30, the cyclotomic polynomials are:<ref>{{Cite OEIS|A013595|mode=cs2}}</ref>

:<math>\begin{align}
\Phi_1(x) &= x - 1 \\
\Phi_2(x) &= x + 1 \\
\Phi_3(x) &= x^2 + x + 1 \\
\Phi_4(x) &= x^2 + 1 \\
\Phi_5(x) &= x^4 + x^3 + x^2 + x +1 \\
\Phi_6(x) &= x^2 - x + 1 \\
\Phi_7(x) &= x^6 + x^5 + x^4 + x^3 + x^2 + x + 1 \\
\Phi_8(x) &= x^4 + 1 \\
\Phi_9(x) &= x^6 + x^3 + 1 \\
\Phi_{10}(x) &= x^4 - x^3 + x^2 - x + 1 \\
\Phi_{11}(x) &= x^{10} + x^9 + x^8 + x^7 + x^6 + x^5 + x^4 + x^3 + x^2 + x + 1 \\
\Phi_{12}(x) &= x^4 - x^2 + 1 \\
\Phi_{13}(x) &= x^{12} + x^{11} + x^{10} + x^9 + x^8 + x^7 + x^6 + x^5 + x^4 + x^3 + x^2 + x + 1 \\
\Phi_{14}(x) &= x^6 - x^5 + x^4 - x^3 + x^2 - x + 1 \\
\Phi_{15}(x) &= x^8 - x^7 + x^5 - x^4 + x^3 - x + 1 \\
\Phi_{16}(x) &= x^8 + 1 \\
\Phi_{17}(x) &= x^{16} + x^{15} + x^{14} + x^{13} + x^{12} + x^{11} + x^{10} + x^9 + x^8 + x^7 + x^6 + x^5 + x^4 + x^3 + x^2 + x + 1\\
\Phi_{18}(x) &= x^6 - x^3 + 1 \\
\Phi_{19}(x) &= x^{18} + x^{17} + x^{16} + x^{15} + x^{14} + x^{13} + x^{12} + x^{11} + x^{10} + x^9 + x^8 + x^7 + x^6 + x^5 + x^4 + x^3 + x^2 + x + 1\\
\Phi_{20}(x) &= x^8 - x^6 + x^4 - x^2 + 1 \\
\Phi_{21}(x) &= x^{12} - x^{11} + x^9 - x^8 + x^6 - x^4 + x^3 - x + 1 \\
\Phi_{22}(x) &= x^{10} - x^9 + x^8 - x^7 + x^6 - x^5 + x^4 - x^3 + x^2 - x + 1 \\
\Phi_{23}(x) &= x^{22} + x^{21} + x^{20} + x^{19} + x^{18} + x^{17} + x^{16} + x^{15} + x^{14} + x^{13} + x^{12} \\
& \qquad\quad + x^{11} + x^{10} + x^9 + x^8 + x^7 + x^6 + x^5 + x^4 + x^3 + x^2 + x + 1 \\
\Phi_{24}(x) &= x^8 - x^4 + 1 \\
\Phi_{25}(x) &= x^{20} + x^{15} + x^{10} + x^5 + 1 \\
\Phi_{26}(x) &= x^{12} - x^{11} + x^{10} - x^9 + x^8 - x^7 + x^6 - x^5 + x^4 - x^3 + x^2 - x + 1 \\
\Phi_{27}(x) &= x^{18} + x^9 + 1 \\
\Phi_{28}(x) &= x^{12} - x^{10} + x^8 - x^6 + x^4 - x^2 + 1 \\
\Phi_{29}(x) &= x^{28} + x^{27} + x^{26} + x^{25} + x^{24} + x^{23} + x^{22} + x^{21} + x^{20} + x^{19} + x^{18} + x^{17} + x^{16} + x^{15} \\
& \qquad\quad + x^{14} + x^{13} + x^{12} + x^{11} + x^{10} + x^9 + x^8 + x^7 + x^6 + x^5 + x^4 + x^3 + x^2 + x + 1 \\
\Phi_{30}(x) &= x^8 + x^7 - x^5 - x^4 - x^3 + x + 1.
\end{align}</math>

The case of the 105th cyclotomic polynomial is interesting because 105 is the least positive integer that is the product of three distinct odd prime numbers (3×5×7) and this polynomial is the first one that has a [[coefficient]] other than 1, 0, or −1:<ref>{{citation
 | last = Brookfield | first = Gary
 | doi = 10.4169/math.mag.89.3.179
 | issue = 3
 | journal = Mathematics Magazine
 | jstor = 10.4169/math.mag.89.3.179
 | mr = 3519075
 | pages = 179–188
 | title = The coefficients of cyclotomic polynomials
 | volume = 89
 | year = 2016}}</ref>

:<math>\begin{align}
\Phi_{105}(x) ={}&x^{48} + x^{47} + x^{46} - x^{43} - x^{42} - 2 x^{41} - x^{40} - x^{39} + x^{36} + x^{35} + x^{34} \\ 
&{}+ x^{33} + x^{32} + x^{31} - x^{28} - x^{26} - x^{24} - x^{22} - x^{20} + x^{17} + x^{16} + x^{15} \\
&{}+ x^{14} + x^{13} + x^{12} - x^9 - x^8 - 2 x^7 - x^6 - x^5 + x^2 + x + 1. 
\end{align}</math>

==Properties==

===Fundamental tools===

The cyclotomic polynomials are monic polynomials with integer coefficients that are [[irreducible polynomial|irreducible]] over the field of the rational numbers. Except for ''n'' equal to 1 or 2, they are [[Palindromic polynomial|palindrome]]s of even degree.

The degree of <math>\Phi_n</math>, or in other words the number of ''n''th primitive roots of unity, is <math>\varphi (n)</math>, where <math>\varphi</math> is [[Euler's totient function]].

The fact that <math>\Phi_n</math> is an irreducible polynomial of degree <math>\varphi (n)</math> in the [[ring (mathematics)|ring]] <math>\Z[x]</math> is a nontrivial result due to [[Carl Friedrich Gauss|Gauss]].<ref>{{Lang Algebra}}</ref> Depending on the chosen definition, it is either the value of the degree or the irreducibility which is a nontrivial result. The case of prime ''n'' is easier to prove than the general case, thanks to [[Eisenstein's criterion#Cyclotomic polynomials|Eisenstein's criterion]].

A fundamental relation involving cyclotomic polynomials is 

:<math>\begin{align} x^n - 1 
&=\prod_{1\leqslant k\leqslant n} \left(x- e^{2i\pi\frac{k}{n}} \right) \\
&= \prod_{d \mid n} \prod_{1 \leqslant k \leqslant n \atop \gcd(k, n) = d} \left(x- e^{2i\pi\frac{k}{n}} \right) \\
&=\prod_{d \mid n} \Phi_{\frac{n}{d}}(x) =  \prod_{d\mid n} \Phi_d(x).\end{align}</math>

which means that each ''n''-th root of unity is a primitive ''d''-th root of unity for a unique ''d'' dividing ''n''.

The [[Möbius inversion formula#Multiplicative notation|Möbius inversion formula]] allows <math>\Phi_n(x)</math> to be expressed as an explicit rational fraction:

:<math>\Phi_n(x)=\prod_{d\mid n}(x^d-1)^{\mu \left (\frac{n}{d} \right )}, </math>

where <math>\mu</math> is the [[Möbius function]].

This provides a [[Recursive definition|recursive formula]] for the cyclotomic polynomial <math>\Phi_{n}(x)</math>, which may be computed by [[Polynomial long division|dividing]] <math>x^n-1</math> by the cyclotomic polynomials <math>\Phi_d(x)</math> for the proper divisors ''d'' dividing ''n'', starting from <math>\Phi_{1}(x)=x-1</math>:

:<math>\Phi_n(x)=\frac{x^{n}-1}{\prod_{\stackrel{d|n}{{}_{d<n}}}\Phi_{d}(x)}.</math>

This gives an algorithm for computing any <math>\Phi_n(x)</math>, provided [[integer factorization]] and [[Euclidean division of polynomials|division of polynomials]] are available. Many [[computer algebra systems]], such as [[SageMath]], [[Maple (software)|Maple]], [[Mathematica]], and [[PARI/GP]], have a built-in function to compute the cyclotomic polynomials.

===Easy cases for computation===
As noted above, if {{math|1=''n'' = ''p''}} is a prime number, then

:<math>\Phi_p(x) = 1+x+x^2+\cdots+x^{p-1}=\sum_{k=0}^{p-1}x^k\;.</math>

If ''n'' is an odd integer greater than one, then 

:<math>\Phi_{2n}(x) = \Phi_n(-x)\;.</math>

In particular, if {{math|1=''n'' = 2''p''}} is twice an odd prime, then (as noted above)

:<math>\Phi_{2p}(x) = 1-x+x^2-\cdots+x^{p-1}=\sum_{k=0}^{p-1}(-x)^k\;.</math>

If {{math|1=''n'' = ''p<sup>m</sup>''}} is a [[prime power]] (where ''p'' is prime), then

:<math>\Phi_{p^m}(x) = \Phi_p(x^{p^{m-1}}) =\sum_{k=0}^{p-1}x^{kp^{m-1}}\;.</math>

More generally, if {{math|1=''n'' = ''p<sup>m</sup>r''}} with {{math|''r''}} [[relatively prime]] to {{math|''p''}}, then 

:<math>\Phi_{p^mr}(x) = \Phi_{pr}(x^{p^{m-1}})\;.</math>

These formulas may be applied repeatedly to get a simple expression for any cyclotomic polynomial <math>\Phi_n(x)</math> in terms of a cyclotomic polynomial of [[square-free number|square free]] index: If {{math|''q''}} is the [[Product (mathematics)|product]] of the prime divisors of {{math|''n''}} (its [[Radical of an integer|radical]]), then<ref>{{citation
 | last = Cox | first = David A. | author-link = David A. Cox  | contribution = Exercise 12  | doi = 10.1002/9781118218457 | edition = 2nd  | isbn = 978-1-118-07205-9 | page = 237 | publisher = John Wiley & Sons  | title = Galois Theory | year = 2012}}.</ref>

:<math>\Phi_n(x) = \Phi_q(x^{n/q})\;.</math>

This allows formulas to be given for the {{math|''n''}}th cyclotomic polynomial when {{math|''n''}} has at most one odd prime factor: If {{math|''p''}} is an odd prime number, and {{math|''h''}} and {{math|''k''}} are positive integers, then
:<math>\Phi_{2^m}(x) = x^{2^{m-1}}+1\;,</math>
:<math>\Phi_{p^m}(x) = \sum_{j=0}^{p-1}x^{jp^{m-1}}\;,</math>
:<math>\Phi_{2^\ell p^m}(x) = \sum_{j=0}^{p-1}(-1)^jx^{j2^{\ell-1}p^{m-1}}\;.</math>

For other values of {{math|''n''}}, the computation of the {{math|''n''}}th cyclotomic polynomial is similarly reduced to that of  <math>\Phi_q(x),</math> where {{math|''q''}} is the product of the distinct odd prime divisors of {{math|''n''}}. To deal with this case, one has that, for {{math|''p''}} prime and not dividing {{math|''n''}},<ref name="WolframCyclotomic">{{MathWorld |title=Cyclotomic Polynomial |id=CyclotomicPolynomial|mode=cs2}}</ref>

:<math>\Phi_{np}(x)=\Phi_{n}(x^p)/\Phi_n(x)\;.</math>

===Integers appearing as coefficients===

The problem of bounding the magnitude of the coefficients of the cyclotomic polynomials has been the object of a number of research papers.<ref name=arXivSanna>{{cite arXiv|eprint=2111.04034 |last1=Sanna |first1=Carlo |title=A Survey on Coefficients of Cyclotomic Polynomials |year=2021 |class=math.NT|mode=cs2 }}</ref>
 
If ''n'' has at most two distinct odd prime factors, then Migotti showed that the coefficients of <math>\Phi_n</math> are all in the set {1, −1, 0}.<ref>{{citation |title=Algebra: A Graduate Course |first=Martin |last=Isaacs |page=310 |isbn=978-0-8218-4799-2 |publisher=AMS Bookstore |year=2009}}</ref>

The first cyclotomic polynomial for a product of three different odd prime factors is <math>\Phi_{105}(x);</math> it has a coefficient −2 (see [[#Examples|above]]). The converse is not true: <math>\Phi_{231}(x)=\Phi_{3\times 7\times 11}(x)</math> only has coefficients in {1, −1, 0}.

If ''n'' is a product of more different odd prime factors, the coefficients may increase to very high values. E.g., <math>\Phi_{15015}(x) =\Phi_{3\times 5\times 7\times 11\times 13}(x)</math> has coefficients running from −22 to 23; also <math>\Phi_{255255}(x)=\Phi_{3\times 5\times 7\times 11\times 13\times 17}(x)</math>, the smallest ''n'' with 6 different odd primes, has coefficients of magnitude up to 532.

Let ''A''(''n'') denote the maximum absolute value of the coefficients of <math>\Phi_{n}(x)</math>.  It is known that for any positive ''k'', the number of ''n'' up to ''x'' with ''A''(''n'') > ''n''<sup>''k''</sup> is at least ''c''(''k'')⋅''x'' for a positive ''c''(''k'') depending on ''k'' and ''x'' sufficiently large.  In the opposite direction, for any function ψ(''n'') tending to [[infinity]] with ''n'' we have ''A''(''n'') bounded above by ''n''<sup>ψ(''n'')</sup> for almost all ''n''.<ref name=Mai2008>{{Citation
 | last = Maier
 | first = Helmut
 | chapter = Anatomy of integers and cyclotomic polynomials
 | editor1-last = De Koninck
 | editor1-first = Jean-Marie
 | editor2-last = Granville
 | editor2-first = Andrew
 | editor2-link = Andrew Granville
 | editor3-last = Luca
 | editor3-first = Florian
 | title = Anatomy of integers. Based on the CRM workshop, Montreal, Canada, March 13-17, 2006
 | location = Providence, RI
 | publisher = [[American Mathematical Society]]
 | series = CRM Proceedings and Lecture Notes
 | volume = 46
 | pages = 89–95
 | year = 2008
 | isbn = 978-0-8218-4406-9
 | zbl = 1186.11010
}}</ref>

A combination of theorems of Bateman and Vaughan states that{{r|arXivSanna|p=10}} on the one hand, for every <math>\varepsilon>0</math>, we have
:<math>A(n) < e^{\left(n^{(\log 2+\varepsilon)/(\log\log n)}\right)}</math>
for all sufficiently large positive integers <math>n</math>, and on the other hand, we have
:<math>A(n) > e^{\left(n^{(\log 2)/(\log\log n)}\right)}</math>
for infinitely many positive integers <math>n</math>. This implies in particular that [[univariate polynomial|univariate polynomials]] (concretely <math>x^n-1</math> for infinitely many positive integers <math>n</math>) can have factors (like <math>\Phi_n</math>) whose coefficients are [[Superpolynomial|superpolynomially]] larger than the original coefficients. This is not too far from the general [[Landau-Mignotte bound]].

===Gauss's formula===

Let ''n'' be odd, [[Square-free integer|square-free]], and greater than 3. Then:<ref>Gauss, DA, Articles 356-357</ref><ref name=riesel>{{citation
 | last1 = Riesel  | first1 = Hans
 | title = Prime Numbers and Computer Methods for Factorization
 | edition = 2nd
 | publisher = Birkhäuser
 | location = Boston
 | year = 1994
 | isbn = 0-8176-3743-5
 | pages = 309-316, 436, 443
}}</ref>

:<math>4\Phi_n(z) = A_n^2(z) - (-1)^{\frac{n-1}{2}}nz^2B_n^2(z)</math>

for certain polynomials ''A<sub>n</sub>''(''z'') and ''B<sub>n</sub>''(''z'') with integer coefficients, ''A<sub>n</sub>''(''z'') of degree ''&phi;''(''n'')/2, and ''B<sub>n</sub>''(''z'') of degree ''&phi;''(''n'')/2 − 2. Furthermore, ''A<sub>n</sub>''(''z'') is palindromic when its degree is even; if its degree is odd it is antipalindromic. Similarly, ''B<sub>n</sub>''(''z'') is palindromic unless ''n'' is composite and ''n'' ≡ 3 (mod 4), in which case it is antipalindromic.

The first few cases are

:<math>\begin{align}
4\Phi_5(z) &=4(z^4+z^3+z^2+z+1)\\ 
&= (2z^2+z+2)^2 - 5z^2  \\[6pt]
4\Phi_7(z) &=4(z^6+z^5+z^4+z^3+z^2+z+1)\\ 
&= (2z^3+z^2-z-2)^2+7z^2(z+1)^2 \\ [6pt]
4\Phi_{11}(z)
&=4(z^{10}+z^9+z^8+z^7+z^6+z^5+z^4+z^3+z^2+z+1)\\ 
&= (2z^5+z^4-2z^3+2z^2-z-2)^2+11z^2(z^3+1)^2
\end{align}</math>

===Lucas's formula===

Let ''n'' be odd, square-free and greater than 3. Then{{r|riesel}}

:<math>\Phi_n(z) = U_n^2(z) - (-1)^{\frac{n-1}{2}}nzV_n^2(z)</math>

for certain polynomials ''U<sub>n</sub>''(''z'') and ''V<sub>n</sub>''(''z'') with integer coefficients, ''U<sub>n</sub>''(''z'') of degree ''&phi;''(''n'')/2, and ''V<sub>n</sub>''(''z'') of degree ''&phi;''(''n'')/2 − 1. This can also be written

:<math>\Phi_n \left ((-1)^{\frac{n-1}{2}}z \right ) = C_n^2(z) - nzD_n^2(z).</math>

If ''n'' is even, square-free and greater than 2 (this forces ''n''/2 to be odd),

:<math>\Phi_{\frac{n}{2}} (-z^2) = \Phi_{2n}(z)= C_n^2(z) - nzD_n^2(z)</math>

for ''C<sub>n</sub>''(''z'') and ''D<sub>n</sub>''(''z'') with integer coefficients, ''C<sub>n</sub>''(''z'') of degree ''&phi;''(''n''), and ''D<sub>n</sub>''(''z'') of degree ''&phi;''(''n'') − 1. ''C<sub>n</sub>''(''z'') and ''D<sub>n</sub>''(''z'') are both palindromic.

The first few cases are:

:<math>\begin{align}
\Phi_3(-z) &=\Phi_6(z) =z^2-z+1 \\
&= (z+1)^2 - 3z \\[6pt]
\Phi_5(z) &=z^4+z^3+z^2+z+1 \\
&= (z^2+3z+1)^2 - 5z(z+1)^2 \\[6pt]
\Phi_{6/2}(-z^2) &=\Phi_{12}(z)=z^4-z^2+1 \\
&= (z^2+3z+1)^2 - 6z(z+1)^2
\end{align}</math>

===Sister Beiter conjecture===

The [[Sister Beiter conjecture]] is concerned with the maximal size (in absolute value) <math>A(pqr)</math> of coefficients of ''ternary cyclotomic polynomials'' <math>\Phi_{pqr}(x)</math> where <math>p\leq q\leq r</math> are three odd primes.<ref name=beiter68>{{citation|last=Beiter|first=Marion|author-link=Marion Beiter|title=Magnitude of the Coefficients of the Cyclotomic Polynomial <math>F_{pqr}(x)</math>|journal=[[The American Mathematical Monthly]]|volume=75|issue=4|date=April 1968|pages=370–372|doi=10.2307/2313416 |jstor=2313416}}</ref>

== Cyclotomic polynomials over a finite field and over the {{math|''p''}}-adic integers ==
{{see also|Finite field#Roots of unity}}
Over a [[finite field]] with a prime number {{math|''p''}} of elements, for any integer {{math|''n''}} that is not a multiple of {{math|''p''}}, the cyclotomic polynomial <math>\Phi_n</math> factorizes into <math>\frac{\varphi (n)}{d}</math> irreducible polynomials of degree {{math|''d''}}, where <math>\varphi (n)</math> is [[Euler's totient function]] and {{math|''d''}} is the [[multiplicative order]] of {{math|''p''}} modulo {{math|''n''}}. In particular, <math>\Phi_n</math> is irreducible [[if and only if]] {{math|''p''}} is a [[primitive root modulo n|primitive root modulo {{mvar|n}}]], that is, {{math|''p''}} does not divide {{math|''n''}}, and its multiplicative order modulo {{math|''n''}} is <math>\varphi(n)</math>, the degree of <math>\Phi_n</math>.<ref>{{citation | last1 = Lidl | first1 = Rudolf | last2 = Niederreiter| first2 = Harald | edition = 2nd  |  page = 65 | publisher = Cambridge University Press | title = Finite Fields | year = 2008}}.</ref>

These results are also true over the [[p-adic integer|{{mvar|p}}-adic integers]], since [[Hensel's lemma]] allows lifting a factorization over the field with {{math|''p''}} elements to a factorization over the {{math|''p''}}-adic integers.

==Polynomial values==
{{unreferenced section|date=April 2014}}

If {{math|''x''}} takes any real value, then <math>\Phi_n(x)>0</math> for every {{math|''n'' ≥ 3}} (this follows from the fact that the roots of a cyclotomic polynomial are all non-real, for {{math|''n'' ≥ 3}}).

For studying the values that a cyclotomic polynomial may take when {{math|''x''}} is given an integer value, it suffices to consider only the case {{math|''n'' ≥ 3}}, as the cases {{math|1=''n'' = 1}} and  {{math|1=''n'' = 2}} are trivial (one has <math>\Phi_1(x)=x-1</math> and <math>\Phi_2(x)=x+1</math>). 

For {{math|''n'' ≥ 2}}, one has

:<math>\Phi_n(0) =1,</math>
:<math>\Phi_n(1) =1</math> if {{math|''n''}} is not a [[prime power]],
:<math>\Phi_n(1) =p</math> if <math>n=p^k</math> is a prime power with {{math|''k'' ≥ 1}}.

The values that a cyclotomic polynomial <math>\Phi_n(x)</math> may take for other integer values of {{math|''x''}} is strongly related with the [[multiplicative order]] modulo a prime number. 

More precisely, given a prime number {{math|''p''}} and an integer {{math|''b''}} coprime with {{math|''p''}}, the multiplicative order of {{math|''b''}} modulo {{math|''p''}}, is the smallest positive integer {{math|''n''}} such that {{math|''p''}} is a divisor of <math>b^n-1.</math> For {{math|''b'' > 1}}, the multiplicative order of {{math|''b''}} modulo {{math|''p''}} is also the [[periodic function|shortest period]] of the representation of {{math|1/''p''}} in the [[numeral base]] {{math|''b''}} (see [[Unique prime]]; this explains the notation choice). 

The definition of the multiplicative order implies that, if {{math|''n''}} is the multiplicative order of {{math|''b''}} modulo {{math|''p''}}, then {{math|''p''}} is a divisor of <math>\Phi_n(b).</math> The converse is not true, but one has the following.

If {{math|''n'' > 0}} is a positive integer and {{math|''b'' > 1}} is an integer, then (see below for a proof)
:<math>\Phi_n(b)=2^kgh,</math>
where 
* {{math|''k''}} is a non-negative integer, always equal to 0 when {{math|''b''}} is even. (In fact, if {{math|''n''}} is neither 1 nor 2, then {{math|''k''}} is either 0 or 1. Besides, if {{math|''n''}} is not a [[power of 2]], then {{math|''k''}} is always equal to 0)
* {{math|''g''}} is 1 or the largest odd prime factor of {{math|''n''}}.
* {{math|''h''}} is odd, coprime with {{math|''n''}}, and its [[prime factor]]s are exactly the odd primes {{math|''p''}} such that {{math|''n''}} is the multiplicative order of {{math|''b''}} modulo {{math|''p''}}.

This implies that, if {{math|''p''}} is an odd prime divisor of <math>\Phi_n(b),</math> then either {{math|''n''}} is a divisor of {{math|''p'' − 1}} or {{math|''p''}} is a divisor of {{math|''n''}}. In the latter case, <math>p^2</math> does not divide <math>\Phi_n(b).</math>

[[Zsigmondy's theorem]] implies that the only cases where  {{math|1=''b'' > 1}} and {{math|1=''h'' = 1}} are

:<math>\begin{align}
\Phi_1(2) &=1 \\
\Phi_2 \left (2^k-1 \right ) & =2^k && k >0 \\
\Phi_6(2) &=3
\end{align}</math> 

It follows from above factorization that the odd prime factors of

:<math>\frac{\Phi_n(b)}{\gcd(n,\Phi_n(b))}</math>

are exactly the odd primes {{math|''p''}} such that {{math|''n''}} is the multiplicative order of {{math|''b''}} modulo {{math|''p''}}. This fraction may be even only when {{math|''b''}} is odd. In this case, the multiplicative order of {{math|''b''}} modulo {{math|2}} is always {{math|1}}.

There are many pairs {{math|(''n'', ''b'')}} with {{math|''b'' > 1}} such that <math>\Phi_n(b)</math> is prime. In fact, [[Bunyakovsky conjecture]] implies that, for every {{math|''n''}}, there are infinitely many {{math|''b'' > 1}} such that <math>\Phi_n(b)</math> is prime. See {{oeis|id=A085398}} for the list of the smallest {{math|''b'' > 1}} such that <math>\Phi_n(b)</math> is prime (the smallest {{math|''b'' > 1}} such that <math>\Phi_n(b)</math> is prime is about <math>\gamma \cdot \varphi(n)</math>, where <math>\gamma</math> is [[Euler–Mascheroni constant]], and <math>\varphi</math> is [[Euler's totient function]]). See also {{oeis|id=A206864}} for the list of the smallest primes of the form <math>\Phi_n(b)</math> with {{math|''n'' > 2}} and {{math|''b'' > 1}}, and, more generally, {{oeis|id=A206942}}, for the smallest positive integers of this form.
{{cot| title=Proofs}}
* ''Values of'' <math>\Phi_n(1).</math> If <math>n=p^{k+1}</math> is a prime power, then 
::<math>\Phi_n(x)=1+x^{p^k}+x^{2p^{k}}+\cdots+x^{(p-1)p^k} \qquad \text{and} \qquad \Phi_n(1)=p.</math> 
:If {{math|''n''}} is not a prime power, let <math>P(x)=1+x+\cdots+x^{n-1},</math> we have <math>P(1)=n,</math> and {{math|''P''}} is the product of the <math>\Phi_k(x)</math> for {{math|''k''}} dividing {{math|''n''}} and different of {{math|1}}. If {{math|''p''}} is a prime divisor of multiplicity {{math|''m''}} in {{math|''n''}}, then <math>\Phi_p(x), \Phi_{p^2}(x), \cdots, \Phi_{p^m}(x)</math> divide {{math|''P''(''x'')}}, and their values at {{math|1}} are {{math|''m''}} factors equal to {{math|''p''}} of <math>n=P(1).</math> As {{math|''m''}} is the multiplicity of {{math|''p''}} in {{math|''n''}}, {{math|''p''}} cannot divide the value at {{math|1}} of the other factors of <math>P(x).</math> Thus there is no prime that divides <math>\Phi_n(1).</math>

*''If'' {{math|''n''}} ''is the multiplicative order of'' {{math|''b''}} ''modulo'' {{math|''p''}}, ''then'' <math>p \mid \Phi_n(b).</math> By definition, <math>p \mid b^n-1.</math> If <math>p \nmid \Phi_n(b),</math> then {{math|''p''}} would divide another factor <math>\Phi_k(b)</math> of <math>b^n-1,</math> and would thus divide <math>b^k-1,</math> showing that, if there would be the case, {{math|''n''}} would not be the multiplicative order of {{math|''b''}} modulo {{math|''p''}}.

*''The other prime divisors of'' <math>\Phi_n(b)</math> ''are divisors of'' {{math|''n''}}. Let {{math|''p''}} be a prime divisor of <math>\Phi_n(b)</math> such that {{math|''n''}} is not be the multiplicative order of {{math|''b''}} modulo {{math|''p''}}. If {{math|''k''}} is the multiplicative order of {{math|''b''}} modulo {{math|''p''}}, then {{math|''p''}} divides both <math>\Phi_n(b)</math> and <math>\Phi_k(b).</math> The [[resultant]] of <math>\Phi_n(x)</math> and <math>\Phi_k(x)</math> may be written <math>P\Phi_k+Q\Phi_n,</math> where {{math|''P''}} and {{math|''Q''}} are polynomials. Thus {{math|''p''}} divides this resultant. As {{math|''k''}} divides {{math|''n''}}, and the resultant of two polynomials divides the [[discriminant]] of any common multiple of these polynomials, {{math|''p''}} divides also the discriminant <math>n^n</math> of <math>x^n-1.</math> Thus {{math|''p''}} divides {{math|''n''}}.

*{{math|''g''}} ''and'' {{math|''h''}} ''are coprime''. In other words, if {{math|''p''}} is a prime common divisor of {{math|''n''}} and <math>\Phi_n(b),</math> then {{math|''n''}} is not the multiplicative order of {{math|''b''}} modulo {{math|''p''}}. By [[Fermat's little theorem]], the multiplicative order of {{math|''b''}} is a divisor of {{math|''p'' − 1}}, and thus smaller than {{math|''n''}}.

*{{math|''g''}} ''is square-free''. In other words, if  {{math|''p''}} is a prime common divisor of {{math|''n''}} and <math>\Phi_n(b),</math> then <math>p^2</math> does not divide <math>\Phi_n(b).</math> Let {{math|1=''n'' = ''pm''}}. It suffices to prove that <math>p^2</math> does not divide {{math|''S''(''b'')}} for some polynomial {{math|''S''(''x'')}}, which is a multiple of <math>\Phi_n(x).</math> We take 
::<math>S(x)=\frac{x^n-1}{x^m-1} = 1 + x^m + x^{2m} + \cdots + x^{(p-1)m}.</math> 
:The multiplicative order of {{math|''b''}} modulo {{math|''p''}} divides {{math|gcd(''n'', ''p'' − 1)}}, which is a divisor of {{math|1=''m'' = ''n''/''p''}}. Thus  {{math|1=''c'' = ''b<sup>m</sup>'' − 1}} is a multiple of {{math|''p''}}. Now, 
::<math>S(b) = \frac{(1+c)^p-1}{c} = p+ \binom{p}{2}c + \cdots + \binom{p}{p}c^{p-1}.</math> 
:As {{math|''p''}} is prime and greater than 2, all the terms but the first one are multiples of <math>p^2.</math> This proves that <math>p^2 \nmid \Phi_n(b).</math>
{{cob}}


==Applications==

Using <math>\Phi_n</math>, one can give an elementary proof for the infinitude of [[Prime number|prime]]s [[Congruence relation|congruent]] to 1 modulo ''n'',<ref>S. Shirali. ''Number Theory''. Orient Blackswan, 2004. p. 67. {{isbn|81-7371-454-1}}</ref> which is a special case of [[Dirichlet's theorem on arithmetic progressions]].
{{cot| title=Proof}}
Suppose <math>p_1, p_2, \ldots, p_k</math> is a finite list of primes congruent to <math>1</math> modulo <math>n.</math> Let <math>N = np_1p_2\cdots  p_k</math> and consider <math>\Phi_n(N)</math>. Let <math>q</math> be a prime factor of <math>\Phi_n(N)</math> (to see that <math>\Phi_n(N) \neq \pm 1</math> decompose it into linear factors and note that 1 is the closest root of unity to <math>N</math>). Since <math>\Phi_n(x) \equiv \pm 1 \pmod x,</math> we know that <math>q</math> is a new prime not in the list. We will show that <math>q \equiv 1 \pmod n.</math>

Let <math>m</math> be the order of <math>N</math> modulo <math>q.</math> Since <math>\Phi_n(N) \mid N^n - 1</math> we have <math>N^n -1 \equiv 0 \pmod{q}</math>. Thus <math>m \mid n</math>.  We will show that <math>m = n</math>.

Assume for contradiction that <math>m < n</math>. Since 

:<math>\prod_{d \mid m} \Phi_d(N) = N^m - 1 \equiv 0 \pmod q</math> 

we have 

:<math>\Phi_d(N) \equiv 0 \pmod q,</math> 

for some <math>d < n</math>. Then <math>N</math> is a double root of 

:<math>\prod_{d \mid n} \Phi_d(x) \equiv x^n -1 \pmod q.</math>

Thus <math>N</math> must be a root of the derivative so 

:<math>\left.\frac{d(x^n -1)}{dx}\right|_N \equiv nN^{n-1} \equiv 0 \pmod q.</math>

But <math>q \nmid N</math> and therefore <math>q \nmid n.</math> This is a contradiction so <math>m = n</math>. The order of <math>N \pmod q,</math> which is <math>n</math>, must divide <math>q-1</math>. Thus <math>q \equiv 1 \pmod n.</math>
{{cob}}

=== Periodic recursive sequences ===

The constant-coefficient [[Linear recurrence with constant coefficients|linear recurrences]] which are periodic are precisely the power series coefficients of rational functions whose denominators are products of cyclotomic polynomials. 

In the theory of combinatorial [[Generating function|generating functions]], the denominator of a rational function determines a linear recurrence for its power series coefficients. For example, the [[Fibonacci sequence]] has generating function <blockquote><math>F(x) = F_1x + F_2x^2 + F_3x^3 + \cdots = \frac{x}{1-x-x^2} ,</math></blockquote>and equating coefficients on both sides of <math>F(x)(1-x-x^2) = x</math> gives <math>F_n - F_{n-1} - F_{n-2} = 0</math> for <math>n\geq 2</math>.  
<p>
Any rational function whose denominator is a divisor of <math>x^n - 1</math> has a recursive sequence of coefficients which is periodic with period at most ''n''. For example,</p> <blockquote><math>P(x) = -\frac{1+2x}{\Phi_6(x)} = \frac{1+2x}{1-x+x^2}
= \sum_{n\geq 0} P_n x^n 
= 1 + 3 x + 2 x^2 - x^3 - 3 x^4 - 2 x^5 + x^6 + 3 x^7 + 2 x^8 + \cdots</math> </blockquote>has coefficients defined by the recurrence <math>P_n - P_{n-1} + P_{n-2} = 0</math> for <math>n\geq 2</math>, starting from <math>P_0=1, P_1=3</math>. But <math>1-x^6 = \Phi_6(x)\Phi_3(x)\Phi_2(x)\Phi_1(x)</math>, so we may write <blockquote><math>P(x) = \frac{(1+2x)\Phi_3(x)\Phi_2(x)\Phi_1(x)}{1 - x^6}
 = \frac{1 + 3 x + 2 x^2 - x^3 - 3 x^4-2 x^5}{1 - x^6}, </math></blockquote>which means <math>P_n - P_{n-6} = 0 </math> for <math>n\geq 6</math>, and the sequence has period 6 with initial values given by the coefficients of the numerator.

==See also==
* [[Cyclotomic field]]
* [[Aurifeuillean factorization]]
* [[Root of unity]]

==References==
{{Reflist}}

==Further reading==

Gauss's book ''[[Disquisitiones Arithmeticae]]'' [''Arithmetical Investigations''] has been translated from Latin into French, German, and English. The German edition includes all of his papers on number theory: all the proofs of quadratic reciprocity, the determination of the sign of the Gauss sum, the investigations into biquadratic reciprocity, and unpublished notes.
* {{citation
 | last = Gauss | first = Carl Friedrich
 | year = 1801
 | language = la
 | title = Disquisitiones Arithmeticae
 | publisher = Gerh. Fleischer
 | location = Leipzig
 | url = https://archive.org/details/disquisitionesa00gaus/
 }}
*{{citation
 | last = Gauss | first = Carl Friedrich
 | year = 1807 | orig-year = 1801
 | translator-last = Poullet-Delisle | translator-first = A.-C.-M.
 | title = Recherches Arithmétiques
 | language = fr
 | publisher = Courcier
 | location = Paris
 | url = https://archive.org/details/recherchesarithm00gaus/
 }}
*{{citation
 | last = Gauss | first = Carl Friedrich
 | year = 1889 | orig-year = 1801
 | translator-last = Maser | translator-first = H. 
 | title = Carl Friedrich Gauss' Untersuchungen über höhere Arithmetik
 | language = de
 | publisher = Springer 
 | location = Berlin
 | url = https://archive.org/details/gri_33125000752168/
 }}; Reprinted 1965, New York: Chelsea, {{isbn|0-8284-0191-8}}
*{{citation
 | last = Gauss | first = Carl Friedrich
 | year = 1966 | orig-year = 1801
 | translator-last = Clarke |translator-first = Arthur A.
 | title = Disquisitiones Arithmeticae
 | publisher = Yale
 | location = New Haven
 | isbn = 978-0-300-09473-2
 | doi = 10.12987/9780300194258
 }}; Corrected ed. 1986, New York: Springer, {{doi|10.1007/978-1-4939-7560-0}}, {{isbn|978-0-387-96254-2}}
*{{citation
 | last1 = Lemmermeyer | first1 = Franz
 | title = Reciprocity Laws: from Euler to Eisenstein
 | publisher = Springer
 | location = Berlin
 | year = 2000
 | isbn = 978-3-642-08628-1
 | doi = 10.1007/978-3-662-12893-0
 }}

==External links==
*{{mathworld|urlname=CyclotomicPolynomial|title=Cyclotomic polynomial|mode=cs2}}
*{{springer|title=Cyclotomic polynomials|id=p/c027580}}
*{{OEIS el|sequencenumber=A013595|name=Triangle of coefficients of cyclotomic polynomial Phi_n(x) (exponents in increasing order)}}
*{{OEIS el|sequencenumber=A013594|name=Smallest order of cyclotomic polynomial containing n or −n as a coefficient}}

{{bots|deny=Citation bot}}

[[Category:Polynomials]]
[[Category:Algebra]]
[[Category:Number theory]]