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.


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.
