# What's the remainder when $x^{7} + x^{27} + x^{47} +x^{67} + x^{87}$ is divided by $x ^ 3 - x$

What's the remainder when $$x^{7} + x^{27} + x^{47} +x^{67} + x^{87}$$ is divided by $$x ^ 3 - x$$ in terms of $$x$$?I tried factoring $$x$$ from both polynomials but I don't know what to do next since there'd be a $$1$$ in the second polynomial. Any help would be appreciated!

• @Arthur Yeah sorry. I fixed it. May 3 '19 at 16:14
• Do you already know modular arithmetic or congruences? May 3 '19 at 17:42

Modulo $$x^3-x$$ we have $$x^3=x$$ so $$x^{2n+1}=x$$ for any integer $$n\ge 0$$ (a trivial induction exercise). Hence your sum leaves remainder $$5x$$.

• @OP Note that the above claim requires rigorous proof (e.g. by induction). More generally $\,xf(x^2) \bmod x^3\!-\!x\,=\, xf(1)\,$ by modular arithmetic - as in my answer (there the induction is hidden in the application of the Polynomial Congruence Rule). $\ \ \$ May 3 '19 at 17:35

Let your $$87$$-th degree polynomial be $$P(x)$$. You're to find $$Q(x)=ax^2+bx+c$$ where $$P(x)=(x^3-x)D(x)+Q(x).$$ Then: $$5=P(1)=0\cdot D(1)+Q(1)\implies Q(1)=5;\\ 0=P(0)=0\cdot D(0)+Q(0)\implies Q(0)=0;\\ -5=P(-1)=0\cdot D(-1)+Q(-1)\implies Q(-1)=-5.$$ From $$Q(0)=0$$, it is easy to see $$c=0$$. Using this and the other 2 conditions, we have: $$a+b=5,\quad a-b=-5\implies a=0,\quad b=5.$$ In sum $$Q(x)=5x$$.

• Why must $Q(x)$ be quadratic? May 3 '19 at 16:53
• $Q(x)$ can at the most be a quadratic. But owing to the conditions turns out to be linear. May 3 '19 at 16:58
• @ChaseRyanTaylor Because we're dividing by $x^3-x$, a 3rd-order polynomial. May 3 '19 at 17:04

$$xf(x^2)\,\bmod\, x(x^2\!-\!1)\, =\, x\,(\overbrace{f(\color{#c00}{x^2})\,\bmod\, x^2\!-\!1}^{\color{#c00}{\Large x^2\ \equiv\,\ 1}})\, =\, xf(\color{#c00}{ 1})\, =\, 5x$$

• We applied $\ \large hf\bmod hg = h\,(f\bmod g),\,$ the mod Distributive Law, to factor out $\, h = x\ \ \$ May 3 '19 at 17:37
• And we used $\large \bmod x^2\!-\!1\!:\,\ \color{#c00}{x^2\equiv 1}\,\Rightarrow\, f(\color{#c00}{x^2})\equiv f(\color{#c00}1)\$ by the Polynomial Congruence Rule $\ \ \$ May 5 '19 at 14:29

$$P(x)=x^{7} + x^{27} + x^{47} +x^{67} + x^{87}=x(x-1)(x+1)q(x) + r(x)$$

Note that we have $$r(1)= P(1)$$, $$r(0)= P(0)$$ and $$r(-1)=P(-1)$$.

We can find $$r(x)=x^2+ax+b =5x$$ using the above information.

Doing long division: $$P(x)=\frac{x^{7} + x^{27} + x^{47} +x^{67} + x^{87}}{x^3-x}=\frac{x^{86}+x^{66}+x^{46}+x^{26}+x^6}{x^2-1}=\\ \frac{\sum_{i=0}^{9}(x^{86-2i}-x^{84-2i})+2\sum_{i=0}^{9}(x^{66-2i}-x^{64-2i})+3\sum_{i=0}^{9}(x^{46-2i}-x^{44-2i})+4\sum_{i=0}^{9}(x^{26-2i}-x^{24-2i})+5\sum_{i=0}^{2}(x^{6-2i}-x^{4-2i})+5}{x^2-1}=\\ Q(x)+\frac{5}{x^2-1}=Q(x)+\frac{5x}{x^3-x}.$$

$$x^{2n}\equiv1 \pmod{x^2-1}$$ so $$(x^2-1) | (x^{2n}-1)$$ so $$(x^3-x) | (x^{2n+1}-x)$$

so $$x^{2n+1}\equiv x \pmod {x^3-x}$$

so $$x^7+x^{27}+x^{47}+x^{67}+x^{87}\equiv 5x \pmod {x^3-x}$$

• @OP Above is essentially the modular proof in my answer with the modular language (congruences) eliminated, i.e. expressed in the more primitive language of divisibility. When learning modular arithmetic you may find it instructive to go back-and-forth between both languages to better understand their relationship. May 5 '19 at 14:24
• i.e. the first 2 lines show $\,\large xf(x^2) \equiv xf(1)\, \pmod{\!x^3\!-\!x}\$ for special case $\large \,f = x^n\ \ \$ May 5 '19 at 14:38