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 "2007 iTest Problems/Problem TB2"

(This problem was fun.)
 
(→‎Solution)
Line 33: Line 33:
  
 
For any of the factors of degree more than 1 to be factorable in the integers, they must have rational roots, since their degrees are less than 4. None of them have rational roots. Hence <math>p(x)</math> is completely factored.
 
For any of the factors of degree more than 1 to be factorable in the integers, they must have rational roots, since their degrees are less than 4. None of them have rational roots. Hence <math>p(x)</math> is completely factored.
 +
 +
===Alternate Solution===
 +
We write <cmath>p(x)=x^8+x^5+x^4+x^3+x+1=</cmath> <cmath>x^5(x^3+1)+x^3(x+1)+(x+1)=</cmath> <cmath>(x+1)(x^5(x^2-x+1) + (x^3+1))=</cmath> <cmath>(x+1)(x^5(x^2-x+1)+(x+1)(x^2-x+1))=</cmath> <cmath>(x+1)(x^2-x+1)(x^5+x+1)=</cmath> <cmath>(x+1)(x^2-x+1)(x^2+x+1)(x^3-x^2+1)</cmath>
 +
 +
The factorization of <math>x^5+x+1</math> is trivial once we look at the exponents modulo <math>3</math>; since any root <math>\omega</math> of <math>x^2+x+1</math> satisfies <math>\omega^3=1</math>, it follows that <math>x^2+x+1 | x^5+x+1</math> and the cubic factor comes as a result of polynomial division.
 +
 +
To prove that this is a complete factorization, it suffices to note that the factors of degree greater than <math>1</math> have no rational roots (follows from the rational root theorem and some small cases).
  
 
==See also==
 
==See also==
  
 
[[Category:Intermediate Algebra Problems]]
 
[[Category:Intermediate Algebra Problems]]

Revision as of 16:28, 13 June 2013

Problem

Factor completely over integer coefficients the polynomial $p(x)=x^8+x^5+x^4+x^3+x+1$. Demonstrate that your factorization is complete.

Solution

Note that $p(x)=(x^5+x+1)+(x^8+x^4+x^3)$. If $x\neq 1$ and $x^3=1$, then $x^5+x+1=x^2+x+1=0$ and $x^8+x^4+x^3=x^2+x+1=0$. Therefore if $x\neq 1$ and $x^3=1$, then $p(x)=0$. Hence $x^2+x+1|p(x)$. Dividing through gives us

$p(x)=(x^2+x+1)(x^6-x^5+2x^3-x^2+1)$

Using the Rational Root Theorem on the second polynomial gives us that $\pm 1$ are possible roots. Only $-1$ is a possible root. Dividing through gives us

$p(x)=(x+1)(x^2+x+1)(x^5-2x^4+2x^3-x+1)$

Note that $x^5-2x^4+2x^3-x+1$ can be factored into the product of a cubic and a quadratic. Let the product be

$x^5-2x^4+2x^3-x+1=(x^2+ax+b)(x^3+cx^2+dx+e)$

We would want the coefficients to be integers, hence we shall only look for integer solutions. The following equations must then be satisfied:

  • $be=1$
  • $ae+bd=-1$
  • $c+ad+e=0$
  • $b+ac+d=2$
  • $a+c=-2$

Since $b$ and $e$ are integers, $(b,e)$ is either $(1,1)$ or $(-1,-1)$. Testing the first one gives

  • $a+d=-1$
  • $c+ad=-1$
  • $ac+d=1$
  • $a+c=-2$

We must have that $(a+c)-(a+d)=c-d=-2--1=-1$ $(ac+d)-(c+ad)=a(c-d)-(c-d)=(a-1)(c-d)=1--1=2$. Therefore $a-1=-2$, or $a=-1$. Solving for $c$ and $d$ gives $(a,b,c,d,e)=(-1,1,-1,0,1)$. We don't need to test the other one.

Hence we have

$p(x)=(x+1)(x^2+x+1)(x^2-x+1)(x^3-x^2+1)$

For any of the factors of degree more than 1 to be factorable in the integers, they must have rational roots, since their degrees are less than 4. None of them have rational roots. Hence $p(x)$ is completely factored.

Alternate Solution

We write \[p(x)=x^8+x^5+x^4+x^3+x+1=\] \[x^5(x^3+1)+x^3(x+1)+(x+1)=\] \[(x+1)(x^5(x^2-x+1) + (x^3+1))=\] \[(x+1)(x^5(x^2-x+1)+(x+1)(x^2-x+1))=\] \[(x+1)(x^2-x+1)(x^5+x+1)=\] \[(x+1)(x^2-x+1)(x^2+x+1)(x^3-x^2+1)\]

The factorization of $x^5+x+1$ is trivial once we look at the exponents modulo $3$; since any root $\omega$ of $x^2+x+1$ satisfies $\omega^3=1$, it follows that $x^2+x+1 | x^5+x+1$ and the cubic factor comes as a result of polynomial division.

To prove that this is a complete factorization, it suffices to note that the factors of degree greater than $1$ have no rational roots (follows from the rational root theorem and some small cases).

See also

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2007_iTest_Problems/Problem_TB2&oldid=53003"