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

• Here's a broad hint: you know that $x^2\equiv -1\pmod {x^2+1}$; this means that $x^4\equiv 1\pmod{x^2+1}$. Can you continue from there? – Steven Stadnicki Oct 12 '18 at 17:30
• Aleksa, I think you mean to correct the typo to read $P(x)=Q(x)(x^2+1)+y$. If you leave it as it currently is, you should correct it to $P(x)/(x^2+1)=Q(x)+\frac{y}{x^2+1}$. (Please note that this formulation is still invalid, but it is more in line with your approach.) – Clayton Oct 12 '18 at 17:42
• @Clayton I'll leave it as it is, since it's a mistake I made in the first place. Anyone reading the whole post with answers will see that it's incorrect. – Aleksa Oct 12 '18 at 17:48

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

• We don't need to solve any equations since $\,P(i) = ai+b\,$ implies the remainder $= ax+b,\,$ see my answer. – Bill Dubuque Oct 12 '18 at 18:46
• @BillDubuque This is true in the special case of division by $x^2+1$ when the coefficients of $P$ are real; in this case, if $P(i) = ai+b$, we know that $P(-i) = P(\overline{i}) = \overline{P(i)} = a(-i)+b$, so in general the remainder is $ax+b$. But in some more general case, we would need to solve the equations. – Misha Lavrov Oct 12 '18 at 18:58
• The idea works much more generally, e.g. using roots of an irreducible polynomial. This will be clear when one studies ring theory. – Bill Dubuque Oct 12 '18 at 19:04
• @BillDubuque I am familiar with the ring theory, thank you. This means that I know when the idea applies and when it does not. However, the asker of the question may not know when the idea applies and when it does not, so you do not need to condescend to me just because I have tried to give an answer that does not require ring theory. – Misha Lavrov Oct 12 '18 at 20:03
• Generally my answers and comments are targeted as widely as possible, i.e. not at you but anyone who may be reading (hence I wrote "when one studies", not "when you study"). Also, keep in mind that it is usually not easy to infer the knowledge level of an answerer from a single answer. – Bill Dubuque Oct 12 '18 at 20:17

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

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.

• I don't think this idea works since you end up with $P(i)/0=0+y$. You're using that $x^2+1=0$ on the right-hand side but not on the left-hand side (which causes a division by $0$). – Clayton Oct 12 '18 at 17:27
• It could be that $y=x$, or that $y=i$ no matter what $x$ is, or that $y=2x-i$. There is no way to know without a second equation. – Misha Lavrov Oct 12 '18 at 17:34
• @Clayton Yes but in this case I just say that $x^{2016}-x^{2015}-1=Q(x)(x^2+1)+y$, there is no division in this case. – Aleksa Oct 12 '18 at 17:34
• @Aleksa: If you write the formula correctly, I agree. But if you look at your original post, you have $P(x)/(x^2+1)=Q(x)(x^2+1)+y$. See Misha's correction for an approach similar to this – Clayton Oct 12 '18 at 17:35
• @Clayton Perhaps then you should say "you made a typo" not "your math is all wrong". – Misha Lavrov Oct 12 '18 at 17:36

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

• I am always surprised how few people seem to get this way of looking at things. – Mark Bennet Oct 12 '18 at 19:11