Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "Eisenstein's criterion"

(Created page with "Let <math>a_0, a_1, ... ,a_n</math> be integers. Then, '''Eisenstein's Criterion''' states that the polynomial <math>a_nx^n+a_{n-1}x^{n-1}+ ... + a_1x+a_0</math> cannot be facto...")
 
(Proof and Extended Eisentein's Criterion)
 
Line 7: Line 7:
  
 
<math> 3) a_0</math> is not divisible by <math>p^2</math>
 
<math> 3) a_0</math> is not divisible by <math>p^2</math>
 +
 +
==Proof==
 +
Assume <math>f(x)=a_nx^n+a_{n-1}x^{n-1}+\cdots+ a_1x+a_0</math> and <math>f(x)=g(x)h(x)</math> for non-constant polynomials <math>g(x)=g_rx^r+g_{r-1}x^{r-1}+\cdots+ g_1x+g_0</math> and <math>h=h_sx^s+h_{s-1}x^{s-1}+\cdots+ h_1x+h_0</math>. Since <math>a_0</math> has only one factor of <math>p</math>, we know that <math>p|g_0</math> or <math>p|h_0</math>. WLOG, assume <math>p|g_0</math>. Then, we know that <math>a_1 \equiv g_0h_1+g_1h_0 \equiv g_1h_0 \equiv 0 \pmod{p}</math>. This means <math>p|g_1</math>. Similarily, we see, since <math>r<n</math>, <math>p|g_i</math> for all <math>0\leq i \leq r</math>. This means that <math>p|g(x)</math>, so <math>p|f(x)</math>. However, we know that <math>p\nmid a_n</math>, a contradiction. Therefore, <math>f(x)</math> is irreducible.
 +
 +
==Extended Eisenstein's Criterion==
 +
Let <math>a_0, a_1, ... ,a_n</math> be integers. Then, '''Eisenstein's Criterion''' states that the polynomial
 +
<math>a_nx^n+a_{n-1}x^{n-1}+ ... + a_1x+a_0</math> has an irreducible factor of degree more than <math>k</math> if:
 +
 +
<math> 1) p</math> is a prime which divides each of <math>a_0,a_1,a_2,...,a_{k} </math>
 +
 +
<math> 2) a_{k+1}</math> is not divisible by <math> p</math>
 +
 +
<math> 3) a_0</math> is not divisible by <math>p^2</math>
 +
 +
===Proof===
 +
Let <math>f(x)=g(x)h(x)</math>, where <math>g(x)=g_rx^r+g_{r-1}x^{r-1}+\cdots+ g_1x+g_0</math> and <math>h=h_sx^s+h_{s-1}x^{s-1}+\cdots+ h_1x+h_0</math>. Since <math>a_0</math> has only one factor of <math>p</math>, we know that <math>p|g_0</math> or <math>p|h_0</math>. WLOG, assume <math>p|g_0</math>. Then, we know that <math>a_1 \equiv g_0h_1+g_1h_0 \equiv g_1h_0 \equiv 0 \pmod{p}</math>. This means <math>p|g_1</math>. Similarily, we see, if <math>r\leq k</math>, <math>p|g_i</math> for all <math>0\leq i \leq r</math>. This means that <math>p|g(x)</math>, so <math>p|f(x)</math>. However, we know that <math>p\nmid a_{k+1}</math>, a contradiction. Therefore, <math>r\geq k+1</math>.
 +
 +
  
 
{{stub}}
 
{{stub}}

Latest revision as of 13:47, 14 August 2018

Let $a_0, a_1, ... ,a_n$ be integers. Then, Eisenstein's Criterion states that the polynomial $a_nx^n+a_{n-1}x^{n-1}+ ... + a_1x+a_0$ cannot be factored into the product of two non-constant polynomials if:

$1) p$ is a prime which divides each of $a_0,a_1,a_2,...,a_{n-1}$

$2) a_n$ is not divisible by $p$

$3) a_0$ is not divisible by $p^2$

Proof

Assume $f(x)=a_nx^n+a_{n-1}x^{n-1}+\cdots+ a_1x+a_0$ and $f(x)=g(x)h(x)$ for non-constant polynomials $g(x)=g_rx^r+g_{r-1}x^{r-1}+\cdots+ g_1x+g_0$ and $h=h_sx^s+h_{s-1}x^{s-1}+\cdots+ h_1x+h_0$. Since $a_0$ has only one factor of $p$, we know that $p|g_0$ or $p|h_0$. WLOG, assume $p|g_0$. Then, we know that $a_1 \equiv g_0h_1+g_1h_0 \equiv g_1h_0 \equiv 0 \pmod{p}$. This means $p|g_1$. Similarily, we see, since $r<n$, $p|g_i$ for all $0\leq i \leq r$. This means that $p|g(x)$, so $p|f(x)$. However, we know that $p\nmid a_n$, a contradiction. Therefore, $f(x)$ is irreducible.

Extended Eisenstein's Criterion

Let $a_0, a_1, ... ,a_n$ be integers. Then, Eisenstein's Criterion states that the polynomial $a_nx^n+a_{n-1}x^{n-1}+ ... + a_1x+a_0$ has an irreducible factor of degree more than $k$ if:

$1) p$ is a prime which divides each of $a_0,a_1,a_2,...,a_{k}$

$2) a_{k+1}$ is not divisible by $p$

$3) a_0$ is not divisible by $p^2$

Proof

Let $f(x)=g(x)h(x)$, where $g(x)=g_rx^r+g_{r-1}x^{r-1}+\cdots+ g_1x+g_0$ and $h=h_sx^s+h_{s-1}x^{s-1}+\cdots+ h_1x+h_0$. Since $a_0$ has only one factor of $p$, we know that $p|g_0$ or $p|h_0$. WLOG, assume $p|g_0$. Then, we know that $a_1 \equiv g_0h_1+g_1h_0 \equiv g_1h_0 \equiv 0 \pmod{p}$. This means $p|g_1$. Similarily, we see, if $r\leq k$, $p|g_i$ for all $0\leq i \leq r$. This means that $p|g(x)$, so $p|f(x)$. However, we know that $p\nmid a_{k+1}$, a contradiction. Therefore, $r\geq k+1$.


This article is a stub. Help us out by expanding it.

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Eisenstein%27s_criterion&oldid=97227"