Cohn's irreducibility criterion

Arthur Cohn's irreducibility criterion is a sufficient condition for a polynomial to be irreducible in Z [ x ] —that is, for it to be unfactorable into the product of lower-degree polynomials with integer coefficients.

The criterion is often stated as follows:

If a prime number p is expressed in base 10 as p = a m 10 m + a m − 1 10 m − 1 + ⋯ + a 1 10 + a 0 (where 0 ≤ a i ≤ 9 ) then the polynomial f ( x ) = a m x m + a m − 1 x m − 1 + ⋯ + a 1 x + a 0 is irreducible in Z [ x ] .

The theorem can be generalized to other bases as follows:

Assume that b ≥ 2 is a natural number and p ( x ) = a k x k + a k − 1 x k − 1 + ⋯ + a 1 x + a 0 is a polynomial such that 0 ≤ a i ≤ b − 1 . If p ( b ) is a prime number then p ( x ) is irreducible in Z [ x ] .

The base-10 version of the theorem is 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.