Does anyone know of a much faster way to solve this polynomial question? A monic cubic $p(x) $ is divided by $(x^2 +x +1)$ and the remainder is $(2x+3)$. When $p(x)$ is divided by $x(x+3)$, the remainder is $5(x+1)$. Find $p(x)$
So the way I solved it was through using long division - as you can imagine very lengthy, and not very efficient in exam situations. I then equated the remainders with the given remainders. However, in an exam situation, would there be an even faster way? I am open to suggestions.
 A: here is a trick: as the polynomial has leading coefficient 1 and degree 3 we have $$p(x)=(x+K)(x^2+x+1)+2x+3$$  Now use the fact that $$p(x)=x(x+3)g(x)+5(x+1)$$ $$p(0)=5(0+1)=5$$ $$K=2$$
A: This may not be a quicker way, but it is systematic and will work in all cases where the two moduli have no common factors. Hopefully, it also might make the use of the Extended Euclidean Algorithm with the Chinese Remainder Theorem more transparent.

We want
$$
\begin{align}
p(x)&\equiv2x+3&&\pmod{x^2+x+1}\tag{1a}\\
p(x)&\equiv5x+5&&\pmod{x^2+3x}\tag{1b}
\end{align}
$$
so we apply the Extended Euclidean Algorithm (as implemented in this answer and adapted to polynomials) to $x^2+3x$ and $x^2+x+1$:
$$
\begin{array}{c|c|c|c}
x^2+3x&1&0\\
x^2+x+1&0&1\\
2x-1&1&-1&1\\
\frac74&-\frac{2x+3}4&\frac{2x+7}4&\frac{2x+3}4
\end{array}\tag2
$$
Thus, we get
$$
(2x+7)\left(x^2+x+1\right)-(2x+3)\left(x^2+3x\right)=7\tag3
$$
So we have
$$
-\frac{(2x+3)\left(x^2+3x\right)}7\equiv\left\{
\begin{align}
&1&&\pmod{x^2+x+1}\\
&0&&\pmod{x^2+3x}
\end{align}
\right.\tag4
$$
and
$$
\frac{(2x+7)\left(x^2+x+1\right)}7\equiv\left\{
\begin{align}
&0&&\pmod{x^2+x+1}\\
&1&&\pmod{x^2+3x}\\
\end{align}
\right.\tag5
$$
Adding $2x+3$ times $(4)$ to $5x+5$ times $(5)$ yields one solution to $(1)$:
$$
\begin{align}
&\overbrace{(5x+5)\frac{(2x+7)\left(x^2+x+1\right)}7}^{\substack{0&\pmod{x^2+x+1}\\5x+5&\pmod{x^2+3x}}}\overbrace{-(2x+3)\frac{(2x+3)\left(x^2+3x\right)}7}^{\substack{2x+3&\pmod{x^2+x+1}\\0&\pmod{x^2+3x}}}\\
&=\frac{6x^4+31x^3+45x^2+53x+35}7\tag6
\end{align}
$$
The Chinese Remainder Theorem says that this is the solution mod $\left(x^2+x+1\right)\left(x^2+3x\right)$, so we can subtract $\frac67$ of the modulus to get
$$
\begin{align}
p(x)
&=\frac{6x^4+31x^3+45x^2+53x+35}7-\frac67\left(x^2+x+1\right)\left(x^2+3x\right)\\
&=\bbox[5px,border:2px solid #C0A000]{x^3+3x^2+5x+5}\tag7
\end{align}
$$
