# If $x^{19}+x^{17}+x^{13}+x^{11}+x^{7}+x^{5}+x^{3}$ is divided by $(x^2 +1)$, then find the remainder

If the polynomial $$x^{19}+x^{17}+x^{13}+x^{11}+x^{7}+x^{5}+x^{3}$$ is divided by $$(x^ 2 +1)$$, then the remainder is:

How Do I solve this question without the tedious long division?

Using remainder theorem , we can take $$x^3$$ common and put $$x^2 =-1$$ although $$x$$ is not a real number. By this method, I got the right answer as $$-x$$. Is it the right way? Because $$x$$ comes out to be $$i$$ which is not real.

Also , can I apply remainder theorem to quadratic divisor polynomials in this way?

Following may help

$$P(x)=x^{19} +x^{17} +x^{13} +x^{11} +x^{7} +x^{5} +x^{3}$$

$$P(x)=x^{17}(x^2+1)+x^{11}(x^2+1)+x^{5}(x^2+1)+x^3$$

$$P(x)=(x^2+1)(x^{17}+x^{11}+x^{5})+x^3$$

That $$x^3$$ looks sad alone , Let's also include it

$$P(x)=(x^2+1)(x^{17}+x^{11}+x^{5})+x^3+x-x$$

$$P(x)=(x^2+1)(x^{17}+x^{11}+x^{5}+x)-x$$

$$P(x)=(x^2+1)(x^{17}+x^{11}+x^{5}+x)-x$$

Now this is in the form -

$$P(x)=Q(x)*d(x)+R(x)$$

Hence you get everything now

You have $$P=x^{19}+x^{17}+x^{13}+x^{11}+x^7+x^5+x^3$$, you want to compute the remainder when dividing it by $$x^2+1$$.

$$\mod{x^2+1}$$, we have $$x^2\equiv -1$$, so $$P \equiv (-1)^9x+(-1)^8x+(-1)^6x+(-1)^5x+(-1)^3x+(-1)^2x+(-1)x \equiv -x$$

As we the remainder we look for is linear, it can only then be $$-x$$.

Of course it may not be as easy computationally for other polynomials and divisors, but yes, a similar approach will work as you can reduce every higher power monomial to less than the degree of the divisor.

With $$y:=x^2$$,$$P(x)=x^{19} +x^{17} +x^ {13} +x^ {11} +x^ 7 +x^ 5 +x^ 3=(y^9+y^8+y^6+y^5+y^3+y^2+y)x$$ and you are asked the remainder of the division by the polynomial $$x^2+1=y+1$$.

You can write

$$P(x)=(Q(y)(y+1)+R(y))x$$ where $$R$$ is of degree $$0$$, i.e. a constant (which you know how to compute by division by a linear binomial).

From this

$$P(x)=Q(x^2)(x^2+1)x+Rx$$ and the remainder is $$Rx$$.

Note that at no time do you have to deal with the solutions of $$x^2+1=0$$.

• You omitted the $y^3$ term in the expression for $P(x)$ Jun 25, 2021 at 13:10

\!\begin{align}{\rm Hint}\!\!:\ \bmod x^2+1\!:\,\ \color{#c00}{x^2\equiv -1}\ \Rightarrow\ & \overbrace{f_0(\color{#c00}{x^2})\, +\, f_1(\color{#c00}{x^2})\,x}^{\large \text{even + odd part}\!\!\!\!\!\!}\\[.3em] \equiv\:\!\ & f_0(\color{#c00}{-1}) + f_1(\color{#c00}{-1})\, x\end{align}

Remark  To understand how the answers are related note that it is easy to prove the equivalence below (either directly by the division algorithm, or using $$\,\Bbb Q[x]/(x^2+1)\cong \Bbb Q[i],\ i^2=-1);\,$$ said simply: the (ring) arithmetic of polynomials mod $$\,x^2+1\,$$ with coef's $$\in\Bbb Q$$ is algebraically the same as the arithmetic of complex numbers of the form $$\,a+b\,i,\,$$ for $$\,a,b\in\Bbb Q,\,$$ since

$$f(x)\equiv a+b\,x \!\!\!\pmod {\!x^2+1}\iff f(i) = a + b\,i$$

CRT or Lagrange interpolation yields a closed form (cf. first congruence above)

$$f(x) \,\equiv\, \dfrac{f(i)+f(-i)}2 + \dfrac{f(i)-f(-i)}{2i}\,x\ \ \!\!\!\!\pmod{\!x^2+1}$$

Note that the above is the same result that "lone student" derived by evaluating $$\,f(x)\,$$ at $$\,x = \pm i\,$$ then solving the resulting system of equations for $$\,a,b.\,$$ So such evaluation (and interpolation) methods are special cases of CRT = Chinese Remainder Theorem (when the moduli are linear polynomials $$\,x-a,\,$$ so congruence boils down to evaluation $$\,f(x)\equiv f(a)\pmod{x-a}\,$$ by the Polynomial Remainder Theorem..

These methods often come in handy for computations, e.g. here where I show how to use them in a (quadratic) nonlinear generalization of the Heaviside cover-up method for computing partial fraction expansions with quadratic denominators.

• See here for more on decompositions of polynomials into even + odd parts (and, more generally, power series bisections and multisections). You may find it instructive to compare this method to the common method of evaluation at $\,\pm i\ \$ Jun 25, 2021 at 20:04
• Is there a relationship between the last part of your answer and my answer? Your last formulas were similar to mine. I'm not totally in control of the subject.. Jun 26, 2021 at 0:02
• @lone It's the same formula - see the note I appended. Jun 26, 2021 at 0:27
• Honestly the things I did, I wasn't sure. (I wasn't sure of my answer, it's the first time I've used such a method). Thank you for the additional information. You provide very useful information. As you always do. Jun 26, 2021 at 0:30
• @lone Glad you found it helpful. These more general results aren't usually discussed till one studies abstract algebra or number theory. But they can be understood earlier, and doing so often lends insight. Jun 26, 2021 at 0:32

$$P(x)=Q(x)(x^2+1)+R(x), \\ R(x)=mx+n$$

\begin{align}\begin{cases} mi+n=P(i) \\ -mi+n=P(-i)\end{cases}\end{align}

\begin{align}\implies n&=\frac{P(i)+P(-i)}{2} \\ &=\frac{P(i)-P(i)}{2}\\ &=0.\end{align}

\begin{align}\thinspace\thinspace\thinspace\thinspace\thinspace\thinspace\implies m&=\frac{iP(-i)-iP(i)}{2}\\ &=\frac{-2iP(i)}{2}\\ &=-iP(i)\\ &=i^2=-1.\end{align}

$$\thinspace\thinspace\thinspace\thinspace\thinspace\thinspace\thinspace\thinspace\thinspace\thinspace\implies R(x)=mx+n=-x.$$

Hint:

• Notice that remainder is linear polynomial $$r(x)=ax+b$$ with $$a,b$$ real.
• Notice that $$i$$ is zero of $$x^2+1$$.
• Write down remainder theorem $$p(x)=k(x)(x^2+1)+r(x)$$

Note that mod $$x^2+1$$, $$x^n\equiv\left\{\begin{array}{} (-1)^{n/2}&\text{if n is even}\\ (-1)^{(n-1)/2}x&\text{if n is odd} \end{array}\right.$$ Therefore, $$\overset{\raise{3pt}{-x}}{x^{19}}+\overset{\raise{3pt}{+x}}{x^{17}}+\overset{\raise{3pt}{+x}}{x^{13}}+\overset{\raise{3pt}{-x}}{x^{11}}+\overset{\raise{3pt}{-x}}{x^7}+\overset{\raise{3pt}{+x}}{x^5}+\overset{\raise{3pt}{-x}}{x^3}\equiv-x$$

Expanded from a comment on Macavity's answer:

Since my comment on Macavity's answer (which I upvoted) has been deleted, I will mention here that I did not notice, when I posted, that my answer was essentially the same as theirs. I debated deleting this answer, but as this answer gives additional detail, I decided to leave it, if nothing else, as an addition to Macavity's answer.

NOTE : Roots of $$x^2+1$$ are $$(i,-i)$$ OR $$x^2+1=(x-i)(x+i)$$ .

So , remainder when $$P(x)$$ is divided by $$(x-i)$$ & $$(x+i)$$ respectively are : $$P(i)=i^{19}+i^{17}+i^{13}+i^{11}+i^{7}+i^{5}+i^{3}$$ $$=-i+i+i-i-i+i-i\Rightarrow\color{red}{-i}$$ And , $$P(-i)=(-i)^{19}+(-i)^{17}+(-i)^{13}+(-i)^{11}+(-i)^{7}+(-i)^{5}+(-i)^{3}$$ $$=i-i-i+i+i-i+i\Rightarrow \color{red}i$$

By Division Algorithm : $$P(x)=(x-i)f(x)-i ⠀⠀⠀⠀⠀(1)$$ And , $$P(x)=(x+i)g(x)+i⠀⠀⠀⠀(2)$$ Subsitute $$x$$ with $$i$$ in $$eq^n(2)$$ $$P(i)=(i+i)g(i)+i$$ Note: $$P(i)=-i$$ (proved above) $$-i=2i\cdot g(i)+i$$ $$\color{red}{-1=g(i)}$$

Now use Remainder Theorem for $$g(x)$$ : $$g(x)=(x-i)h(x)-1⠀⠀⠀⠀(3)$$

Use the value of $$g(x)$$ in $$eq^n(2)$$ : $$P(x)=(x+i)((x-i)h(x)-1)+i$$

$$P(x)=(x+i)(x-i)h(x)-x- i+ i$$

OR

$$P(x)=(x^2+1)h(x)-x$$

So , finally the remainder is $$\color{red}{-x}$$