# The Lumber Room

"Consign them to dust and damp by way of preserving them"

## Testing irreducibility using prime numbers

Here’s a simple and nice test for irreducibility in ${\mathbb{Z}[x]}$ 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 1 Given a polynomial ${f(x) = a_nx^n + a_{n-1}x^{n-1} + \dots + a_o}$ with integer coefficients, let ${G = \max_{i}|\frac{a_i}{a_n}|}$. If there exists an integer ${m \ge G+2}$ such that ${f(m)}$ is prime, then ${f}$ is irreducible.

For example, with the polynomial $x^2 + 3x + 1$, we have $G = 3$, and $f(5)=f(G+2)=41$ 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.)

Written by S

Sat, 2009-09-05 at 22:01:44

Posted in mathematics