How to find the remainder of dividing polynomial $x^{2016}-x^{2015}-1$ with $x^2+1$

Question

What is the remainder of dividing polynomial $$P(x)=x^{2016}-x^{2015}-1$$ with $x^2+1$?

So what I thought of doing is just dividing them the "school" way:

$(x^{2016}-x^{2015}-1)\div(x^2+1)=x^{2014}-x^{2013}-x^{2012}+x^{2011}\cdots$

But the problem is that this way it just goes on and on, and I can see that it should end up with $x$ as a remainder, but what's the way I can prove that, without knowing that it ends up in $x$?

The other way I thought of solving this is by maybe presenting that:

$P(x)\div(x^2+1)=Q(x)+y$,

so for $P(i)$

$i^{2016}-i^{2015}-1=y$,

where $i^2=-1$, and this way I get

$y=-i$

but that seems incorrect, since I can see that the regular division would end up to $x$.

Answer 1

Your approach works except that it is not fully general: because $x^2+1$ is quadratic, the quotient-remainder form should be $$ P(x) = Q(x)(x^2+1) + ax+b $$ for some unknown $a$ and $b$.

Now we can set $P(i) = Q(i)(0) + ai + b$, getting one equation for $a$ and $b$. We can also set $P(-i) = Q(i)(0) + a(-i) + b$, getting another equation, because $x^2+1$ is $0$ when $x=i$ or when $x=-i$.

Solving for $a$ and $b$, you should get $a=1$ and $b=0$.

Answer 2

Okay so I got where I messed up.

for $P(i)$

$i^{2016}-i^{2015}-1=y\\1-(-i)-1=y\\y=i$

And since I did it for $P(i)$, it should be

$y=x$,

which means that the remainder of dividing those polynomials is $x$, which seems correct.

Correct me on this if I'm wrong somewhere.

Answer 3

The remainder of $P(x)$ with $Q(x)$ stays invariant if we add or subtract a multiple (which can be a polynomial) of $Q(x)$ from $P(x)$. So, we can evaluate the remainder in the analogous way as we would do in case if ordinary numbers using modular arithmetic.

We thus need to do the computations modulo $Q(x) = x^2 + 1$. Since:

$$x^2 = -1 \bmod Q(x)$$

we have:

$$x^{2016} = 1 \bmod Q(x)$$

$$x^{2015} = x^3 \bmod Q(x) = -x \bmod Q(x)$$

Therefore:

$$x^{2016} - x^{2015} - 1 = x \bmod Q(x)$$

Answer 4

$\!\bmod\, x^{\large 2}\!+\!1\!:\,\ x^{\large 2}\equiv -1\,\Rightarrow\, \color{#0a0}{x^{\large 3}\equiv -x}\,\Rightarrow\,\color{#c00}{x^{\large 4}\equiv 1}\,\Rightarrow\, x^{\large\color{#c00}4q+r} = (\color{#c00}{x^{\large 4}})^{\large q} x^{\large r} \equiv\, x^{\large r}$

$\begin{align}{\rm Therefore}\ \ \ \qquad x^{\large\color{#c00} 4n}\! - x^{\large \color{#c00}4k\color{#0a0}{+3}} &-\, 1\\ \equiv\quad\ 1\ \ \,-\,\ \ \color{#0a0}{\large x^3} &-\, 1\, \equiv\, \color{#0a0}x\ \end{align}$

Remark $ $ Above $x$ like $i$ is a square root of $-1$. If you know a little ring theory you know how to say this much more precisely $\,\Bbb Z[x]/(x^2+1)\cong \Bbb Z[i],\,$ so replacing $x$ by $i$ above gives an isomorphic calculation in the Gaussian integers. So we can use numbers to deduce results about polynomials!