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

Read the rest of this entry »

Written by S

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

Posted in mathematics

Tagged with algebra, irreducibility, irreducible polynomials, polynomials, primes
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 9, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9191060662269592, "perplexity_flag": "middle"}