嘿，我来帮你搞定这个多项式求余的问题～ 我们可以通过多项式模运算的性质来简化高次项的计算，核心是先找到$x$在模$x^2+x+1$下的等价关系，这样就能把高次幂的$x$降成低次的啦。

首先先明确两个关键的等价关系：

• 因为$x^3 - 1 = (x-1)(x^{2+x+1)$，所以当除以$x}2+x+1$时，$x^3$的余数就是1，也就是 $x^3 \equiv 1 \pmod{x^2+x+1}$；
• 从除数$x^2+x+1=0$可以直接推导出 $x^2 \equiv -(x+1) \pmod{x^2+x+1}$。

接下来我们一步步化简$P(x)$：

$$
\begin{align}
P(x) &= 3x^{12n+5}+x3+1 \
&\equiv 3x^{12n+5} + 2 \pmod{x^2+x+1} \quad \text{（因为}x^{3\equiv1\text{，所以}x}3+1=1+1=2\text{）} \
&\equiv 3x^{3\times4n + 2} + 2 \pmod{x^2+x+1} \quad \text{（把指数拆成3的倍数加余项：12n+5=3×4n + 2）} \
&\equiv 3(x³⁾{4n} \cdot x^2 + 2 \pmod{x^2+x+1} \
&\equiv 3\times1^{4n} \cdot x^2 + 2 \pmod{x^2+x+1} \quad \text{（因为}x^3\equiv1\text{，1的任何次幂都是1）} \
&\equiv 3x^2 + 2 \pmod{x^2+x+1} \
&\equiv 3\times(-(x+1)) + 2 \pmod{x^2+x+1} \quad \text{（代入之前得到的}x^2\equiv-(x+1)\text{）} \
&\equiv -3x -3 + 2 \pmod{x^2+x+1} \
&\equiv -3x -1 \pmod{x^2+x+1}
\end{align}
$$

所以$P(x)$除以$x^2+x+1$的余数就是$\boldsymbol{-3x -1}$哦。

备注：内容来源于stack exchange，提问作者user956668