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$.

Robert Z
  • 145,942
mpnm
  • 1,097

5 Answers5

1

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$.

J.G.
  • 115,835
  • 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. –  Sep 01 '19 at 17:30
  • 1
    @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 01 '19 at 17:33
1

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.$$

Jyrki Lahtonen
  • 133,153
Luca Goldoni Ph.D.
  • 2,969
  • For heaven's sake keep the punctuation inside the double dollars. Otherwise the next line will begin with a punctuation character :-) – Jyrki Lahtonen Sep 04 '19 at 13:18
0

$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.

Arthur
  • 199,419
0

$$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$

AgentS
  • 12,195
0

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).$$

Michael Rozenberg
  • 194,933