https://artofproblemsolving.com/wiki/api.php?action=feedcontributions&user=Naysh&feedformat=atom AoPS Wiki - User contributions [en] 2021-10-22T18:24:45Z User contributions MediaWiki 1.31.1 https://artofproblemsolving.com/wiki/index.php?title=2007_iTest_Problems/Problem_TB2&diff=53003 2007 iTest Problems/Problem TB2 2013-06-13T21:28:07Z <p>Naysh: /* Solution */</p> <hr /> <div>== Problem ==<br /> Factor completely over integer coefficients the polynomial &lt;math&gt;p(x)=x^8+x^5+x^4+x^3+x+1&lt;/math&gt;. Demonstrate that your factorization is complete.<br /> <br /> == Solution ==<br /> Note that &lt;math&gt;p(x)=(x^5+x+1)+(x^8+x^4+x^3)&lt;/math&gt;. If &lt;math&gt;x\neq 1&lt;/math&gt; and &lt;math&gt;x^3=1&lt;/math&gt;, then &lt;math&gt;x^5+x+1=x^2+x+1=0&lt;/math&gt; and &lt;math&gt;x^8+x^4+x^3=x^2+x+1=0&lt;/math&gt;. Therefore if &lt;math&gt;x\neq 1&lt;/math&gt; and &lt;math&gt;x^3=1&lt;/math&gt;, then &lt;math&gt;p(x)=0&lt;/math&gt;. Hence &lt;math&gt;x^2+x+1|p(x)&lt;/math&gt;. Dividing through gives us<br /> <br /> &lt;center&gt;&lt;math&gt;p(x)=(x^2+x+1)(x^6-x^5+2x^3-x^2+1)&lt;/math&gt;&lt;/center&gt;<br /> <br /> Using the [[Rational Root Theorem]] on the second polynomial gives us that &lt;math&gt;\pm 1&lt;/math&gt; are possible roots. Only &lt;math&gt;-1&lt;/math&gt; is a possible root. Dividing through gives us<br /> <br /> &lt;center&gt;&lt;math&gt;p(x)=(x+1)(x^2+x+1)(x^5-2x^4+2x^3-x+1)&lt;/math&gt;&lt;/center&gt;<br /> <br /> Note that &lt;math&gt;x^5-2x^4+2x^3-x+1&lt;/math&gt; can be factored into the product of a cubic and a quadratic. Let the product be<br /> <br /> &lt;center&gt;&lt;math&gt;x^5-2x^4+2x^3-x+1=(x^2+ax+b)(x^3+cx^2+dx+e)&lt;/math&gt;&lt;/center&gt;<br /> <br /> We would want the coefficients to be integers, hence we shall only look for integer solutions. The following equations must then be satisfied:<br /> * &lt;math&gt;be=1&lt;/math&gt;<br /> * &lt;math&gt;ae+bd=-1&lt;/math&gt;<br /> * &lt;math&gt;c+ad+e=0&lt;/math&gt;<br /> * &lt;math&gt;b+ac+d=2&lt;/math&gt;<br /> * &lt;math&gt;a+c=-2&lt;/math&gt;<br /> Since &lt;math&gt;b&lt;/math&gt; and &lt;math&gt;e&lt;/math&gt; are integers, &lt;math&gt;(b,e)&lt;/math&gt; is either &lt;math&gt;(1,1)&lt;/math&gt; or &lt;math&gt;(-1,-1)&lt;/math&gt;. Testing the first one gives<br /> * &lt;math&gt;a+d=-1&lt;/math&gt;<br /> * &lt;math&gt;c+ad=-1&lt;/math&gt;<br /> * &lt;math&gt;ac+d=1&lt;/math&gt;<br /> * &lt;math&gt;a+c=-2&lt;/math&gt;<br /> We must have that &lt;math&gt;(a+c)-(a+d)=c-d=-2--1=-1&lt;/math&gt; &lt;math&gt;(ac+d)-(c+ad)=a(c-d)-(c-d)=(a-1)(c-d)=1--1=2&lt;/math&gt;. Therefore &lt;math&gt;a-1=-2&lt;/math&gt;, or &lt;math&gt;a=-1&lt;/math&gt;. Solving for &lt;math&gt;c&lt;/math&gt; and &lt;math&gt;d&lt;/math&gt; gives &lt;math&gt;(a,b,c,d,e)=(-1,1,-1,0,1)&lt;/math&gt;. We don't need to test the other one.<br /> <br /> Hence we have<br /> <br /> &lt;center&gt;&lt;math&gt;p(x)=(x+1)(x^2+x+1)(x^2-x+1)(x^3-x^2+1)&lt;/math&gt;&lt;/center&gt;<br /> <br /> 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 &lt;math&gt;p(x)&lt;/math&gt; is completely factored.<br /> <br /> ===Alternate Solution===<br /> We write &lt;cmath&gt;p(x)=x^8+x^5+x^4+x^3+x+1=&lt;/cmath&gt; &lt;cmath&gt;x^5(x^3+1)+x^3(x+1)+(x+1)=&lt;/cmath&gt; &lt;cmath&gt;(x+1)(x^5(x^2-x+1) + (x^3+1))=&lt;/cmath&gt; &lt;cmath&gt;(x+1)(x^5(x^2-x+1)+(x+1)(x^2-x+1))=&lt;/cmath&gt; &lt;cmath&gt;(x+1)(x^2-x+1)(x^5+x+1)=&lt;/cmath&gt; &lt;cmath&gt;(x+1)(x^2-x+1)(x^2+x+1)(x^3-x^2+1)&lt;/cmath&gt; <br /> <br /> The factorization of &lt;math&gt;x^5+x+1&lt;/math&gt; is trivial once we look at the exponents modulo &lt;math&gt;3&lt;/math&gt;; since any root &lt;math&gt;\omega&lt;/math&gt; of &lt;math&gt;x^2+x+1&lt;/math&gt; satisfies &lt;math&gt;\omega^3=1&lt;/math&gt;, it follows that &lt;math&gt;x^2+x+1 | x^5+x+1&lt;/math&gt; and the cubic factor comes as a result of polynomial division.<br /> <br /> To prove that this is a complete factorization, it suffices to note that the factors of degree greater than &lt;math&gt;1&lt;/math&gt; have no rational roots (follows from the rational root theorem and some small cases).<br /> <br /> ==See also==<br /> <br /> [[Category:Intermediate Algebra Problems]]</div> Naysh