Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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?
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}
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$.
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$.
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)$
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
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 $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$.
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$.
