<s>[INST] Finding the remainder of a polynomial divided by $x^4+x^2+1$ if remainders when dividing by $x^2+x+1$, $x^2-x+1$ are $-x+1$, $3x+5$. 
Find the remainder of $f$ divided by $g(x)=x^4+x^2+1$ if the remainder of $f$ divided by $h_1 (x)=x^2+x+1$ is $-x+1$ and the remainder of $f$ divided by $h_2(x)=x^2-x+1$ is $3x+5$.

My attempt was to write $f(x)=(x^4+x^2+1)q(x)+Ax^3+Bx^2+Cx+D=(x^2+x+1)(x^2-x+1)q(x)+Ax^3+Bx^2+Cx+D$ and then factor out $x^2+x+1$ to get $f(x)=(x^2+x+1)[(x^2-x+1)q(x)+B]+Ax^3+(C-B)x+(D-B)$, then do the same for $x^2-x+1$ and then use that along with the known remainder of $f$ divided by $x^2+x+1$ and $x^2-x+1$ to obtain $A$, $B$, $C$, $D$. However, $Ax^3$ is in the way so I don't know how to proceed nor do I have any other ideas to start with.
 [/INST] Using the Extended Euclidean Algorithm as described in this answer and adapted to polynomials yields
$$
\begin{array}{r|r|r|r}
\bbox[5px,border:2px solid #C00]{x^2+x+1}&\bbox[5px,border:2px solid #C00]{1}&0\\
\bbox[5px,border:2px solid #090]{x^2-x+1}&0&\bbox[5px,border:2px solid #090]{1}\\
2x\phantom{{}+0}&1&-1&1\\
1&\bbox[5px,border:2px solid #C00]{-\frac12x+\frac12}&\bbox[5px,border:2px solid #090]{\frac12x+\frac12}&\frac12x-\frac12\\
0&x^2\phantom{\frac12}-x+\,1&-x^2\phantom{\frac12}-x-\,1&2x\phantom{{}+\frac12}
\end{array}\tag1
$$
which says that
$$
\overbrace{\color{#C00}{\left(x^2+x+1\right)\left(-\tfrac12x+\tfrac12\right)}}^{\large\frac12-\frac12x^3}+\overbrace{\color{#090}{\left(x^2-x+1\right)\left(\tfrac12x+\tfrac12\right)}}^{\large\frac12+\frac12x^3}=1\tag2
$$
Which, in turn says that
$$
\frac12-\frac12x^3\equiv\left\{\begin{array}{}
0&\bmod x^2+x+1\\
1&\bmod x^2-x+1
\end{array}\right.\tag3
$$
and
$$
\frac12+\frac12x^3\equiv\left\{\begin{array}{}
1&\bmod x^2+x+1\\
0&\bmod x^2-x+1
\end{array}\right.\tag4
$$
Therefore, the desired polynomial is
$$
\begin{align}
\scriptsize(-x+1)\overbrace{\left(\tfrac12+\tfrac12x^3\right)}^{\substack{1\bmod x^2+x+1\\0\bmod x^2-x+1}}+(3x+5)\overbrace{\left(\tfrac12-\tfrac12x^3\right)}^{\substack{0\bmod x^2+x+1\\1\bmod x^2-x+1}}
&=3+x-2x^3-2x^4\\
&\equiv\bbox[5px,border:2px solid #CA0]{5+x+2x^2-2x^3}\bmod x^4+x^2+1\tag5
\end{align}
$$
</s>