Namespaces
Variants
Actions

Difference between revisions of "Cyclotomic polynomials"

From Encyclopedia of Mathematics
Jump to: navigation, search
m (tex encoded by computer)
m (fixing spaces)
Line 31: Line 31:
  
 
where  $  \zeta $
 
where  $  \zeta $
ranges over the primitive  $  n $-
+
ranges over the primitive  $  n $-th roots of unity (cf. [[Primitive root|Primitive root]]). The degree of  $  \Phi _ {n} ( x) $
th roots of unity (cf. [[Primitive root|Primitive root]]). The degree of  $  \Phi _ {n} ( x) $
 
 
is the number of integers  $  k $
 
is the number of integers  $  k $
 
among  $  1 \dots n $
 
among  $  1 \dots n $
Line 96: Line 95:
  
 
The equation  $  \Phi _ {n} ( x) = 0 $,  
 
The equation  $  \Phi _ {n} ( x) = 0 $,  
which gives all primitive  $  n $-
+
which gives all primitive  $  n $-th roots of unity, is known as the equation of division of the circle. The solution of this equation in trigonometric form is
th roots of unity, is known as the equation of division of the circle. The solution of this equation in trigonometric form is
 
  
 
$$  
 
$$  
Line 111: Line 109:
 
is irreducible, i.e.  $  k $
 
is irreducible, i.e.  $  k $
 
and  $  n $
 
and  $  n $
are relatively prime. The solution of the equation of division of the circle by radicals is closely connected with the problem of constructing a regular  $  n $-
+
are relatively prime. The solution of the equation of division of the circle by radicals is closely connected with the problem of constructing a regular  $  n $-gon, or with the equivalent problem of subdividing the circle into  $  n $
gon, or with the equivalent problem of subdividing the circle into  $  n $
 
 
equal parts; the latter problem can be solved using a straightedge and a pair of compasses if and only if the equation  $  \Phi _ {n} ( x) = 0 $
 
equal parts; the latter problem can be solved using a straightedge and a pair of compasses if and only if the equation  $  \Phi _ {n} ( x) = 0 $
 
is solvable in quadratic radicals. It was shown by C.F. Gauss in 1801 that this condition is satisfied if and only if
 
is solvable in quadratic radicals. It was shown by C.F. Gauss in 1801 that this condition is satisfied if and only if
Line 133: Line 130:
 
is equal to  $  \phi ( n) $,  
 
is equal to  $  \phi ( n) $,  
 
the value (at  $  n $)  
 
the value (at  $  n $)  
of the Euler  $  \phi $-
+
of the Euler  $  \phi $-function (cf. [[Euler function|Euler function]]).
function (cf. [[Euler function|Euler function]]).
 
  
 
Prime numbers of the form  $  2 ^ {2  ^ {k} } + 1 $
 
Prime numbers of the form  $  2 ^ {2  ^ {k} } + 1 $
Line 144: Line 140:
 
$  F _ {2} $,  
 
$  F _ {2} $,  
 
$  F _ {3} $,  
 
$  F _ {3} $,  
$  F _ {4} $(
+
$  F _ {4} $ (cf. [[#References|[a1]]], pp. 183-185).
cf. [[#References|[a1]]], pp. 183-185).
 
  
 
====References====
 
====References====
 
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  I. Stewart,  "Galois theory" , Chapman &amp; Hall  (1973)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  H. Davenport,  "Multiplicative number theory" , Springer  (1980)</TD></TR></table>
 
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  I. Stewart,  "Galois theory" , Chapman &amp; Hall  (1973)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  H. Davenport,  "Multiplicative number theory" , Springer  (1980)</TD></TR></table>

Revision as of 05:12, 7 March 2022


circular polynomials

The polynomials $ \Phi _ {1} , \Phi _ {2} \dots $ that satisfy the relation

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

where the product is taken over all positive divisors $ d $ of the number $ n $, including $ n $ itself. Over the field of complex numbers one has

$$ \Phi _ {n} ( x) = \ \prod _ \zeta ( x - \zeta ), $$

where $ \zeta $ ranges over the primitive $ n $-th roots of unity (cf. Primitive root). The degree of $ \Phi _ {n} ( x) $ is the number of integers $ k $ among $ 1 \dots n $ that are relatively prime with $ n $. The polynomials $ \Phi _ {n} ( x) $ can be computed recursively by dividing the polynomial $ x ^ {n} - 1 $ by the product of all $ \Phi _ {d} ( x) $, $ d < n $, $ d \mid n $. The coefficients lie in the prime field $ \mathbf Q $; in case of characteristic zero, they are integers. Thus,

$$ \Phi _ {1} ( x) = x - 1 ,\ \Phi _ {2} ( x) = x + 1 ,\ \ \Phi _ {3} ( x) = x ^ {2} + x + 1 . $$

If, moreover, $ n= p $ is prime, then

$$ \Phi _ {p} ( x) = \frac{x ^ {p} - 1 }{x - 1 } = x ^ {p - 1 } + \dots + x + 1 . $$

The polynomial $ \Phi _ {n} ( x) $ can be explicitly expressed using the Möbius function $ \mu $:

$$ \Phi _ {n} ( x) = \prod _ {d \mid n } ( x ^ {d} - 1 ) ^ {\mu ( n / d ) } . $$

For example,

$$ \Phi _ {12} ( x) = $$

$$ = \ ( x ^ {12} - 1) ( x ^ {6} - 1) ^ {-} 1 ( x ^ {4} - 1) ^ {-} 1 ( x ^ {3} - 1) ^ {0} ( x ^ {2} - 1) ( x - 1) ^ {0\ } = $$

$$ = \ \frac{x ^ {6} + 1 }{x ^ {2} + 1 } = x ^ {4} - x ^ {2} + 1 . $$

All the polynomials $ \Phi _ {n} ( x) $ are irreducible over the field of rational numbers, but they may be reducible over finite prime fields. Thus, the relation

$$ \Phi _ {12} ( x) = x ^ {4} - x ^ {2} + 1 = ( x ^ {2} + 5x + 1 ) ( x ^ {2} - 5x + 1 ) $$

is valid over the field of residues modulo 11.

The equation $ \Phi _ {n} ( x) = 0 $, which gives all primitive $ n $-th roots of unity, is known as the equation of division of the circle. The solution of this equation in trigonometric form is

$$ r _ {k} = \cos \frac{2 k \pi }{n} + i \sin \frac{2 k \pi }{n} = \ e ^ {2 k \pi i /n } , $$

where the fraction $ k / n $ is irreducible, i.e. $ k $ and $ n $ are relatively prime. The solution of the equation of division of the circle by radicals is closely connected with the problem of constructing a regular $ n $-gon, or with the equivalent problem of subdividing the circle into $ n $ equal parts; the latter problem can be solved using a straightedge and a pair of compasses if and only if the equation $ \Phi _ {n} ( x) = 0 $ is solvable in quadratic radicals. It was shown by C.F. Gauss in 1801 that this condition is satisfied if and only if

$$ n = 2 ^ {m} p _ {1} \dots p _ {s} , $$

where $ m $ is a non-negative integer and $ p _ {1} \dots p _ {s} $ are pairwise different prime numbers of the form $ 2 ^ {2 ^ {k} } + 1 $, where $ k $ is a non-negative integer.

References

[1] B.L. van der Waerden, "Algebra" , 1–2 , Springer (1967–1971) (Translated from German)
[2] A.K. Sushkevich, "Foundations of higher algebra" , Moscow-Leningrad (1941) (In Russian)

Comments

The degree of $ \Phi _ {n} ( x) $ is equal to $ \phi ( n) $, the value (at $ n $) of the Euler $ \phi $-function (cf. Euler function).

Prime numbers of the form $ 2 ^ {2 ^ {k} } + 1 $ with $ k $ a non-negative integer are called Fermat primes, these numbers are related to a problem of Fermat: When is the number $ F _ {k} = 2 ^ {2 ^ {k} } + 1 $, with $ k $ as before, prime? The only small Fermat primes are $ F _ {0} $, $ F _ {1} $, $ F _ {2} $, $ F _ {3} $, $ F _ {4} $ (cf. [a1], pp. 183-185).

References

[a1] I. Stewart, "Galois theory" , Chapman & Hall (1973)
[a2] H. Davenport, "Multiplicative number theory" , Springer (1980)
How to Cite This Entry:
Cyclotomic polynomials. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Cyclotomic_polynomials&oldid=52203
This article was adapted from an original article by I.V. Proskuryakov (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article