Cyclotomic polynomial

Template:Short description In mathematics, the nth cyclotomic polynomial, for any positive integer n, is the unique irreducible polynomial with integer coefficients that is a divisor of <math>x^n-1</math> and is not a divisor of <math>x^k-1</math> for any Template:Nowrap Its roots are all nth primitive roots of unity <math> e^{2i\pi\frac{k}{n}} </math>, where k runs over the positive integers less than n and coprime to n (and i is the imaginary unit). In other words, the nth 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 over the field of the rational numbers of any primitive nth-root of unity (<math> e^{2i\pi/n} </math> is an example of such a root).

An important relation linking cyclotomic polynomials and primitive roots of unity is

showing that <math>x</math> is a root of <math>x^n - 1</math> if and only if it is a dTemplate:Spaceth primitive root of unity for some d that divides n.<ref>Template:Citation</ref>

ExamplesEdit

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 = 2p 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>Template:Cite OEIS</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>Template:Citation</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>

PropertiesEdit

Fundamental toolsEdit

The cyclotomic polynomials are monic polynomials with integer coefficients that are irreducible over the field of the rational numbers. Except for n equal to 1 or 2, they are palindromes of even degree.

The degree of <math>\Phi_n</math>, or in other words the number of nth 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 <math>\Z[x]</math> is a nontrivial result due to Gauss.<ref>Template: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.

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 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 formula for the cyclotomic polynomial <math>\Phi_{n}(x)</math>, which may be computed by 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 division of polynomials are available. Many computer algebra systems, such as SageMath, Maple, Mathematica, and PARI/GP, have a built-in function to compute the cyclotomic polynomials.

Easy cases for computationEdit

As noted above, if Template:Math 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

In particular, if Template:Math 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 Template:Math is a prime power (where p is prime), then

More generally, if Template:Math with Template:Math relatively prime to Template:Math, then

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 index: If Template:Math is the product of the prime divisors of Template:Math (its radical), then<ref>Template:Citation.</ref>

This allows formulas to be given for the Template:Mathth cyclotomic polynomial when Template:Math has at most one odd prime factor: If Template:Math is an odd prime number, and Template:Tmath and Template:Math are positive integers, then

For other values of Template:Math, the computation of the Template:Mathth cyclotomic polynomial is similarly reduced to that of <math>\Phi_q(x),</math> where Template:Math is the product of the distinct odd prime divisors of Template:Math. To deal with this case, one has that, for Template:Math prime and not dividing Template:Math,<ref name="WolframCyclotomic">{{#invoke:Template wrapper|{{#if:|list|wrap}}|_template=cite web |_exclude=urlname, _debug, id |url = https://mathworld.wolfram.com/{{#if:CyclotomicPolynomial%7CCyclotomicPolynomial.html}} |title = Cyclotomic Polynomial |author = Weisstein, Eric W. |website = MathWorld |access-date = |ref = Template:SfnRef }}</ref>

Integers appearing as coefficientsEdit

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>Template:Cite arXiv</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>Template:Citation</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 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^k 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^ψ(n) for almost all n.<ref name=Mai2008>Template:Citation</ref>

A combination of theorems of Bateman and Vaughan states thatTemplate:R on the one hand, for every <math>\varepsilon>0</math>, we have

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 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 superpolynomially larger than the original coefficients. This is not too far from the general Landau-Mignotte bound.

Gauss's formulaEdit

Let n be odd, square-free, and greater than 3. Then:<ref>Gauss, DA, Articles 356-357</ref><ref name=riesel>Template:Citation</ref>

for certain polynomials A_n(z) and B_n(z) with integer coefficients, A_n(z) of degree φ(n)/2, and B_n(z) of degree φ(n)/2 − 2. Furthermore, A_n(z) is palindromic when its degree is even; if its degree is odd it is antipalindromic. Similarly, B_n(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 formulaEdit

Let n be odd, square-free and greater than 3. ThenTemplate:R

for certain polynomials U_n(z) and V_n(z) with integer coefficients, U_n(z) of degree φ(n)/2, and V_n(z) of degree φ(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),

for C_n(z) and D_n(z) with integer coefficients, C_n(z) of degree φ(n), and D_n(z) of degree φ(n) − 1. C_n(z) and D_n(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 conjectureEdit

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>Template:Citation</ref>

Cyclotomic polynomials over a finite field and over the Template:Math-adic integersEdit

Template:See also Over a finite field with a prime number Template:Math of elements, for any integer Template:Math that is not a multiple of Template:Math, the cyclotomic polynomial <math>\Phi_n</math> factorizes into <math>\frac{\varphi (n)}{d}</math> irreducible polynomials of degree Template:Math, where <math>\varphi (n)</math> is Euler's totient function and Template:Math is the multiplicative order of Template:Math modulo Template:Math. In particular, <math>\Phi_n</math> is irreducible if and only if Template:Math is a [[primitive root modulo n|primitive root modulo Template:Mvar]], that is, Template:Math does not divide Template:Math, and its multiplicative order modulo Template:Math is <math>\varphi(n)</math>, the degree of <math>\Phi_n</math>.<ref>Template:Citation.</ref>

These results are also true over the [[p-adic integer|Template:Mvar-adic integers]], since Hensel's lemma allows lifting a factorization over the field with Template:Math elements to a factorization over the Template:Math-adic integers.

Polynomial valuesEdit

{{ safesubst:#invoke:Unsubst||date=__DATE__ |$B= {{ safesubst:#invoke:Unsubst||date=__DATE__ |$B= Template:Ambox }} }}

If Template:Math takes any real value, then <math>\Phi_n(x)>0</math> for every Template:Math (this follows from the fact that the roots of a cyclotomic polynomial are all non-real, for Template:Math).

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

For Template:Math, one has

<math>\Phi_n(1) =1</math> if Template:Math is not a prime power,

<math>\Phi_n(1) =p</math> if <math>n=p^k</math> is a prime power with Template:Math.

The values that a cyclotomic polynomial <math>\Phi_n(x)</math> may take for other integer values of Template:Math is strongly related with the multiplicative order modulo a prime number.

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

The definition of the multiplicative order implies that, if Template:Math is the multiplicative order of Template:Math modulo Template:Math, then Template:Math is a divisor of <math>\Phi_n(b).</math> The converse is not true, but one has the following.

If Template:Math is a positive integer and Template:Math is an integer, then (see below for a proof)

where

Template:Math is a non-negative integer, always equal to 0 when Template:Math is even. (In fact, if Template:Math is neither 1 nor 2, then Template:Math is either 0 or 1. Besides, if Template:Math is not a power of 2, then Template:Math is always equal to 0)
Template:Math is 1 or the largest odd prime factor of Template:Math.
Template:Math is odd, coprime with Template:Math, and its prime factors are exactly the odd primes Template:Math such that Template:Math is the multiplicative order of Template:Math modulo Template:Math.

This implies that, if Template:Math is an odd prime divisor of <math>\Phi_n(b),</math> then either Template:Math is a divisor of Template:Math or Template:Math is a divisor of Template:Math. 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 Template:Math and Template:Math 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

are exactly the odd primes Template:Math such that Template:Math is the multiplicative order of Template:Math modulo Template:Math. This fraction may be even only when Template:Math is odd. In this case, the multiplicative order of Template:Math modulo Template:Math is always Template:Math.

There are many pairs Template:Math with Template:Math such that <math>\Phi_n(b)</math> is prime. In fact, Bunyakovsky conjecture implies that, for every Template:Math, there are infinitely many Template:Math such that <math>\Phi_n(b)</math> is prime. See Template:Oeis for the list of the smallest Template:Math such that <math>\Phi_n(b)</math> is prime (the smallest Template:Math 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 Template:Oeis for the list of the smallest primes of the form <math>\Phi_n(b)</math> with Template:Math and Template:Math, and, more generally, Template:Oeis, for the smallest positive integers of this form. Template:Cot

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 Template:Math is not a prime power, let <math>P(x)=1+x+\cdots+x^{n-1},</math> we have <math>P(1)=n,</math> and Template:Math is the product of the <math>\Phi_k(x)</math> for Template:Math dividing Template:Math and different of Template:Math. If Template:Math is a prime divisor of multiplicity Template:Math in Template:Math, then <math>\Phi_p(x), \Phi_{p^2}(x), \cdots, \Phi_{p^m}(x)</math> divide Template:Math, and their values at Template:Math are Template:Math factors equal to Template:Math of <math>n=P(1).</math> As Template:Math is the multiplicity of Template:Math in Template:Math, Template:Math cannot divide the value at Template:Math of the other factors of <math>P(x).</math> Thus there is no prime that divides <math>\Phi_n(1).</math>

If Template:Math is the multiplicative order of Template:Math modulo Template:Math, 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 Template:Math 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, Template:Math would not be the multiplicative order of Template:Math modulo Template:Math.

The other prime divisors of <math>\Phi_n(b)</math> are divisors of Template:Math. Let Template:Math be a prime divisor of <math>\Phi_n(b)</math> such that Template:Math is not be the multiplicative order of Template:Math modulo Template:Math. If Template:Math is the multiplicative order of Template:Math modulo Template:Math, then Template:Math 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 Template:Math and Template:Math are polynomials. Thus Template:Math divides this resultant. As Template:Math divides Template:Math, and the resultant of two polynomials divides the discriminant of any common multiple of these polynomials, Template:Math divides also the discriminant <math>n^n</math> of <math>x^n-1.</math> Thus Template:Math divides Template:Math.

Template:Math and Template:Math are coprime. In other words, if Template:Math is a prime common divisor of Template:Math and <math>\Phi_n(b),</math> then Template:Math is not the multiplicative order of Template:Math modulo Template:Math. By Fermat's little theorem, the multiplicative order of Template:Math is a divisor of Template:Math, and thus smaller than Template:Math.

Template:Math is square-free. In other words, if Template:Math is a prime common divisor of Template:Math and <math>\Phi_n(b),</math> then <math>p^2</math> does not divide <math>\Phi_n(b).</math> Let Template:Math. It suffices to prove that <math>p^2</math> does not divide Template:Math for some polynomial Template:Math, 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 Template:Math modulo Template:Math divides Template:Math, which is a divisor of Template:Math. Thus Template:Math is a multiple of Template:Math. Now,

<math>S(b) = \frac{(1+c)^p-1}{c} = p+ \binom{p}{2}c + \cdots + \binom{p}{p}c^{p-1}.</math>

As Template:Math 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>

Template:Cob

ApplicationsEdit

Using <math>\Phi_n</math>, one can give an elementary proof for the infinitude of primes congruent to 1 modulo n,<ref>S. Shirali. Number Theory. Orient Blackswan, 2004. p. 67. Template:Isbn</ref> which is a special case of Dirichlet's theorem on arithmetic progressions. Template:Cot 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> Template:Cob

Periodic recursive sequencesEdit

The constant-coefficient 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 functions, the denominator of a rational function determines a linear recurrence for its power series coefficients. For example, the Fibonacci sequence has generating function

<math>F(x) = F_1x + F_2x^2 + F_3x^3 + \cdots = \frac{x}{1-x-x^2} ,</math>

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

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,

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

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

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

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.

ReferencesEdit

Template:Reflist

External linksEdit

Template:Bots

Cyclotomic polynomial

Contents

ExamplesEdit

PropertiesEdit

Fundamental toolsEdit

Easy cases for computationEdit

Integers appearing as coefficientsEdit

Gauss's formulaEdit

Lucas's formulaEdit

Sister Beiter conjectureEdit

Cyclotomic polynomials over a finite field and over the Template:Math-adic integersEdit

Polynomial valuesEdit

ApplicationsEdit

Periodic recursive sequencesEdit

See alsoEdit

ReferencesEdit

Further readingEdit

External linksEdit