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

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!

• When divided $P_1(x)$ by $P_2(x)$, you can simply replace $x^{12+k}$ by $x^k$ for each $k=0,2,4,6,8,10$ to get the remainder. – Batominovski Aug 24 '17 at 0:14
• As a quick algebraic trick, I believe the quotient is the same polynomial with alternating signs. That is $\sum_{i=0}^{11} (-1)^{i+1}x^i$. – lulu Aug 24 '17 at 0:16
• @lulu How you got that? – Jaideep Khare Aug 24 '17 at 0:23
• @JaideepKhare Direct calculation. Well, a few examples with smaller powers than $11$ to conjecture the pattern, but then it's fairly easy to read off the coefficient of the product. There should be a good cyclotomic argument for it, but I haven't got one yet. – lulu Aug 24 '17 at 1:53
• Jaideep: Let me suggest that you concentrate on the comments (and answers) you receive rather than on the votes of other users, which, by design, are none of your business. (Which "further explanations" would you need to understand Batominovski's comment? It seems concise and quite clear to me...) – Did Sep 2 '17 at 9:57

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

• @JaideepKhare I should have addressed your questions, does this look OK? – Parcly Taxel Aug 24 '17 at 0:27
• @ParclyTaxel Yes, Thanks a lot! – Jaideep Khare Aug 24 '17 at 0:28

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}

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$

• I don't clearly understand why $x^{12}=1 \pmod{f}$ Can you please explain? – Jaideep Khare Aug 24 '17 at 7:01
• @Jaideep $\ \bmod f\!:\,\ \color{#0a0}{f\equiv 0}\,\Rightarrow\,\color{#c00}{x^{\large 12}\!-1} = (x\!-\!1)\color{#0a0}f\equiv 0,\,$ i.e. because $\,f\,$ divides $\,x^{\large 12}\!-\!1\ \$ – Bill Dubuque Aug 24 '17 at 14:29
• @Downvoter If something is not clear then please feel welcome to ask questions and I will be happy to elaborate. – Bill Dubuque Sep 2 '17 at 13:36

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