## Testing irreducibility using prime numbers

Here’s a simple and nice test for irreducibility in that N told me about a year ago. (I just noticed this lying around while cleaning; I don’t have a year’s buffer like Raymond Chen.) Apologies for the ugly formatting; you’ll have to trust that the result (Theorem 1, or Corollary 8) is more beautiful than it looks. :-)

Actually I’m not sure why I wrote this originally, given that it’s all already well-explained in the originals and even partially on Wikipedia. Perhaps my proofs are different or simpler or I was bored or something.

**1. Irreducibility test **

In its simplest form, the test can be stated as follows.

Theorem 1Given a polynomial with integer coefficients, let . If there exists an integer such that is prime, then is irreducible.

For example, with the polynomial , we have , and is prime, which proves that it is irreducible. (We could also evaluate f at e.g. 7, 8, 9, or 10 to get the same conclusion.)

It follows directly from the following two results:

Lemma 2Given a polynomial with integer coefficients, let . Then for any root of , .

*Proof:* Let be any (complex) root of . As , either , or which means that . Thus in either case .

Lemma 3Given a polynomial with integer coefficients, suppose is prime for some such that for every root of . Then is irreducible.

*Proof:* Suppose can be factorized in as where and have nonzero degree. As is prime, at least one of and must be 1, say .

Let the roots of (over ) be . Then , where the leading coefficient of being an integer, . As each factor , this implies that , which is a contradiction.

A related nice result can be proved:

Theorem 4Let be a prime number, written in base as . Then thedigit polynomialis irreducible in .

Note that this result does not automatically follow from Theorem 1. Unless , could be as large as , and the fact that is prime does not help, as the theorem only applies for .

On the other hand, Theorem 1 is “best-possible” in terms of the absolute values of the coefficients: consider, for , the polynomials , or , for both of which , and is prime!

Clearly, then, Theorem 4 depends not only on being prime, but also on the signs of the coefficients. It turns out that we only need the sign of :

Lemma 5Given a polynomial with integer coefficients such that , let . Then for any root of , either or .

*Proof:* If , we are done. Else, as before, .

So if , then , so which means that , from which we get .

We can now prove the theorem for bases other than 2: *Proof:* As and all the coefficients lie between and , we have . Thus by Lemma 5, for any root of , we have if . As is prime, Lemma 3 now implies the irreducibility of .

The theorem is also true for base 2, see \cite{Murty} or \cite{BFO}.

**2. Generalisations **

We can consider a few variants of Lemma 2 that are stronger when .

Lemma 6Given a polynomial with integer coefficients, let be the first nonzero coefficient of after (i.e., if ). Let . Then for any root of , .

*Proof:* If , we are done. Else, which means that . Thus in either case .

Lemma 7Given a polynomial with integer coefficients, let . Then for any root of , .

*Proof:* If , we are done. Else, which means that , i.e., .

We can combine all these into the following result.

Corollary 8Given a polynomial with integer coefficients and , let be the first nonzero coefficient of after (i.e., if ). Let . Let . If there exists an integer such that is prime, then is irreducible.

*Proof:* As in Lemmas 5, 6 and 7, we can prove that either or . Lemma 3 then gives the result.

Perhaps the “generalisations” in this section, as they contain no new idea, are like the “cheap generalization” Pólya talks about:

There are two kinds of generalizations. One is cheap and the other is valuable.It is easy to generalize by diluting a little idea with a big terminology. It is much more difficult to prepare a refined and condensed extract from several good ingredients.

— [G. Pólya]

And also

However, one must not forget that there are two kinds of generalization, one facile and one valuable. One is generalization by dilution, the other is generalization by concentration. Dilution means boiling the meat in a large quantity of water into a thin soup; concentration means condensing a large amount of nutritive material into an essence. The unification of concepts which in the usual view appear to be far removed from each other is concentration. Thus, for example, group theory has concentrated ideas which formerly were found scattered in algebra, number theory, geometry and analysis and which appeared to be very different. Examples of generalizations by dilution would be still easier to quote, but this would be at the risk of offending sensibilities.

— [Pólya and Szegö]

**3. Remarks and historical notes **

4 was proved for base 10 by Arthur Cohn, a student of Issai Schur, as attributed by Pólya and Szegö in their book, first published in 1925.\cite{PolyaSzego}

It was extended to all bases by Brillhart, Filaseta and Odlyzko in 1981.\cite{BFO} They point out that not all irreducible polynomials can be shown irreducible by a theorem of this sort, as there exist irreducible polynomials that never take a prime value at integral arguments, e.g., .

A simplified proof was given by M. Ram Murty\cite{Murty}, who points out that this theorem is a (strong) converse to Buniakowski’s conjecture, that any irreducible polynomial takes primes values infinitely often, unless it has a common divisor—this is a generalization of Dirichlet’s theorem about primes in arithmetic progressions. He also extends it to an analogue in function fields. He observes that this theorem sometimes applies when most traditional tests fail, e.g., is reducible modulo for every , but is prime which proves that it is irreducible.

**4. References**

[BFO] John Brillhart, Michael Filaseta, and Andrew Odlyzko. On an irreducibility theorem of A. Cohn. *Canadian Journal of Mathematics*, 33(5):1055–1059, 1981.

[Murty] M. Ram Murty. Prime numbers and irreducible polynomials. *The American Mathematical Monthly*, 109(5):452–458, 2002. [JSTOR]

[Polya] G. Polya. *Induction and Analogy in Mathematics*. Princeton University Press, New Jersey, 1954. Volume 1 of Mathematics and Plausible Reasoning.

[PolyaSzego] G. Pólya and G. Szegö. *Problems and Theorems in Analysis*. Springer–Verlag, Berlin, 1972.

## Leave a Reply