8
$\begingroup$

Factorise $$x^5+x+1$$

I'm being taught that one method to factorise this expression which is $=x^5+x^4+x^3-x^4-x^3-x^2+x^2+x+1$

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

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

My question:

Is there another method to factorise this as this solution it seems impossible to invent it?

Improve this question
$\endgroup$
  • $\begingroup$ In general, factorization of polynomials is, as you say, "impossible to invent" by hand. There are algorithms, though, which can solve the problem. $\endgroup$ – Dietrich Burde May 23 '17 at 15:04
  • $\begingroup$ Any high school student can solve this problem when he guesses one of the factors and then calculates the other factor by division. But that is not really a useful method to factor a polynomial. But it is similar to the method most of the answers uses. $\endgroup$ – miracle173 May 23 '17 at 16:03
  • $\begingroup$ $$ 5 \equiv 2 \pmod 3 $$ $\endgroup$ – Will Jagy May 23 '17 at 16:06
  • $\begingroup$ I just don't know how to accept only one answer when all the answers are simply amazing and awesome. $\endgroup$ – Mathxx May 23 '17 at 22:25
  • $\begingroup$ @Mathxx, See math.stackexchange.com/questions/1584594/… $\endgroup$ – lab bhattacharjee May 24 '17 at 5:36
11
$\begingroup$

With algebraic identities, this is actually rather natural:

Remember if we had all powers of $x$ down to $x^0=1$, we could easily factor: $$x^5+x^4+x^3+x^2+x+1=\frac{x^6-1}{x-1}=\frac{(x^3-1)(x^3+1)}{x-1}=(x^2+x+1)(x^3+1),$$ so we can write: \begin{align}x^5+x+1&=(x^2+x+1)(x^3+1)-(x^4+x^3+x^2)\\ &=(x^2+x+1)(x^3+1)-x^2(x^2+x+1)\\ &=(x^2+x+1)(x^3+1-x^2). \end{align}

Improve this answer
$\endgroup$
  • $\begingroup$ (x3+1−x2) = ((x - 1)x^2 + 1) $\endgroup$ – MCCCS May 23 '17 at 15:04
  • 1
    $\begingroup$ That's true, but it's not a factorisation. What do you mean? $\endgroup$ – Bernard May 23 '17 at 15:06
  • $\begingroup$ Never mind, it's useless. $\endgroup$ – MCCCS May 23 '17 at 15:07
  • $\begingroup$ What does "this is rather natural" mean in this context? $\endgroup$ – miracle173 May 23 '17 at 15:42
  • $\begingroup$ I simply meant any high school student which is trained to tackle formulae using various identities can factor this polynomial. $\endgroup$ – Bernard May 23 '17 at 15:45
11
$\begingroup$

If you suspect there exists a factorization over $\mathbb{Q}[x]$ into polynomials of degree 2 and 3, but you just don't know their coefficients, one way is to write it down as

$x^5 + x + 1 = (x^2 + ax + b)(x^3 + cx^2 + dx + e)$ where the coefficients are integers (by Gauss' lemma). And then expand and solve the system.

Then $a + c = 0, b + ac + d = 0, bc + ad + e = 0, ae + bd = 1, be = 1$. So we get $c = -a$ and $b = e = 1$ or $b = e = -1$.

In the first case we reduce to $1 - a^2 + d = 0, -a + ad + 1 = 0, a + d = 1$ which gives $d = 1 - a, 1 - a^2 + 1 - a = 0, 1 - a^2 = 0$ so $a = 1, b = 1, c = -1, d = 0, e = 1$.

Substituting gives us $x^5 + x + 1 = (x^2 + x + 1)(x^3 - x^2 + 1)$

If the factorization was not over $\mathbb{Q}[x]$ then things would get more complicated because I could not assume $b = e = +/- 1$.

Improve this answer
$\endgroup$
  • $\begingroup$ If you suspect there exists a factorization over Q[x] than it is easy to show that polynomial cannot be split into a polynomail of degree 4 and a linears factor, so it must be the product of thwo polynomails of degree 2 and 3 $\endgroup$ – miracle173 May 23 '17 at 15:46
8
$\begingroup$

Alternatively note that $$\begin{align}x^5 + x + 1 &= x^5 - x^2 + x^2 + x + 1\\ & =x^2(x^3-1) + \color{red}{x^2+x+1} \\ & = x^2(x-1)\color{red}{(x^2+x+1)} + \color{red}{x^2+x+1} \\& =\color{blue}{(x^3-x^2+1)}\color{red}{(x^2+x+1)} \end{align}$$

where we used the well known identity $x^3 - 1 = (x-1)(x^2+x+1)$ in the third equality.

Meta: whilst the first step may seem arbitrary and magical, it is natural to want to insert a term like $x^2$ or $x^3$ into the equation in order to get some traction with factorising $x^5 + x^k$.

Improve this answer
$\endgroup$
6
$\begingroup$

Note that if $z^3=1, z\neq 1$ so that $z^3-1=(z-1)(z^2+z+1)=0$ then $z^5+z+1=z^2+z+1=0$. A key to this observation is just seeing whether an appropriate root of unity may be a root.

This tells you that $x^2+x+1$ is a factor of $x^5+x+1$, and the question then is how you do the division. The factorisation method you have been shown is equivalent to doing the polynomial long division.

Another method, not suggested by others, is to use the fact that you know $x^2+x+1$ is a factor and multiply through by $x-1$ so that this factor becomes $x^3-1$.

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

Improve this answer
$\endgroup$
  • $\begingroup$ I think this is no better than the solution the user already showed us. One has to guess the right things $\endgroup$ – miracle173 May 23 '17 at 16:32
  • $\begingroup$ @miracle173 But the user suggested the solution could not be discovered easily. The art of problem solving is in part learning the kind of things you might try when faced with something unfamiliar. $\endgroup$ – Mark Bennet May 23 '17 at 19:22
3
$\begingroup$

standard trick from contests: $5 \equiv 2 \pmod 3.$ Therefore, if $\omega^3 = 1$ but $\omega \neq 1,$ we get $$ \omega^5 = \omega^2 $$ $$ \omega^5 + \omega + 1 = \omega^2 + \omega + 1 = 0 $$ Which means, various ways of saying this, $x^5 + x + 1$ must be divisible by $$ (x - \omega)(x - \omega^2) = x^2 + x + 1. $$ This is what we call a "minimal polynomial" for $\omega$

The same idea would work for $$ x^{509} + x^{73} + 1 $$ although the other factor would be worse

SEE

Prove that $n^5+n^4+1$ is composite for $n>1.$

Prime factor of $A=14^7+14^2+1$

Improve this answer
$\endgroup$
  • $\begingroup$ I think this is no better than the solution the user already showed us. One has to guess the right things $\endgroup$ – miracle173 May 23 '17 at 16:32
  • $\begingroup$ @miracle173 it's a matter of where the questions arise. This is a contest or contest preparation question, there is a trick; this comes up over and over again on this site, from kids who are trying to get better at contests. You might ask the OP where he got the question and what is the setting responsible for "I'm being taught..." Put another way, someone skilled at searching could find hundreds of questions on MSE where one factor is $x^2 + x + 1$ $\endgroup$ – Will Jagy May 23 '17 at 16:42
3
$\begingroup$

So far the answers just (cleverly) elaborate on high school tricks and techniques. Therefore, I think it can be interesting to see, instead, how standard modern algorithms work in this special case. I will implement a small version of the Berlekamp-Zassenhaus algorithm. I will try to factor $F(x)=x^5+x+1$ over $\mathbb Z[x]$ as a product $f_1(x)f_2(x)$ of polynomials of degree 2 and 3; it will not be long (of course), nor difficult. I recall what is the plan:

  • Bound the coefficients of the factors $f_1,f_2$;
  • Factor $F(x)=g_1(x)g_2(x)$ over modulo $p$ for some prime $p$;
  • Lift (in essence, by Hensel's lemma) the factorization modulo higher $p^k$.

Bound the coefficients of $f_1(x)$: The leading coefficient of $F$ is $c=1$, the degree of $f_1$ is $\delta=2$, and the roots $\alpha$ of $F$ satisfy ${|\alpha|}^5\leq 1+|\alpha|$, so for sure, say, $|\alpha|<\rho=1.5$. Therefore the (absolute values of the) coefficients of $f_1(x)$ are all dominated by those of $(x+\rho)^2$. In particular they are all $<3$. This is called the binomial bound. The same estimate can be obtained with the Knuth-Cohen bound. See Abbott, John. "Bounds on Factors in Z [x]." Journal of Symbolic Computation 50 (2013): 532-563.

Find $g_i(x)\equiv f_i(x)$ modulo 2: Since $F(0)=1$ and $F(1)=3$ we have that $g_1(0)=g_1(1)=1\bmod 2$. Thus the only possibility is $g_1(x)=x^2+x+1$. By polynomial long division in $\mathbb F_2[x]$ we get $g_2(x)=\frac{F(x)}{g_1(x)}=x^3+x^2+1$. Well, if you are clever enough, and not a computer, you might finish the exercise here, by doing long division in $\mathbb Z[x]$.

Factor modulo 4 as $F=(g_1+2 h_1)(g_2 + 2 h_2)$: In other words, we need $g_1 h_2+g_2 h_1 = \frac {F(x)-g_1(x)g_2(x)}{2} = x^4+x^3+x^2 \bmod 2$. Of course the solution is $h_1=0$ and $h_2=x^2$.

Conclusion: We have $f_1(x)\equiv x^2+x+1\bmod 4$. Since the absolute value of the coefficients of $f_1(x)$ is at most $2$, we get $f_1(x)= x^2+x+1$. It works.

Supplement: actually I am deeply convinced that the most natural technique to factor $F(x)$ is the one provided by the OP (although all the other approaches, included the one I described above, are interesting). I'll try to justify this claim. Suppose you want to factor $7763073514021$ in prime numbers. The factor $7$ is easy to find (actually, this completes the factorization). Why? Because you decompose $7-7-63-0-7-35-14-0-21$ and you factor out termwise. "Piecewise" factorization is by far the most natural, and easy to spot, approach to factorization "by hand". Another example is $x^6-x^4-20x^3+14x^2+20 x -14$, where you may wish to take advantage of the pattern $(1,-1),(-20,20),(14,-14)$. Now, suppose you want to factor the number $636362236363$. It's very similar to the example before, only that you must be able to see the "negative": you are just subtracting a "14" from $636363636363$. Although the pattern of coefficients $[1,0,0,0,1,1]$ of $F(x)$ might be irregular at first glance, I find it very natural to see it as a $0-111-00$ subtracted from a $111-111$.

Improve this answer
$\endgroup$
  • $\begingroup$ Or else (but only for "how to factor", not "why does it factor"): coefficients of f_1 have norm at most 2; F is monic; F(0)=F(-1)=1. So f_1=x^2+x+1 or f_1=x^2-x-1. Now use F(-2)=-33. $\endgroup$ – Luca Ghidelli May 24 '17 at 1:09
1
$\begingroup$

Let $f (x)=x^5+x+1$

$$f'(x)=5x^4+1>0$$

$f $ is stricly increasing at $\mathbb R $, thus it has only one real root $\alpha \in (-1,0) $.

the factorisation will be of the form

$$(x-\alpha)(x^2+ax+b)(x^2+cx+d) $$

with $a^2-4b <0$ and $c^2-4d <0$.

Improve this answer
$\endgroup$
  • $\begingroup$ Why can't it be factored in $\mathbf R[X]$? The only irreducible polynomials in $\mathbf R[X]$ are linear polynomials and quadratic polynomials with a negative discriminant. $\endgroup$ – Bernard May 23 '17 at 14:56
  • $\begingroup$ Just because it has no linear factors does not mean that it does not have higher order factors (DAMHIKT). Also, he showed a factorization of it and the factorization is correct: just multiply it out. So, your answer is wrong: it can be factorized in $\mathbb R[X]$. $\endgroup$ – NickD May 23 '17 at 14:58
  • $\begingroup$ @Nick Yes you are right. i edited. $\endgroup$ – hamam_Abdallah May 23 '17 at 15:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.