# What is the method to factor $x^3 + 1$?

In the solution to a problem, it's stated that

We see that $$x^3+1=(x+1)(x^2-x+1)$$.

Why is this, and what method can I use for similar problems with different coefficients?

The full problem is

Find the remainder when $$x^{81}+x^{48}+2x^{27}+x^6+3$$ is divided by $$x^3+1$$.

• Try to use long division. – Hussain-Alqatari Sep 1 '19 at 13:45
• By inspection, I think the answer is 2. – Andrew Chin Sep 1 '19 at 13:45
• Cf. answers to this question – J. W. Tanner Sep 1 '19 at 13:49
• Read your identity from right to left. And ask yourself why it is true. And your answer will be to multiply the two factors and finding out that the result is $x^3+1$. – Bernard Massé Sep 1 '19 at 19:16

For the full problem: let be $$y=x^3.$$ Your problem is equivalent to find the remainder of $$P(y) = y^{27} + y^{16} + 2y^9 + y^2 + 3$$ when it is divided by $$y+1.$$ By Remainder's Theorem, that remainder is given by $$P(-1)=2.$$

• For heaven's sake keep the punctuation inside the double dollars. Otherwise the next line will begin with a punctuation character :-) – Jyrki Lahtonen Sep 4 '19 at 13:18

For the full problem, working modulo $$x^3+1$$ we have $$x^3=-1\implies x^{3n}=(-1)^n\implies x^{81}+x^{48}+2x^{27}+x^6+3=-1+1-2+1+3=2.$$

So no such factorisation is needed. But when it is needed, here's how to do it. By the factor theorem, the fact that $$(-1)^3+1=0$$ implies $$x-(-1)=x+1$$ is a factor. So try $$x^3+1=(x+1)(ax^2+bx+c)$$. We know $$a=1$$ from the $$x^3$$ coefficient and $$c=1$$ from the constant term, and the $$x^2$$ coefficient tells us $$0=a+b\implies b=-1$$.

• Is "modulo $x^3+1$" something that I would understand better if I read up on polynomial rings? I am simultaneously understanding and having my mind blown reading through your equation. – Matthew Daly Sep 1 '19 at 17:30
• @MatthewDaly That subject would help, but for now it's sufficient to note that if $x^{3k}=(-1)^k(\operatorname{mod}x^3+1)$, as is certainly true if $k=0$, $x^{3(k+1)}=(x^3+1)x^{3k}-x^{3k}=(-1)^{k+1}(\operatorname{mod}x^3+1)$, completing a proof by induction. Or even simpler, since you want to find the remainder when dividing a polynomial function of $u:=x^3$ by $u+1$, you can just use the usual remainder theorem for division by linear factors to get a constant remainder. – J.G. Sep 1 '19 at 17:33

$$x^3+1=(x+1)(x^2-x+1)$$ is something one just knows, similar to how one knows that $$x^2+2x+1=(x+1)^2$$, or $$x^2-1=(x+1)(x-1)$$

If you don't already know it, note that $$(-1)^3+1=0$$, which implies that $$x-(-1)$$ is a factor of $$x^3+1$$. Finding the second factor can be done through long division.

$$x^3+1=(x+1)(x^2-x+1)$$ can be seen from our good friend geometric series: $$\dfrac{r^n-1}{r-1} = 1+r+r^2+\cdots+r^{n-1}$$

Plug $$r=-x$$ and $$n=3$$

Since $$(-1)^3+1=0,$$ we know that $$x^3+1$$ is divisible by $$x+1$$, which gives the following way: $$x^3+1=x^3+x^2-x^2-x+x+1=x^2(x+1)-x(x+1)+x+1=(x+1)(x^2-x+1).$$