Cohn's irreducibility criterion
Encyclopedia
Arthur Cohn's irreducibility criterion is a test to determine whether a polynomial
is irreducible
in
.
The criterion is often stated as follows:
The theorem can be generalized to other bases as follows:
The base-10 version of the theorem attributed to Cohn by Pólya
and Szegő
in one of their books while the generalization to any base, 2 or greater, is due to Brillhart, Filaseta, and Odlyzko
.
In 2002, Ram Murty gave a simplified proof as well as some history of the theorem in a paper that is available online..
The converse of this criterion is that, if p is an irreducible polynomial with integer coefficients that have greatest common divisor 1, then there exists a base such that the coefficients of p form the representation of a prime number in that base; this is the Bunyakovsky conjecture
and its truth or falsity remains an open question.
Polynomial
In mathematics, a polynomial is an expression of finite length constructed from variables and constants, using only the operations of addition, subtraction, multiplication, and non-negative integer exponents...
is irreducible
Irreducible polynomial
In mathematics, the adjective irreducible means that an object cannot be expressed as the product of two or more non-trivial factors in a given set. See also factorization....
in
Polynomial ring
In mathematics, especially in the field of abstract algebra, a polynomial ring is a ring formed from the set of polynomials in one or more variables with coefficients in another ring. Polynomial rings have influenced much of mathematics, from the Hilbert basis theorem, to the construction of...
.
The criterion is often stated as follows:
- If a prime numberPrime numberA prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. A natural number greater than 1 that is not a prime number is called a composite number. For example 5 is prime, as only 1 and 5 divide it, whereas 6 is composite, since it has the divisors 2...
is expressed in base 10 as 
(where 
) then the polynomial
- is irreducible in
.
The theorem can be generalized to other bases as follows:
- Assume that
is a natural number and 
is a polynomial such that 
. If 
is a prime number then 
is irreducible in 
.
The base-10 version of the theorem attributed to Cohn by Pólya
George Pólya
George Pólya was a Hungarian mathematician. He was a professor of mathematics from 1914 to 1940 at ETH Zürich and from 1940 to 1953 at Stanford University. He made fundamental contributions to combinatorics, number theory, numerical analysis and probability theory...
and Szegő
Gábor Szego
Gábor Szegő was a Hungarian mathematician. He was one of the foremost analysts of his generation and made fundamental contributions to the theory of Toeplitz matrices and orthogonal polynomials.-Life:...
in one of their books while the generalization to any base, 2 or greater, is due to Brillhart, Filaseta, and Odlyzko
Andrew Odlyzko
Andrew Michael Odlyzko is a mathematician and a former head of the University of Minnesota's Digital Technology Center.In the field of mathematics he has published extensively on analytic number theory, computational number theory, cryptography, algorithms and computational complexity,...
.
In 2002, Ram Murty gave a simplified proof as well as some history of the theorem in a paper that is available online..
The converse of this criterion is that, if p is an irreducible polynomial with integer coefficients that have greatest common divisor 1, then there exists a base such that the coefficients of p form the representation of a prime number in that base; this is the Bunyakovsky conjecture
Bunyakovsky conjecture
The Bunyakovsky conjecture stated in 1857 by the Russian mathematician Viktor Bunyakovsky, claims that an irreducible polynomial of degree two or higher with integer coefficients generates for natural arguments either an infinite set of numbers with greatest common divisor exceeding unity, or...
and its truth or falsity remains an open question.
Historical notes
- Polya and Szegő gave their own generalization but it has many side conditions (on the locations of the roots, for instance) so it lacks the elegance of Brillhart's, Filaseta's, and Odlyzko's generalization.
- It is clear from context that the "A. Cohn" mentioned by Polya and Szegő is Arthur Cohn, a student of Issai SchurIssai SchurIssai Schur was a mathematician who worked in Germany for most of his life. He studied at Berlin...
who was awarded his PhD in BerlinBerlinBerlin is the capital city of Germany and is one of the 16 states of Germany. With a population of 3.45 million people, Berlin is Germany's largest city. It is the second most populous city proper and the seventh most populous urban area in the European Union...
in 1921.