Irreducible polynomial whose roots are nth roots of unity
In mathematics, the nth cyclotomic polynomial, for any positive integer n, is the unique irreducible polynomial with integer coefficients that is a divisor of
and is not a divisor of
for any k < n. Its roots are all nth primitive roots of unity
, 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
![{\displaystyle \Phi _{n}(x)=\prod _{\stackrel {1\leq k\leq n}{\gcd(k,n)=1}}\left(x-e^{2i\pi {\frac {k}{n}}}\right).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/554f883b91a211f03701b1cfda4815e70d8abd9d)
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 (
is an example of such a root).
An important relation linking cyclotomic polynomials and primitive roots of unity is
![{\displaystyle \prod _{d\mid n}\Phi _{d}(x)=x^{n}-1,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1babe98bf5909455748bbb1169acdf380adb7f06)
showing that x is a root of
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
![{\displaystyle \Phi _{n}(x)=1+x+x^{2}+\cdots +x^{n-1}=\sum _{k=0}^{n-1}x^{k}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5842932945a8fff53f2877715b671c3b3d272b73)
If n = 2p where p is a prime number other than 2, then
![{\displaystyle \Phi _{2p}(x)=1-x+x^{2}-\cdots +x^{p-1}=\sum _{k=0}^{p-1}(-x)^{k}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ab6c3fc93d4f9c6c0554f59af8f7906e07ff0579)
For n up to 30, the cyclotomic polynomials are:[2]
![{\displaystyle {\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c080d78ddb6bf437db6ba043144f8715ad9d86e7)
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]
![{\displaystyle {\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}-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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/41084e04f476e069d8611b42928fe6756ec88070)
Properties
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
, or in other words the number of nth primitive roots of unity, is
, where
is Euler's totient function.
The fact that
is an irreducible polynomial of degree
in the ring
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
![{\displaystyle {\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b2bb6a3e04511af16d40dfb0ba2f8e12411c24ae)
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
to be expressed as an explicit rational fraction:
![{\displaystyle \Phi _{n}(x)=\prod _{d\mid n}(x^{d}-1)^{\mu \left({\frac {n}{d}}\right)},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/64cbe93ef8e96d78b85c61b484546188e08c06d4)
where
is the Möbius function.
The cyclotomic polynomial
may be computed by (exactly) dividing
by the cyclotomic polynomials of the proper divisors of n previously computed recursively by the same method:
![{\displaystyle \Phi _{n}(x)={\frac {x^{n}-1}{\prod _{\stackrel {d|n}{{}_{d<n}}}\Phi _{d}(x)}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9ac6f6a04ffa6d1549edcfee43768c9377fc16a3)
(Recall that
.)
This formula defines an algorithm for computing
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
![{\displaystyle \Phi _{n}(x)=1+x+x^{2}+\cdots +x^{n-1}=\sum _{k=0}^{n-1}x^{k}\;.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d49a7ed2dbc65e06d37df681fabebbcad54636b6)
If n is an odd integer greater than one, then
![{\displaystyle \Phi _{2n}(x)=\Phi _{n}(-x)\;.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ac412cecbef9f7609bf8e2eb4716a5ed3f867a3f)
In particular, if n = 2p is twice an odd prime, then (as noted above)
![{\displaystyle \Phi _{n}(x)=1-x+x^{2}-\cdots +x^{p-1}=\sum _{k=0}^{p-1}(-x)^{k}\;.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d30e0f0b6dcca6d4bac6063b26c3e7b3845586d5)
If n = pm is a prime power (where p is prime), then
![{\displaystyle \Phi _{n}(x)=\Phi _{p}(x^{p^{m-1}})=\sum _{k=0}^{p-1}x^{kp^{m-1}}\;.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/219b42e5c4ca98b9a49db40f1365c5f585b8e169)
More generally, if n = pmr with r relatively prime to p, then
![{\displaystyle \Phi _{n}(x)=\Phi _{pr}(x^{p^{m-1}})\;.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/97aa9848f249dbd15b923128d4c7245daa37b302)
These formulas may be applied repeatedly to get a simple expression for any cyclotomic polynomial
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]
![{\displaystyle \Phi _{n}(x)=\Phi _{q}(x^{n/q})\;.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a79ae9e5de884e8b9aaed1873a107a3fa9ab9932)
This allows formulas to be given for the nth 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
![{\displaystyle \Phi _{2^{h}}(x)=x^{2^{h-1}}+1\;,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/641cadc090b170f57cbcfa6461ecbb33f8ff5863)
![{\displaystyle \Phi _{p^{k}}(x)=\sum _{j=0}^{p-1}x^{jp^{k-1}}\;,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/dc4e05834c6ad790f0120cca74bf54cbce8c9e9d)
![{\displaystyle \Phi _{2^{h}p^{k}}(x)=\sum _{j=0}^{p-1}(-1)^{j}x^{j2^{h-1}p^{k-1}}\;.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/17fc82297cc0afcd1eb6dc9b5a07196c1502f261)
For the other values of n, the computation of the nth cyclotomic polynomial is similarly reduced to that of
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]
![{\displaystyle \Phi _{np}(x)=\Phi _{n}(x^{p})/\Phi _{n}(x)\;.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3be9930b8339704f56e1ea7e0ef21b5603a05752)
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
are all in the set {1, −1, 0}.[8]
The first cyclotomic polynomial for a product of three different odd prime factors is
it has a coefficient −2 (see its expression above). The converse is not true:
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.,
has coefficients running from −22 to 23,
, 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) > nk 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
, we have
![{\displaystyle A(n)<e^{\left(n^{(\log 2+\varepsilon )/(\log \log n)}\right)}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/690257ec01cf505037d774e0c9dfc78a34188653)
for all sufficiently large positive integers
, and on the other hand, we have
![{\displaystyle A(n)>e^{\left(n^{(\log 2)/(\log \log n)}\right)}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0533abec427830c376ef96f2b92b2f646189def9)
for infinitely many positive integers
. This implies in particular that univariate polynomials (concretely
for infinitely many positive integers
) can have factors (like
) whose coefficients are superpolynomially larger than the original coefficients. This is not too far from the general Landau-Mignotte bound.
Let n be odd, square-free, and greater than 3. Then:[10][11]
![{\displaystyle 4\Phi _{n}(z)=A_{n}^{2}(z)-(-1)^{\frac {n-1}{2}}nz^{2}B_{n}^{2}(z)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/df8fc094000e0de1481492d5c014d7bfb1dc011f)
where both An(z) and Bn(z) have integer coefficients, An(z) has degree φ(n)/2, and Bn(z) has degree φ(n)/2 − 2. Furthermore, An(z) is palindromic when its degree is even; if its degree is odd it is antipalindromic. Similarly, Bn(z) is palindromic unless n is composite and ≡ 3 (mod 4), in which case it is antipalindromic.
The first few cases are
![{\displaystyle {\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f0a83de9b0cde73a918cf03c71e45b6ad3fcdf33)
Let n be odd, square-free and greater than 3. Then[11]
![{\displaystyle \Phi _{n}(z)=U_{n}^{2}(z)-(-1)^{\frac {n-1}{2}}nzV_{n}^{2}(z)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c937939a4fab9005464e32be4537cbd72f07f340)
where both Un(z) and Vn(z) have integer coefficients, Un(z) has degree φ(n)/2, and Vn(z) has degree φ(n)/2 − 1. This can also be written
![{\displaystyle \Phi _{n}\left((-1)^{\frac {n-1}{2}}z\right)=C_{n}^{2}(z)-nzD_{n}^{2}(z).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/61f72459a3e28168ff7ad6ce7693e296c3371519)
If n is even, square-free and greater than 2 (this forces n/2 to be odd),
![{\displaystyle \Phi _{\frac {n}{2}}\left(-z^{2}\right)=\Phi _{2n}(z)=C_{n}^{2}(z)-nzD_{n}^{2}(z)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cc5f206a65aee6dccf1da7647276f6a0c8b55276)
where both Cn(z) and Dn(z) have integer coefficients, Cn(z) has degree φ(n), and Dn(z) has degree φ(n) − 1. Cn(z) and Dn(z) are both palindromic.
The first few cases are:
![{\displaystyle {\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b0cca61f37705f3e9001225f94a45b1f9f92919b)
Sister Beiter conjecture
The Sister Beiter conjecture is concerned with the maximal size (in absolute value)
of coefficients of ternary cyclotomic polynomials
where
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
factorizes into
irreducible polynomials of degree d, where
is Euler's totient function and d is the multiplicative order of p modulo n. In particular,
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
, the degree of
.[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
for every n ≥ 3 (this follows from the fact that the roots of a cyclotomic polynomial are all non-real, for n ≥ 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 ≥ 3, as the cases n = 1 and n = 2 are trivial (one has
and
).
For n ≥ 2, one has
![{\displaystyle \Phi _{n}(0)=1,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9a7fdfed3034b83187060d2b06310d11a1ca7edc)
if n is not a prime power,
if
is a prime power with k ≥ 1.
The values that a cyclotomic polynomial
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
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
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)
![{\displaystyle \Phi _{n}(b)=2^{k}gh,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c6a463c9cb50010db79e0b28f5110406c5a431ae)
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
then either n is a divisor of p − 1 or p is a divisor of n. In the latter case,
does not divide
Zsigmondy's theorem implies that the only cases where b > 1 and h = 1 are
![{\displaystyle {\begin{aligned}\Phi _{1}(2)&=1\\\Phi _{2}\left(2^{k}-1\right)&=2^{k}&&k>0\\\Phi _{6}(2)&=3\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a4fde95495f0213d51e76724b6b71e019e012d25)
It follows from above factorization that the odd prime factors of
![{\displaystyle {\frac {\Phi _{n}(b)}{\gcd(n,\Phi _{n}(b))}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f7ff7d5021231b6be2f02e553f7ad21f3a8df43c)
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
is prime. In fact, Bunyakovsky conjecture implies that, for every n, there are infinitely many b > 1 such that
is prime. See OEIS: A085398 for the list of the smallest b > 1 such that
is prime (the smallest b > 1 such that
is prime is about
, where
is Euler–Mascheroni constant, and
is Euler's totient function). See also OEIS: A206864 for the list of the smallest primes of the form
with n > 2 and b > 1, and, more generally, OEIS: A206942, for the smallest positive integers of this form.
Proofs |
- Values of
If is a prime power, then ![{\displaystyle \Phi _{n}(x)=1+x^{p^{k}}+x^{2p^{k}}+\cdots +x^{(p-1)p^{k}}\qquad {\text{and}}\qquad \Phi _{n}(1)=p.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6606dfdcd322e7784b97028b189d5148544a73c5)
- If n is not a prime power, let
we have and P is the product of the for k dividing n and different of 1. If p is a prime divisor of multiplicity m in n, then divide P(x), and their values at 1 are m factors equal to p of As m is the multiplicity of p in n, p cannot divide the value at 1 of the other factors of Thus there is no prime that divides ![{\displaystyle \Phi _{n}(1).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5b39da7c237d5834a0c9a5761856a4b1a274c499) - If n is the multiplicative order of b modulo p, then
By definition, If then p would divide another factor of and would thus divide showing that, if there would be the case, n would not be the multiplicative order of b modulo p. - The other prime divisors of
are divisors of n. Let p be a prime divisor of 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 and The resultant of and may be written 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 of Thus p divides n. - g and h are coprime. In other words, if p is a prime common divisor of n and
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
then does not divide Let n = pm. It suffices to prove that does not divide S(b) for some polynomial S(x), which is a multiple of We take ![{\displaystyle S(x)={\frac {x^{n}-1}{x^{m}-1}}=1+x^{m}+x^{2m}+\cdots +x^{(p-1)m}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/551762962e9ecdaf1fc57f40db724498bce17513)
- The multiplicative order of b modulo p divides gcd(n, p − 1), which is a divisor of m = n/p. Thus c = bm − 1 is a multiple of p. Now,
![{\displaystyle S(b)={\frac {(1+c)^{p}-1}{c}}=p+{\binom {p}{2}}c+\cdots +{\binom {p}{p}}c^{p-1}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/43bdf060bda14db74c6d3500d89dbf7d42512a58)
- As p is prime and greater than 2, all the terms but the first one are multiples of
This proves that ![{\displaystyle p^{2}\nmid \Phi _{n}(b).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9ab5ef919b0dd95c14fe5648d4c0e76458b1f09d) |
Applications
Using
, 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 is a finite list of primes congruent to modulo Let and consider . Let be a prime factor of (to see that decompose it into linear factors and note that 1 is the closest root of unity to ). Since we know that is a new prime not in the list. We will show that Let be the order of modulo Since we have . Thus . We will show that . Assume for contradiction that . Since ![{\displaystyle \prod _{d\mid m}\Phi _{d}(N)=N^{m}-1\equiv 0{\pmod {q}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7de009a15e9c3f9b01c292716a589d68b82ed9e9) we have ![{\displaystyle \Phi _{d}(N)\equiv 0{\pmod {q}},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ceb06caab454a30b335560dd3df937037c651bdd) for some . Then is a double root of ![{\displaystyle \prod _{d\mid n}\Phi _{d}(x)\equiv x^{n}-1{\pmod {q}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9fe766920d702c0b615a81f9e4e4e7bb6b6ff8a6) Thus must be a root of the derivative so ![{\displaystyle \left.{\frac {d(x^{n}-1)}{dx}}\right|_{N}\equiv nN^{n-1}\equiv 0{\pmod {q}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/28d182b720407e9d67b324dddd18d66486dbf23d) But and therefore This is a contradiction so . The order of which is , must divide . Thus |
See also
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
", 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
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.
- Gauss, Carl Friedrich (1801), Disquisitiones Arithmeticae (in Latin), Leipzig: Gerh. Fleischer
- Gauss, Carl Friedrich (1807) [1801], Recherches Arithmétiques (in French), translated by Poullet-Delisle, A.-C.-M., Paris: Courcier
- Gauss, Carl Friedrich (1889) [1801], Carl Friedrich Gauss' Untersuchungen über höhere Arithmetik (in German), translated by Maser, H., Berlin: Springer; Reprinted 1965, New York: Chelsea, ISBN 0-8284-0191-8
- Gauss, Carl Friedrich (1966) [1801], Disquisitiones Arithmeticae, translated by Clarke, Arthur A., New Haven: Yale, doi:10.12987/9780300194258, ISBN 978-0-300-09473-2; Corrected ed. 1986, New York: Springer, doi:10.1007/978-1-4939-7560-0, ISBN 978-0-387-96254-2
- Lemmermeyer, Franz (2000), Reciprocity Laws: from Euler to Eisenstein, Berlin: Springer, doi:10.1007/978-3-662-12893-0, ISBN 978-3-642-08628-1
External links
- Weisstein, Eric W., "Cyclotomic polynomial", MathWorld
- "Cyclotomic polynomials", Encyclopedia of Mathematics, EMS Press, 2001 [1994]
- OEIS sequence A013595 (Triangle of coefficients of cyclotomic polynomial Phi_n(x) (exponents in increasing order))
- OEIS sequence A013594 (Smallest order of cyclotomic polynomial containing n or −n as a coefficient)