Editing Cyclotomic polynomial (section)

==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}}