# Find a remainder when $(x^5+1)^{100} + (x^5-1)^{100}$ is divided by $x^4+x^2+1$

The question is:

Find a remainder when $$f(x)=(x^5+1)^{100} + (x^5-1)^{100}$$ is divided by $$x^4+x^2+1$$

I first began by decomposing $$x^4+x^2+1=(x^2+x+1)(x^2-x+1)$$ and using $$x^3-1=(x-1)(x^2+x+1)\\x^3+1=(x+1)(x^2-x+1)$$

and could get remainders when divided by each factors. \begin{align} (x^5+1)^{100}&\equiv(x^2+1)^{100}&(\mathrm{mod}\,x^3-1)\\ &\equiv(-x)^{100}&(\mathrm{mod}\,x^2+x+1)\\ &=x^{100}=x\cdot(x^3)^{33}\\ &\equiv x&(\mathrm{mod}\,x^3-1)\\\\ (x^5-1)^{100}&\equiv(x^2-1)^{100}&(\mathrm{mod}\,x^3-1)\\ &=(x+1)^{100}(x-1)^{100}\\ &=(x^2+x+1+x)^{50}\cdot(x^2+x+1-3x)^{50}\\ &\equiv x^{50}\cdot(-3x)^{50}&(\mathrm{mod}\,x^2+x+1)\\ &=3^{50}(x^2)^{50}=3^{50}x\cdot(x^3)^{33}\\ &\equiv 3^{50}x&(\mathrm{mod}\,x^3-1)\\ \end{align} Therefore $$f(x)\equiv (3^{50}+1)x\quad(\mathrm{mod}\,x^2+x+1)\\$$ Similarly, $$f(x)\equiv -(3^{50}+1)x\quad(\mathrm{mod}\,x^2-x+1)\\$$ So \begin{align} f(x) &= (x²+x+1)p(x) + (3^{50}+1)x\\ f(x) &= (x²-x+1)q(x) - (3^{50}+1)x \end{align} As $$f(x)$$ is an even function, I could derive that $$q(x)=p(-x)$$ And then, my plan was to find a remainder when $$p(x)$$ is devided by $$x²-x+1$$ and so on \begin{align} p(x)&=(x²-x+1)A(x)+Cx+D\\ q(x)&=(x²+x+1)B(x)+Ex+F\\ \end{align} So that I could conclude that $$f(x)\equiv (x^2+x+1)(Cx+D)+(3^{50}+1)x\quad(\mathrm{mod}\,x^4+x^2+1)\\$$ Using $$p(x)=q(-x)$$, I could derive that $$A(x)=B(-x)$$, $$C=-E$$, and $$D=F$$. And further using $$f(x)=f(-x)$$, I could do \begin{align} p(x)&=e(x)+o(x)\quad(e(x)=e(-x)\,,o(x)=-o(-x))\\ \rightarrow&(x²+x+1)(e(x)+o(x)) + (3^{50}+1)x = (x²-x+1)(e(x)-o(x)) - (3^{50}+1)x\\ \rightarrow&2xe(x)+(x²+1)o(x) + 2(3^{50}+1)x = 0\\ p(x)&=\frac{(-x²+2x-1)o(x)}{2x} - (3^{50}+1) = \frac{(-x²+x-1 + x)o(x)}{2x} - (3^{50}+1)\\ &= \frac{(-x²+x-1)o(x)}{2x} + \frac{o(x)}2 - (3^{50}+1) \end{align} And that was it. I couldn't proceed further.

## 1 Answer

Therefore,  with $$\,n = 3^{50}\!+1$$
\begin{align} &f(x)\,\equiv\ \ \ n\,\color{#c00}x\quad(\mathrm{mod}\ \ x^2\!+\!x\!+\!1)\\[.2em] &f(x)\,\equiv -n\,\color{#0a0}x\quad(\mathrm{mod}\ \ x^2\!-\!x\!+\!1)\end{align}\qquad\qquad

Hint: make the following substitutions \begin{align}\color{#c00}x &\equiv -(x^2\!+\!1)\!\pmod{x^2\!+\!x\!+\!1}\\ \color{#0a0}x&\equiv \ \ \ \ \ x^2\!+\!1\,\pmod{x^2\!-\!x\!+\!1} \end{align}

which yields that $$\, f\equiv -n(x^2\!+\!1)\,$$ mod both, so also mod their lcm = product. QED  Good work.

• The "hence" is by lcm or CCRT = Constant-case CRT as described here. – Bill Dubuque Apr 19 at 22:34
• Thank you. That completes the last piece. I appreciate. – Kay K. Apr 19 at 22:49