# $x^{10}+x^{11}+\dots+x^{20}$ divided by $x^3+x$. Remainder?

Question:

If $$x^{10}+x^{11}+\dots+x^{20}$$ is divided by $$x^3+x$$, then what is the remainder?
Options: (A) $$x\qquad\quad$$ (B)$$-x\qquad\quad$$ (C)$$x^2\qquad\quad$$ (D)$$-x^2$$

In these types of questions generally I follow the following approach:

Since divisor is cubic so the remainder must be a constant/linear/quadratic expression.
$$\Rightarrow F(x)=(x^3+x)Q(x)+ax^2+bx+c$$
For $$x=0$$, we get $$c=0$$

But since $$x^3+x$$ has no other roots so I can't find $$a$$ and $$b$$. Please help.

Option (B)

• $x^3+x$ has three roots, even if two of them are complex.
– lulu
Jul 30 at 11:40
• Spoilers should not be in questions Jul 30 at 11:41
• @lulu the complex roots don't seem helpful to me here Jul 30 at 11:45
• Of course they are helpful. Just evaluate both sides at $x=\pm i$, just as you did with $x=0$.
– lulu
Jul 30 at 11:46
• You might notice that $x^{20}+x^{18} = (x^3+x)x^{17}$. Jul 30 at 11:50

Most useful for multiple choice is very quick elimination methods by considering special cases.

Put $$x = 2$$. The original expression is a geometric sum with number of terms, first term and common ratio being respectively $$11,2^{20},2$$ and it has the sum $$2^{10}(2^{11} - 1) = (1024)(2047)$$.

The divisor is $$2^3 + 2 = 10$$.

The original value modulo $$10$$ is $$(4)(7) = 28 \equiv 8 \equiv -2 \pmod{10}$$,so the only choice that fits is (B)$$-x$$.

By the way, using $$x=1$$ etc. doesn't help narrow down the possibilities sufficiently.

The above took me less than half a minute. It is a good technique for MCQ but (of course) not for open-ended questions.

• (+1) for the creative solution (although it relies on that one of the options is correct) Jul 30 at 12:20
• Wow! Great! Thank you for taking into account the very purpose of me adding "contest-math" tag. Sometimes solving just by procedure is indeed very time draining. Upvoted. Jul 30 at 12:37

What about this : We have for example $$x^{10}+x^{12}=x^{10}(x^2+1)\equiv 0\mod x(x^2+1)$$

This way we can also cancel $$11-13,14-16,15-17,18-20$$. It remains $$x^{19}$$ for which you can use $$x^6\equiv x^2$$ giving $$x^{18}\equiv x^6$$ hence $$x^{18}\equiv x^2$$ hence $$x^{19}\equiv x^3\equiv -x$$ $$\mod (x^3+x)$$

• Why $x^6≡x^2$? Jul 30 at 12:13
• We have $x^3\equiv -x\mod (x^3+x)$ . Now just square both sides Jul 30 at 12:14
• 1. Why spoilers should not be in question? Is it not good to tell others that I know the answer? 2. (I know this is rookie thing but) I'm not aware with "mod" properties so I see $x^3≡−x$ but how it works I need to know. Please enlighten me. Jul 30 at 12:23
• @InanimateBeing $p \equiv a \text{ mod } b$ means $(p-a)$ is divisible by $b$. Clearly, $x^3-(-x)$ is divisible by $x^3+x$. Jul 30 at 12:30
• It is correct to share everything you know about the problem (also the final answer, if you happen to know it) , just mention it and do not hide it with a spoiler. Jul 30 at 13:03

You want to divide by $$x^3+x = x(x^2+1)$$, hence by the Chinese remainder theorem it is enough to check the remainders $$\pmod{x}$$ (which is obviously zero) and $$\pmod{x^2+1}$$. This remainder is simply given by setting $$x^2\equiv -1$$, such that $$x^{10}+x^{11}+\ldots+x^{19}+x^{20} \equiv (-1-x+1+x)+(-1-x+1+x)+(-1-x+1+x)\color{red}{-x}$$ and option $$(B)$$ is apparent now.

• Oh! Such a straightforward and uncomplicated answer. Upvoted. It is such a solution when I say to myself, as said by Helen Keller: Those who do not see even by seeing. Thank you! Jul 30 at 14:39

\begin{align}p(x)&=x^{20}+x^{19}+\dots+x^{10}\\&=x^{17}(x^3+x)+x^{16}(x^3+x)+x^{13}(x^3+x)+x^{12}(x^3+x)+x^9(x^3+x)+\color{red}{x^{11}}\end{align}

Again $$x^{11}=x^8(x^3+x) -x^6(x^3+x) +x^4(x^3+x) -x^2(x^3+x) +(x^3+x) -x$$

Hence remainder is $$=-x$$

• Smooth! Thanks. Upvoted. Jul 30 at 12:16

The polynomial $$x^{k+2}+x^k$$ is divisible by $$x^3+x$$ for $$k\ge 1.$$ Hence $$[x^{13}+x^{14}+\ldots +x^{20}]$$ and $$x^{10}+x^{12}$$ are divisible by $$x^3+x.$$ We are down to $$x^{11}$$ (thanks @Cathedral ) and $$\displaylines{x^{11}=x^{11}+x^9-(x^9+x^7)+(x^7+x^5)\\ -(x^5+x^3)+(x^3+x)-x}$$ The remainder is equal $$-x.$$

• $x^{11}+\cdots +x^{20}$ is not divisible by $x^3+x$ Jul 30 at 11:58
• I think you mean that only $x^{11}$ is left over... which does in fact leave $-x$ as the remainder. Jul 30 at 12:00
• $-x$ is correct (see my answer) Jul 30 at 12:00
• Thanks. I will re-edit soon Jul 30 at 12:02
• @Cathedral You are absolutely right. Jul 30 at 12:18

$$\overbrace{\!\!\bmod \color{c00}{x^2\!+\!1}}^{\color{#c00}{\large x^2\ \equiv\ -1}\!\!}\!:\ f\color{#0af}{\!+\!x^9} =\! (x^9\!+\!x^{13}\!+\!x^{17})\!\!\overbrace{(1\!+\!x\!+\!x^2\!+\!x^3)}^{\large ((\color{#c00}{x^2})^2-1)/(x-1)=\color{#0a0}0}\!\!\equiv\color{#0a0}0\,$$ so $$\,f \equiv \color{#0af}{-x^9} = -x(\color{#c00}{x^2})^4\! \equiv -x$$

• Nice! Thank you. Upvoted. Nov 8 at 3:32

We want to find the remainder from the division:$$\frac{x^{20} + x^{19} + \ldots + x^{11} + x^{10}}{x^3 + x}$$

Now note that $$(x^3 + x)(x^{n+1} + x^n ) = x^{n+4} + x^{n+3} + x^{n+2} + x^{n+1},$$

so that

$$\frac{x^{20} + x^{19} + \ldots + x^{11} + x^{10}}{x^3 + x} = x^{17} + x^{16} + x^{13} + x^{12} + \frac{x^{12} + x^{11} + x^{10}}{x^3 + x}$$

and using long division you can show that the remainder from the final term is $$-x.$$

Peter's method is more efficient though.

• Great answer! Nice way to cut down on the length. Upvoted. Also, now that I think about it, how about this: add and subtract $\bf x^9+x^8+\dots+x$ then make pairs of 4 to be finally left with $\bf -x$. Is this alright? Jul 30 at 12:43

Here $$x$$ is common, hence we can "cancel" it to get $$x^9+x^{10}+x^{11}+x^{12}+ \cdots +x^{19}$$ & $$x^2+1$$

By your method, let this be $$f(x) = (x^2+1)g(x)+ax+b$$

At $$x=i$$, we get $$x^9+x^{10}+x^{11}+x^{12}+ \cdots +x^{19} = 0 + ai+b$$
At $$x=-i$$, we get $$x^9+x^{10}+x^{11}+x^{12}+ \cdots +x^{19} = 0 - ai+b$$

LHS in both can be calculated by Geometric Progression. We will end up with $$2$$ Simultaneous Equations having complex co-efficients.

Solving that will give the required reminder.

Alternately, we know that $$x^4 = 1$$ when $$x=i$$ or $$x=-i$$.

With that, we can reduce the given Equations:
$$x^1+x^{2}+x^{3}+x^{0}+ \cdots +x^{3} = 0 + ai+b$$
$$x^1+x^{2}+x^{3}+x^{0}+ \cdots +x^{3} = 0 - ai+b$$

$$(+i)+(-1)+(-i)+(+1)+ \cdots +(-i) = 0 + ai+b$$
$$(-i)+(-1)+(+i)+(+1)+ \cdots +(+i) = 0 - ai+b$$

$$(0i)+(-1) = 0 + ai+b$$
$$(0i)+(-1) = 0 - ai+b$$

Both give $$(a,b)=(0,-1)$$

Plugging into the original, before we did the "cancellation", we get $$0x^2-x = -x$$

• Great answer! Thank you. Upvoted. Jul 30 at 12:26