Cyclotomic polynomial

In mathematics, the nth cyclotomic polynomial, for any positive integer n, is the unique irreducible polynomial with integer coefficients that is a divisor of $x^{n}-1$ and is not a divisor of $x^{k}-1$ for any k < n. Its roots are all nth primitive roots of unity $e^{2i\pi {\frac {k}{n}}}$ , 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

\Phi _{n}(x)=\prod _{\stackrel {1\leq k\leq n}{\gcd(k,n)=1}}\left(x-e^{2i\pi {\frac {k}{n}}}\right).

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 ( $e^{2i\pi /n}$ is an example of such a root).

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

\prod _{d\mid n}\Phi _{d}(x)=x^{n}-1,

showing that $x$ is a root of $x^{n}-1$ if and only if it is a d th primitive root of unity for some d that divides n.^[1]

Examples

If n is a prime number, then

\Phi _{n}(x)=1+x+x^{2}+\cdots +x^{n-1}=\sum _{k=0}^{n-1}x^{k}.

If n = 2p where p is an odd prime number, then

\Phi _{2p}(x)=1-x+x^{2}-\cdots +x^{p-1}=\sum _{k=0}^{p-1}(-x)^{k}.

For n up to 30, the cyclotomic polynomials are:^[2]

{\begin{aligned}\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{aligned}}

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]

{\begin{aligned}\Phi _{105}(x)&=x^{48}+x^{47}+x^{46}-x^{43}-x^{42}-2x^{41}-x^{40}-x^{39}+x^{36}+x^{35}+x^{34}+x^{33}+x^{32}+x^{31}-x^{28}-x^{26}\\&\qquad \quad -x^{24}-x^{22}-x^{20}+x^{17}+x^{16}+x^{15}+x^{14}+x^{13}+x^{12}-x^{9}-x^{8}-2x^{7}-x^{6}-x^{5}+x^{2}+x+1.\end{aligned}}

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 $\Phi _{n}$ , or in other words the number of nth primitive roots of unity, is $\varphi (n)$ , where $\varphi$ is Euler's totient function.

The fact that $\Phi _{n}$ is an irreducible polynomial of degree $\varphi (n)$ in the ring $\mathbb {Z} [x]$ 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

{\begin{aligned}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{aligned}}

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 $\Phi _{n}(x)$ as an explicit rational fraction:

\Phi _{n}(x)=\prod _{d\mid n}(x^{d}-1)^{\mu \left({\frac {n}{d}}\right)},

where $\mu$ is the Möbius function.

The cyclotomic polynomial $\Phi _{n}(x)$ may be computed by (exactly) dividing $x^{n}-1$ by the cyclotomic polynomials of the proper divisors of n previously computed recursively by the same method:

\Phi _{n}(x)={\frac {x^{n}-1}{\prod _{\stackrel {d|n}{{}_{d<n}}}\Phi _{d}(x)}}

(Recall that $\Phi _{1}(x)=x-1$ .)

This formula defines an algorithm for computing $\Phi _{n}(x)$ 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 $n$ is a prime number, then

\Phi _{n}(x)=1+x+x^{2}+\cdots +x^{n-1}=\sum _{k=0}^{n-1}x^{k}.

If n is an odd integer greater than one, then

\Phi _{2n}(x)=\Phi _{n}(-x).

In particular, if $n = 2 p$ is twice an odd prime, then (as noted above)

\Phi _{n}(x)=1-x+x^{2}-\cdots +x^{p-1}=\sum _{k=0}^{p-1}(-x)^{k}.

If $n = p m$ is a prime power (where p is prime), then

\Phi _{n}(x)=\Phi _{p}(x^{p^{m-1}})=\sum _{k=0}^{p-1}x^{kp^{m-1}}.

More generally, if $n = p m r$ with $r$ relatively prime to $p$ , then

\Phi _{n}(x)=\Phi _{pr}(x^{p^{m-1}}).

These formulas may be applied repeatedly to get a simple expression for any cyclotomic polynomial $\Phi _{n}(x)$ in term of a cyclotomic polynomial of square free index: If $q$ is the product of the prime divisors of $n$ (its radical), then^[5]

\Phi _{n}(x)=\Phi _{q}(x^{n/q}).

This allows to give formulas for the $n$ th cyclotomic polynomial when $n$ has at most one odd prime factor: If $p$ is an odd prime number, and $h$ and $k$ are positive integers, then:

\Phi _{2^{h}}(x)=x^{2^{h-1}}+1

\Phi _{p^{k}}(x)=\sum _{j=0}^{p-1}x^{jp^{k-1}}

\Phi _{2^{h}p^{k}}(x)=\sum _{j=0}^{p-1}(-1)^{j}x^{j2^{h-1}p^{k-1}}

For the other values of $n$ , the computation of the $n$ th cyclotomic polynomial is similarly reduced to that of $\Phi _{q}(x),$ where $q$ is the product of the distinct odd prime divisors of $n$ . To deal with this case, one has that, for $p$ prime and not dividing $n$ ,^[6]

\Phi _{np}(x)=\Phi _{n}(x^{p})/\Phi _{n}(x).

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 $\Phi _{n}$ are all in the set {1, −1, 0}.^[8]

The first cyclotomic polynomial for a product of three different odd prime factors is $\Phi _{105}(x);$ it has a coefficient −2 (see its expression above). The converse is not true: $\Phi _{231}(x)=\Phi _{3\times 7\times 11}(x)$ 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., $\Phi _{15015}(x)=\Phi _{3\times 5\times 7\times 11\times 13}(x)$ has coefficients running from −22 to 23, $\Phi _{255255}(x)=\Phi _{3\times 5\times 7\times 11\times 13\times 17}(x)$ , 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^[7]^: 10 that on the one hand, for every $\varepsilon >0$ , we have

A(n)<e^{\left(n^{(\log 2+\varepsilon )/(\log \log n)}\right)}

for all sufficiently large positive integers $n$ , and on the other hand, we have

A(n)>e^{\left(n^{(\log 2)/(\log \log n)}\right)}

for infinitely many positive integers $n$ . This implies in particular that univariate polynomials (concretely $x^{n}-1$ for infinitely many positive integers $n$ ) can have factors (like $\Phi _{n}$ ) 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]

4\Phi _{n}(z)=A_{n}^{2}(z)-(-1)^{\frac {n-1}{2}}nz^{2}B_{n}^{2}(z)

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

{\begin{aligned}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{aligned}}

Lucas's formula

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

\Phi _{n}(z)=U_{n}^{2}(z)-(-1)^{\frac {n-1}{2}}nzV_{n}^{2}(z)

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

\Phi _{n}\left((-1)^{\frac {n-1}{2}}z\right)=C_{n}^{2}(z)-nzD_{n}^{2}(z).

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

\Phi _{\frac {n}{2}}\left(-z^{2}\right)=\Phi _{2n}(z)=C_{n}^{2}(z)-nzD_{n}^{2}(z)

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:

{\begin{aligned}\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{aligned}}

Sister Beiter conjecture

The Sister Beiter conjecture is concerned with the maximal size (in absolute value) $A(pqr)$ of coefficients of ternary cyclotomic polynomials $\Phi _{pqr}(x)$ where $3\leq p\leq q\leq r$ are three prime numbers.^[12]

Cyclotomic polynomials over a finite field and over the $p$ -adic integers

Over a finite field with a prime number $p$ of elements, for any integer $n$ that is not a multiple of $p$ , the cyclotomic polynomial $\Phi _{n}$ factorizes into ${\frac {\varphi (n)}{d}}$ irreducible polynomials of degree $d$ , where $\varphi (n)$ is Euler's totient function and $d$ is the multiplicative order of $p$ modulo $n$ . In particular, $\Phi _{n}$ is irreducible if and only if $p$ is a primitive root modulo $n$ , that is, $p$ does not divide $n$ , and its multiplicative order modulo $n$ is $\varphi (n)$ , the degree of $\Phi _{n}$ .^[13]

These results are also true over the $p$ -adic integers, since Hensel's lemma allows lifting a factorization over the field with $p$ elements to a factorization over the $p$ -adic integers.

Polynomial values

If $x$ takes any real value, then $\Phi _{n}(x)>0$ for every $n \geq 3$ (this follows from the fact that the roots of a cyclotomic polynomial are all non-real, for $n \geq 3$ ).

For studying the values that a cyclotomic polynomial may take when $x$ is given an integer value, it suffices to consider only the case $n \geq 3$ , as the cases $n = 1$ and $n = 2$ are trivial (one has $\Phi _{1}(x)=x-1$ and $\Phi _{2}(x)=x+1$ ).

For $n \geq 2$ , one has

\Phi _{n}(0)=1,

\Phi _{n}(1)=1

if

n

is not a prime power,

\Phi _{n}(1)=p

if

n=p^{k}

is a prime power with

k \geq 1

.

The values that a cyclotomic polynomial $\Phi _{n}(x)$ may take for other integer values of $x$ is strongly related with the multiplicative order modulo a prime number.

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

The definition of the multiplicative order implies that, if $n$ is the multiplicative order of $b$ modulo $p$ , then $p$ is a divisor of $\Phi _{n}(b).$ The converse is not true, but one has the following.

If $n > 0$ is a positive integer and $b > 1$ is an integer, then (see below for a proof)

\Phi _{n}(b)=2^{k}gh,

where

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

This implies that, if $p$ is an odd prime divisor of $\Phi _{n}(b),$ then either $n$ is a divisor of $p - 1$ or $p$ is a divisor of $n$ . In the latter case, $p^{2}$ does not divide $\Phi _{n}(b).$

Zsigmondy's theorem implies that the only cases where $b > 1$ and $h = 1$ are

{\begin{aligned}\Phi _{1}(2)&=1\\\Phi _{2}\left(2^{k}-1\right)&=2^{k}&&k>0\\\Phi _{6}(2)&=3\end{aligned}}

It follows from above factorization that the odd prime factors of

{\frac {\Phi _{n}(b)}{\gcd(n,\Phi _{n}(b))}}

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

There are many pairs $(n, b)$ with $b > 1$ such that $\Phi _{n}(b)$ is prime. In fact, Bunyakovsky conjecture implies that, for every $n$ , there are infinitely many $b > 1$ such that $\Phi _{n}(b)$ is prime. See OEIS: A085398 for the list of the smallest $b > 1$ such that $\Phi _{n}(b)$ is prime (the smallest $b > 1$ such that $\Phi _{n}(b)$ is prime is about $\lambda \cdot \varphi (n)$ , where $\lambda$ is Euler–Mascheroni constant, and $\varphi$ is Euler's totient function). See also OEIS: A206864 for the list of the smallest primes of the form $\Phi _{n}(b)$ with $n > 2$ and $b > 1$ , and, more generally, OEIS: A206942, for the smallest positive integers of this form.

Proofs

Values of $\Phi _{n}(1).$ If $n=p^{k+1}$ is a prime power, then

\Phi _{n}(x)=1+x^{p^{k}}+x^{2p^{k}}+\cdots +x^{(p-1)p^{k}}\qquad {\text{and}}\qquad \Phi _{n}(1)=p.

If

n

is not a prime power, let

P(x)=1+x+\cdots +x^{n-1},

we have

P(1)=n,

and

P

is the product of the

\Phi _{k}(x)

for

k

dividing

n

and different of

1

. If

p

is a prime divisor of multiplicity

m

in

n

, then

\Phi _{p}(x),\Phi _{p^{2}}(x),\cdots ,\Phi _{p^{m}}(x)

divide

P (x)

, and their values at

1

are

m

factors equal to

p

of

n=P(1).

As

m

is the multiplicity of

p

in

n

,

p

cannot divide the value at

1

of the other factors of

P(x).

Thus there is no prime that divides

\Phi _{n}(1).

If $n$ is the multiplicative order of $b$ modulo $p$ , then $p\mid \Phi _{n}(b).$ By definition, $p\mid b^{n}-1.$ If $p\nmid \Phi _{n}(b),$ then $p$ would divide another factor $\Phi _{k}(b)$ of $b^{n}-1,$ and would thus divide $b^{k}-1,$ showing that, if there would be the case, $n$ would not be the multiplicative order of $b$ modulo $p$ .

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

$g$ and $h$ are coprime. In other words, if $p$ is a prime common divisor of $n$ and $\Phi _{n}(b),$ then $n$ is not the multiplicative order of $b$ modulo $p$ . By Fermat's little theorem, the multiplicative order of $b$ is a divisor of $p - 1$ , and thus smaller than $n$ .

$g$ is square-free. In other words, if $p$ is a prime common divisor of $n$ and $\Phi _{n}(b),$ then $p^{2}$ does not divide $\Phi _{n}(b).$ Let $n = pm$ . It suffices to prove that $p^{2}$ does not divide $S (b)$ for some polynomial $S (x)$ , which is a multiple of $\Phi _{n}(x).$ We take

S(x)={\frac {x^{n}-1}{x^{m}-1}}=1+x^{m}+x^{2m}+\cdots +x^{(p-1)m}.

The multiplicative order of

b

modulo

p

divides

gcd(n, p - 1)

, which is a divisor of

m = n / p

. Thus

c = b m - 1

is a multiple of

p

. Now,

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

As

p

is prime and greater than 2, all the terms but the first one are multiples of

p^{2}.

This proves that

p^{2}\nmid \Phi _{n}(b).

Applications

Using $\Phi _{n}$ , 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.

Proof

Suppose $p_{1},p_{2},\ldots ,p_{k}$ is a finite list of primes congruent to $1$ modulo $n.$ Let $N=np_{1}p_{2}\cdots p_{k}$ and consider $\Phi _{n}(N)$ . Let $q$ be a prime factor of $\Phi _{n}(N)$ (to see that $\Phi _{n}(N)\neq \pm 1$ decompose it into linear factors and note that 1 is the closest root of unity to $N$ ). Since $\Phi _{n}(x)\equiv \pm 1{\pmod {x}},$ we know that $q$ is a new prime not in the list. We will show that $q\equiv 1{\pmod {n}}.$

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

Assume for contradiction that $m<n$ . Since

\prod _{d\mid m}\Phi _{d}(N)=N^{m}-1\equiv 0{\pmod {q}}

we have

\Phi _{d}(N)\equiv 0{\pmod {q}},

for some $d<n$ . Then $N$ is a double root of

\prod _{d\mid n}\Phi _{d}(x)\equiv x^{n}-1{\pmod {q}}.

Thus $N$ must be a root of the derivative so

\left.{\frac {d(x^{n}-1)}{dx}}\right|_{N}\equiv nN^{n-1}\equiv 0{\pmod {q}}.

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

References

^ Roman, Stephen (2008), Advanced Linear Algebra, Graduate Texts in Mathematics (Third ed.), Springer, p. 465 §18, ISBN 978-0-387-72828-5
^ Sloane, N. J. A. (ed.), "Sequence A013595", The On-Line Encyclopedia of Integer Sequences, OEIS Foundation
^ Brookfield, Gary (2016), "The coefficients of cyclotomic polynomials", Mathematics Magazine, 89 (3): 179–188, doi:10.4169/math.mag.89.3.179, JSTOR 10.4169/math.mag.89.3.179, MR 3519075
^ Lang, Serge (2002), Algebra, Graduate Texts in Mathematics, vol. 211 (Revised third ed.), New York: Springer-Verlag, ISBN 978-0-387-95385-4, MR 1878556
^ Cox, David A. (2012), "Exercise 12", Galois Theory (2nd ed.), John Wiley & Sons, p. 237, doi:10.1002/9781118218457, ISBN 978-1-118-07205-9.
^ Weisstein, Eric W., "Cyclotomic Polynomial", MathWorld
^ ^a ^b Sanna, Carlo (2021), "A Survey on Coefficients of Cyclotomic Polynomials", arXiv:2111.04034 [math.NT]
^ Isaacs, Martin (2009), Algebra: A Graduate Course, AMS Bookstore, p. 310, ISBN 978-0-8218-4799-2
^ Maier, Helmut (2008), "Anatomy of integers and cyclotomic polynomials", in De Koninck, Jean-Marie; Granville, Andrew; Luca, Florian (eds.), Anatomy of integers. Based on the CRM workshop, Montreal, Canada, March 13-17, 2006, CRM Proceedings and Lecture Notes, vol. 46, Providence, RI: American Mathematical Society, pp. 89–95, ISBN 978-0-8218-4406-9, Zbl 1186.11010
^ Gauss, DA, Articles 356-357
^ ^a ^b Riesel, Hans (1994), Prime Numbers and Computer Methods for Factorization (2nd ed.), Boston: Birkhäuser, pp. 309–316, 436, 443, ISBN 0-8176-3743-5
^ Beiter, Marion (April 1968), "Magnitude of the Coefficients of the Cyclotomic Polynomial $F_{pqr}(x)$ ", The American Mathematical Monthly, 75 (4): 370–372, doi:10.2307/2313416, JSTOR 2313416
^ Lidl, Rudolf; Niederreiter, Harald (2008), Finite Fields (2nd ed.), Cambridge University Press, p. 65.
^ S. Shirali. Number Theory. Orient Blackswan, 2004. p. 67. ISBN 81-7371-454-1

External links

[1] Roman, Stephen (2008), Advanced Linear Algebra, Graduate Texts in Mathematics (Third ed.), Springer, p. 465 §18, ISBN 978-0-387-72828-5

[2] Sloane, N. J. A. (ed.), "Sequence A013595", The On-Line Encyclopedia of Integer Sequences, OEIS Foundation

[3] Brookfield, Gary (2016), "The coefficients of cyclotomic polynomials", Mathematics Magazine, 89 (3): 179–188, doi:10.4169/math.mag.89.3.179, JSTOR 10.4169/math.mag.89.3.179, MR 3519075

[4] Lang, Serge (2002), Algebra, Graduate Texts in Mathematics, vol. 211 (Revised third ed.), New York: Springer-Verlag, ISBN 978-0-387-95385-4, MR 1878556

[5] Cox, David A. (2012), "Exercise 12", Galois Theory (2nd ed.), John Wiley & Sons, p. 237, doi:10.1002/9781118218457, ISBN 978-1-118-07205-9.

[WolframCyclotomic-6] Weisstein, Eric W., "Cyclotomic Polynomial", MathWorld

[arXivSanna-7] Sanna, Carlo (2021), "A Survey on Coefficients of Cyclotomic Polynomials", arXiv:2111.04034 [math.NT]

[8] Isaacs, Martin (2009), Algebra: A Graduate Course, AMS Bookstore, p. 310, ISBN 978-0-8218-4799-2

[Mai2008-9] Maier, Helmut (2008), "Anatomy of integers and cyclotomic polynomials", in De Koninck, Jean-Marie; Granville, Andrew; Luca, Florian (eds.), Anatomy of integers. Based on the CRM workshop, Montreal, Canada, March 13-17, 2006, CRM Proceedings and Lecture Notes, vol. 46, Providence, RI: American Mathematical Society, pp. 89–95, ISBN 978-0-8218-4406-9, Zbl 1186.11010

[10] Gauss, DA, Articles 356-357

[riesel-11] Riesel, Hans (1994), Prime Numbers and Computer Methods for Factorization (2nd ed.), Boston: Birkhäuser, pp. 309–316, 436, 443, ISBN 0-8176-3743-5

[beiter68-12] Beiter, Marion (April 1968), "Magnitude of the Coefficients of the Cyclotomic Polynomial $F_{pqr}(x)$ ", The American Mathematical Monthly, 75 (4): 370–372, doi:10.2307/2313416, JSTOR 2313416

[13] Lidl, Rudolf; Niederreiter, Harald (2008), Finite Fields (2nd ed.), Cambridge University Press, p. 65.

[14] S. Shirali. Number Theory. Orient Blackswan, 2004. p. 67. ISBN 81-7371-454-1

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]