6
$\begingroup$

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.

Answer:

Option (B)

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

8 Answers 8

8
$\begingroup$

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.

$\endgroup$
2
  • 2
    $\begingroup$ (+1) for the creative solution (although it relies on that one of the options is correct) $\endgroup$
    – Peter
    Jul 30 at 12:20
  • 1
    $\begingroup$ 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. $\endgroup$ Jul 30 at 12:37
6
$\begingroup$

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

$\endgroup$
11
  • $\begingroup$ Why $ x^6≡x^2$? $\endgroup$ Jul 30 at 12:13
  • 1
    $\begingroup$ We have $x^3\equiv -x\mod (x^3+x)$ . Now just square both sides $\endgroup$
    – Peter
    Jul 30 at 12:14
  • $\begingroup$ 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. $\endgroup$ Jul 30 at 12:23
  • $\begingroup$ @InanimateBeing $p \equiv a \text{ mod } b$ means $(p-a)$ is divisible by $b$. Clearly, $x^3-(-x)$ is divisible by $x^3+x$. $\endgroup$
    – Cathedral
    Jul 30 at 12:30
  • 3
    $\begingroup$ 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. $\endgroup$
    – Peter
    Jul 30 at 13:03
5
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ 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! $\endgroup$ Jul 30 at 14:39
5
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Smooth! Thanks. Upvoted. $\endgroup$ Jul 30 at 12:16
5
$\begingroup$

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

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

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

$\endgroup$
1
  • $\begingroup$ Nice! Thank you. Upvoted. $\endgroup$ Nov 8 at 3:32
3
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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? $\endgroup$ Jul 30 at 12:43
3
$\begingroup$

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$

$\endgroup$
1
  • 1
    $\begingroup$ Great answer! Thank you. Upvoted. $\endgroup$ Jul 30 at 12:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.