Английская Википедия:Cyclotomic polynomial

Шаблон: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 Шаблон: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 not greater 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 is a root of <math>x^n - 1</math> if and only if it is a dШаблон:Spaceth primitive root of unity for some d that divides n.^[1]

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 = 2p where p is an odd prime number, 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:^[2]

<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::^[3]

<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} \\ &\qquad + x^{33} + x^{32} + x^{31} - x^{28} - x^{26} - x^{24} - x^{22} - x^{20} + x^{17} + x^{16} + x^{15} \\ &\qquad + 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 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.^[4] 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 the expression of <math>\Phi_n(x)</math> 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.

The cyclotomic polynomial <math>\Phi_{n}(x)</math> may be computed by (exactly) dividing <math>x^n-1</math> by the cyclotomic polynomials of the proper divisors of n previously computed recursively by the same method:

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

(Recall that <math>\Phi_{1}(x)=x-1</math>.)

This formula defines an algorithm for computing <math>\Phi_n(x)</math> for any n, 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 computation

As noted above, if Шаблон:Math 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 is an odd integer greater than one, then

In particular, if Шаблон:Math is twice an odd prime, then (as noted above)

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

If Шаблон:Math is a prime power (where p is prime), then

More generally, if Шаблон:Math with Шаблон:Math relatively prime to Шаблон:Math, then

These formulas may be applied repeatedly to get a simple expression for any cyclotomic polynomial <math>\Phi_n(x)</math> in term of a cyclotomic polynomial of square free index: If Шаблон:Math is the product of the prime divisors of Шаблон:Math (its radical), then^[5]

This allows to give formulas for the Шаблон:Mathth cyclotomic polynomial when Шаблон:Math has at most one odd prime factor: If Шаблон:Math is an odd prime number, and Шаблон:Math and Шаблон:Math are positive integers, then:

For the other values of Шаблон:Math, the computation of the Шаблон:Mathth cyclotomic polynomial is similarly reduced to that of <math>\Phi_q(x),</math> where Шаблон:Math is the product of the distinct odd prime divisors of Шаблон:Math. To deal with this case, one has that, for Шаблон:Math prime and not dividing Шаблон:Math,^[6]

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. Several survey papers give an overview.^[7]

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}.^[8]

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 its expression 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, <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 Φ_n. 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.^[9]

A combination of theorems of Bateman resp. Vaughan statesШаблон:R that 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 formula

Let n be odd, square-free, and greater than 3. Then:^[10]^[11]

where both A_n(z) and B_n(z) have integer coefficients, A_n(z) has degree φ(n)/2, and B_n(z) has 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 ≡ 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

where both U_n(z) and V_n(z) have integer coefficients, U_n(z) has degree φ(n)/2, and V_n(z) has 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),

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

where both C_n(z) and D_n(z) have integer coefficients, C_n(z) has degree φ(n), and D_n(z) has 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 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>3\leq p\leq q\leq r</math> are three prime numbers.^[12]

Cyclotomic polynomials over a finite field and over the Шаблон:Math-adic integers

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

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

Polynomial values

Шаблон:Unreferenced section

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

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

For Шаблон:Math, one has

<math>\Phi_n(1) =1</math> if Шаблон:Math is not a prime power,

<math>\Phi_n(1) =p</math> if <math>n=p^k</math> is a prime power with Шаблон:Math.

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

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

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

If Шаблон:Math is a positive integer and Шаблон:Math is an integer, then (see below for a proof)

where

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

This implies that, if Шаблон:Math is an odd prime divisor of <math>\Phi_n(b),</math> then either Шаблон:Math is a divisor of Шаблон:Math or Шаблон:Math is a divisor of Шаблон: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 Шаблон:Math and Шаблон: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 Шаблон:Math such that Шаблон:Math is the multiplicative order of Шаблон:Math modulo Шаблон:Math. This fraction may be even only when Шаблон:Math is odd. In this case, the multiplicative order of Шаблон:Math modulo Шаблон:Math is always Шаблон:Math.

There are many pairs Шаблон:Math with Шаблон:Math such that <math>\Phi_n(b)</math> is prime. In fact, Bunyakovsky conjecture implies that, for every Шаблон:Math, there are infinitely many Шаблон:Math such that <math>\Phi_n(b)</math> is prime. See Шаблон:Oeis for the list of the smallest Шаблон:Math such that <math>\Phi_n(b)</math> is prime (the smallest Шаблон:Math such that <math>\Phi_n(b)</math> is prime is about <math>\lambda \cdot \varphi(n)</math>, where <math>\lambda</math> is Euler–Mascheroni constant, and <math>\varphi</math> is Euler's totient function). See also Шаблон:Oeis for the list of the smallest primes of the form <math>\Phi_n(b)</math> with Шаблон:Math and Шаблон:Math, and, more generally, Шаблон:Oeis, for the smallest positive integers of this form. Шаблон: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 Шаблон: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 Шаблон:Math is the product of the <math>\Phi_k(x)</math> for Шаблон:Math dividing Шаблон:Math and different of Шаблон:Math. If Шаблон:Math is a prime divisor of multiplicity Шаблон:Math in Шаблон:Math, then <math>\Phi_p(x), \Phi_{p^2}(x), \cdots, \Phi_{p^m}(x)</math> divide Шаблон:Math, and their values at Шаблон:Math are Шаблон:Math factors equal to Шаблон:Math of <math>n=P(1).</math> As Шаблон:Math is the multiplicity of Шаблон:Math in Шаблон:Math, Шаблон:Math cannot divide the value at Шаблон:Math of the other factors of <math>P(x).</math> Thus there is no prime that divides <math>\Phi_n(1).</math>

If Шаблон:Math is the multiplicative order of Шаблон:Math modulo Шаблон: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 Шаблон: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, Шаблон:Math would not be the multiplicative order of Шаблон:Math modulo Шаблон:Math.

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

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

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

Шаблон:Cob

Applications

Using <math>\Phi_n</math>, one can give an elementary proof for the infinitude of primes congruent to 1 modulo n,^[14] which is a special case of Dirichlet's theorem on arithmetic progressions. Шаблон: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> Шаблон:Cob

References

Шаблон:Reflist

External links

↑ Шаблон:Citation
↑ Шаблон:Cite OEIS
↑ Шаблон:Citation
↑ Шаблон:Lang Algebra
↑ Шаблон:Citation.
↑ Шаблон:MathWorld
↑ Шаблон:Cite arXiv
↑ Шаблон:Citation
↑ Шаблон:Citation
↑ Gauss, DA, Articles 356-357
↑ Шаблон:Citation
↑ Шаблон:Citation
↑ Шаблон:Citation.
↑ S. Shirali. Number Theory. Orient Blackswan, 2004. p. 67. Шаблон:Isbn

[1] Шаблон:Citation

[2] Шаблон:Cite OEIS

[3] Шаблон:Citation

[4] Шаблон:Lang Algebra

[5] Шаблон:Citation.

[WolframCyclotomic-6] Шаблон:MathWorld

[arXivSanna-7] Шаблон:Cite arXiv

[8] Шаблон:Citation

[Mai2008-9] Шаблон:Citation

[10] Gauss, DA, Articles 356-357

[riesel-11] Шаблон:Citation

[beiter68-12] Шаблон:Citation

[13] Шаблон:Citation.

[14] S. Shirali. Number Theory. Orient Blackswan, 2004. p. 67. Шаблон:Isbn

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

Партнерские ресурсы
Криптовалюты	Обмен криптовалют - www.bestchange.ru Криптовалютная биржа CoinEx Криптовалютная биржа Binance HIVE OS - операционная система для майнинга e4pool - Мультивалютный пул для майнинга.
Магазины	AliExpress — глобальная виртуальная (в Интернете) торговая площадка, предоставляющая возможность покупать товары производителей из КНР; computeruniverse.net - Интернет-магазин компьютеров(Промо код 5 Евро на первую покупку:FWWC3ZKQ);
Хостинг	DigitalOcean - американский провайдер облачных инфраструктур, с главным офисом в Нью-Йорке и с центрами обработки данных по всему миру;
Разное	Викиум - Онлайн-тренажер для мозга Like Центр - Центр поддержки и развития предпринимательства. Gamersbay - лучший магазин по бустингу для World of Warcraft. Ноотропы OmniMind N°1 - Усиливает мозговую активность. Повышает мотивацию. Улучшает память. Санкт-Петербургская школа телевидения - это федеральная сеть образовательных центров, которая имеет филиалы в 37 городах России. Lingualeo.com — интерактивный онлайн-сервис для изучения и практики английского языка в увлекательной игровой форме. Junyschool (Джунискул) – международная школа программирования и дизайна для детей и подростков от 5 до 17 лет, где ученики осваивают компьютерную грамотность, развивают алгоритмическое и креативное мышление, изучают основы программирования и компьютерной графики, создают собственные проекты: игры, сайты, программы, приложения, анимации, 3D-модели, монтируют видео. Умназия - Интерактивные онлайн-курсы и тренажеры для развития мышления детей 6-13 лет SkillBox - это один из лидеров российского рынка онлайн-образования. Среди партнеров Skillbox ведущий разработчик сервисного дизайна AIC, медиа-компания Yoola, первое и самое крупное русскоязычное аналитическое агентство Tagline, онлайн-школа дизайна и иллюстрации Bang! Bang! Education, оператор PR-рынка PACO, студия рисования Draw&Go, агентство performance-маркетинга Ingate, scrum-студия Sibirix, имидж-лаборатория Персона. «Нетология» — это университет по подготовке и дополнительному обучению специалистов в области интернет-маркетинга, управления проектами и продуктами, дизайна, Data Science и разработки. В рамках Нетологии студенты получают ценные теоретические знания от лучших экспертов Рунета, выполняют практические задания на отработку полученных навыков, общаются с экспертами и единомышленниками. Познакомиться со всеми продуктами подробнее можно на сайте https://netology.ru, линейка курсов и профессий постоянно обновляется. StudyBay Brazil – это онлайн биржа для португалоговорящих студентов и авторов! Студент получает уникальную работу любого уровня сложности и больше свободного времени, в то время как у автора появляется дополнительный заработок и бесценный опыт. Автор24 — самая большая в России площадка по написанию учебных работ: контрольные и курсовые работы, дипломы, рефераты, решение задач, отчеты по практике, а так же любой другой вид работы. Сервис сотрудничает с более 70 000 авторов. Более 1 000 000 работ уже выполнено. StudyBay – это онлайн биржа для англоязычных студентов и авторов! Студент получает уникальную работу любого уровня сложности и больше свободного времени, в то время как у автора появляется дополнительный заработок и бесценный опыт.

Английская Википедия:Cyclotomic polynomial

Содержание

Examples

Properties

Fundamental tools

Easy cases for computation

Integers appearing as coefficients

Gauss's formula

Lucas's formula

Sister Beiter conjecture

Cyclotomic polynomials over a finite field and over the Шаблон:Math-adic integers

Polynomial values

Applications

See also

References

Further reading

External links

Навигация

Действия на странице

Действия на странице

Персональные инструменты

Навигация

Поиск

Инструменты