How to find the remainder of dividing polynomial $x^{2016}-x^{2015}-1$ with $x^2+1$ 
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$.
 A: 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$.
A: 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)$$
A: $\!\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!
A: 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.
