The Lumber Room

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

Posts Tagged ‘primes

Testing irreducibility using prime numbers

leave a comment »

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.)

Read the rest of this entry »

Written by S

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