Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Cyclotomic polynomial
Summary
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
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
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.
If n is a prime number, then
If n = 2p where p is an odd prime number, then
For n up to 30, the cyclotomic polynomials are:
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 (357) and this polynomial is the first one that has a coefficient other than 1, 0, or −1:
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. 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
which means that each n-th root of unity is a primitive d-th root of unity for a unique d dividing n.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.
Ontological neighbourhood
Related courses (3)
MATH-494: Topics in arithmetic geometry
P-adic numbers are a number theoretic analogue of the real numbers, which interpolate between arithmetics, analysis and geometry. In this course we study their basic properties and give various applic
MATH-489: Number theory II.c - Cryptography
The goal of the course is to introduce basic notions from public key cryptography (PKC) as well as basic number-theoretic methods and algorithms for cryptanalysis of protocols and schemes based on PKC
MATH-310: Algebra
This is an introduction to modern algebra: groups, rings and fields.
Related lectures (33)
Gaussian Lemma III: Irreducibility and Primitive Polynomials
Explains irreducibility in polynomial equations and the properties of primitive polynomials.
Generalized Integrals: Elementary Cases
Explores elementary cases of generalized integrals, convergence criteria, and the interpretation of integrals of type i and ii.
Algebraic Closure of Qp
Covers the algebraic closure of Qp and the definition of p-adic complex numbers, exploring roots' continuous dependence on coefficients.
Related publications (32)
K3 surfaces, cyclotomic polynomials and orthogonal groups
Let X be a complex projective K3 surface and let T-X be its transcendental lattice; the characteristic polynomials of isometries of T-X induced by automorphisms of X are powers of cyclotomic polynomials. Which powers of cyclotomic polynomials occur? The ai ...
Springer Int Publ Ag2024Linear Complexity Self-Attention With 3rd Order Polynomials
Grigorios Chrysos, Filippos Kokkinos
Self-attention mechanisms and non-local blocks have become crucial building blocks for state-of-the-art neural architectures thanks to their unparalleled ability in capturing long-range dependencies in the input. However their cost is quadratic with the nu ...
Los Alamitos2023Related people (5)
Related concepts (16)
Cyclotomic field
In number theory, a cyclotomic field is a number field obtained by adjoining a complex root of unity to Q, the field of rational numbers. Cyclotomic fields played a crucial role in the development of modern algebra and number theory because of their relation with Fermat's Last Theorem. It was in the process of his deep investigations of the arithmetic of these fields (for prime n) – and more precisely, because of the failure of unique factorization in their rings of integers – that Ernst Kummer first introduced the concept of an ideal number and proved his celebrated congruences.
Polynomial ring
In mathematics, especially in the field of algebra, a polynomial ring or polynomial algebra is a ring (which is also a commutative algebra) formed from the set of polynomials in one or more indeterminates (traditionally also called variables) with coefficients in another ring, often a field. Often, the term "polynomial ring" refers implicitly to the special case of a polynomial ring in one indeterminate over a field. The importance of such polynomial rings relies on the high number of properties that they have in common with the ring of the integers.
AKS primality test
The AKS primality test (also known as Agrawal–Kayal–Saxena primality test and cyclotomic AKS test) is a deterministic primality-proving algorithm created and published by Manindra Agrawal, Neeraj Kayal, and Nitin Saxena, computer scientists at the Indian Institute of Technology Kanpur, on August 6, 2002, in an article titled "PRIMES is in P". The algorithm was the first one which is able to determine in polynomial time, whether a given number is prime or composite and this without relying on mathematical conjectures such as the generalized Riemann hypothesis.