Remainder when the polynomial $1+x^2+x^4+\cdots +x^{22}$ is divided by $1+x+x^2\cdots+ x^{11}$

Question

Question : Find the remainder when the polynomial $1+x^2+x^4+\ldots +x^{22}$ is divided by $1+x+x^2+\cdots+ x^{11}$.

I tried using Euclid's division lemma, I.e.

$$P_1(x)=1+x^2+x^4+\cdots+x^{22}$$

$$P_2(x)=1+x+x^2+\cdots+x^{11}$$

Then for some polynomial $Q(x)$ and $R(x)$; we have

$$P_1(x)=Q(x)\cdot P_2(x)+R(x)$$

Now, we put the values of $x$ such that $R(x)=0$ and form equations, but this method is way too long and solving the 11 set of equations for 11 variable (Since $R(x)$ a polynomial of at most 10 degree) is impossible to do for a competitive exam where the average time for solving a question is 3 minutes.

Another method is using the original long division method, and following the pattern, we can predict $Q(x)$ and $R(x)$, but it's also very hard and time taking.

I am searching for a simple solution to this problem since last a week and now I doubt even we have a simple solution to this question.

Can you please give me a hint/solution on how to proceed to solve this problem in time?

Thanks!

Answer 1

$$P_1(x)=\frac{x^{24}-1}{x^2-1}$$ $$P_2(x)=\frac{x^{12}-1}{x-1}$$ $$\frac{P_1(x)}{P_2(x)}=\frac{x^{24}-1}{x^{12}-1}\cdot\frac{x-1}{x^2-1}=\frac{x^{12}+1}{x+1}$$ Then Ruffini's rule tells us that the remainder of this reduced division is the polynomial $x^{12}+1$ evaluated at $-1$, i.e. 2. When the top and bottom of $\frac2{x+1}$ are multiplied by $\frac{x^{12}-1}{x^2-1}$, the denominator becomes $P_2(x)$ and the numerator gives the final answer of $\frac{2(x^{12}-1)}{x^2-1}=2+2x^2+2x^4+2x^6+2x^8+2x^{10}$.

Answer 2

Let $\,P_n(x)=1+x+\cdots+x^{n-1}=(x^n-1)/(x-1)\,$, then the problem is equivalent to finding the remainder of the division $\,P_{12}(x^2) / P_{12}(x)\,$.

The remainder is $\,2 \,P_6(x^2)\,$, which follows for $\,n=6\,$ from the general identity:

$$ \begin{align} P_{2n}(x^2) = \frac{x^{4n}-1}{x^2-1} &= \frac{x^{2n}-1}{x-1} \, \frac{x^{2n}+1}{x+1} \\[5px] &= \, \frac{x^{2n}-1}{x-1} \, \frac{x^{2n}-1+2}{x+1} \\[5px] &= - \, \frac{x^{2n}-1}{x-1} \, \frac{(-x)^{2n}-1}{(-x)-1} + 2 \, \frac{x^{2n}-1}{x^2-1} \\[5px] &= - \, P_{2n}(x) P_{2n}(-x) + 2 P_n(x^2) \end{align} $$

Answer 3

The divisor $f = (\color{#c00}{x^{\large 12}\!-1})/(x-1)$ and $\,g = (1+\color{#c00}{x^{\large 12}})(1+x^{\large 2}+\cdots+x^{\large 10})\,$ is the dividend

hence $ \bmod\, f\!:\,\ \color{#c00}{x^{\large 12}\equiv 1}\ $ implies that $\,\ g\equiv\, (1\:+\ \color{#c00}1\,)\:(1+x^{\large 2}+\cdots+x^{\large 10})$

---

Remark $ $ Generally we can write $\ g = f_{\large 0} + f_{1} x^{\large 12}\! + \cdots + f_{\large k\,} x^{\large 12k}\! = h(\color{#c00}{x^{\large 12}}),\, $ $\,\deg f_{\large i} < 12$

hence as above $\ \color{#c00}{x^{\large 12}\equiv 1}\, \Rightarrow\, g\bmod f\,=\, f_{\large 0}+f_1+\cdots+ f_{\large k}\, =\ h(\color{#c00}1)$

---

Generally, $ $ if $\ f\mid \color{#c00}{x^{\large n}\!-1}\ $ then $\ g\bmod f\, =\, (g\bmod \color{#c00}{x^{\large n}\!\equiv 1})\bmod f$

Answer 4

\begin{eqnarray*} p_2(x) &=& (x^6+1)(x^5+x^4+x^3+x^2+x+1)\\ &=& (x^6+1)(x^3+1)(x^2+x+1)\\ &=& (x^6+1)(x+1)(x^2-x+1)(x^2+x+1)\\ &=& (x+1)(x^6+1)(x^4+x^2+1) \end{eqnarray*}

\begin{eqnarray*} p_1(x) &=& (x^{12}+1)(x^{10}+x^8+x^6+x^4+x^2+1)\\ &=& (x^{12}+1)(x^6+1)(x^4+x^2+1) \end{eqnarray*}

Write $$p_1(x) = k(x)p_2(x) +r(x)$$ then $(x^6+1)(x^4+x^2+1)$ divides $r(x)$.

So $r(x) = (x^6+1)(x^4+x^2+1)s(x)$ where $s(x)$ is constant. So $$x^{12}+1 = k(x)(x+1)+ s(x)$$ Put $x=-1$ and we get: $s(-1)= 2$.