Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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$.
$\!\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}$
e.g. if $\,x = 10\,$ we get the standard divisibility test by $101$ via the alternating digit sum in radix $100\,$ (the radix $100$ analog of the divisibility by $11$ test in radix $10)$.
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.
$$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:
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}$
