What is the remainder in the following division:

$$
\left(x^{1001}-1\right):\left(x^{4}+x^{3}+2 x^{2}+x+1\right)
$$

and also when the divisor is the following polynomial:

$$
x^{8}+x^{6}+2 x^{4}+x^{2}+1
$$

(the remainder being the polynomial that results after determining the last non-negative power term of the quotient).
The division of a polynomial $\mathrm{u}(x)$ by a polynomial $\mathrm{v}(x)$ (with remainder) refers to determining a quotient polynomial $\mathrm{q}(x)$ and a remainder polynomial $\mathrm{r}(x)$ of lower degree than the divisor, such that

$$
\mathrm{u}(x)=\mathrm{q}(x) \cdot \mathrm{v}(x)+\mathrm{r}(x)
$$

If $\mathrm{r}(x)$ is identically 0, then we say that $\mathrm{u}(x)$ is divisible by $\mathrm{v}(x)$, or that $\mathrm{u}(x)$ is a multiple of $\mathrm{v}(x)$. - Here, we only need to determine $\mathrm{r}(x)$, so we look for a shorter path instead of the known division procedure.

I. The divisor in (1) can be easily factored:

$$
\mathrm{d}(x)=\left(x^{4}+x^{3}+x^{2}\right)+\left(x^{2}+x+1\right)=\left(x^{2}+x+1\right)\left(x^{2}+1\right)
$$

To simplify the division, we seek simple (i.e., with few terms) polynomials that are multiples of individual factors of $\mathrm{d}(x)$, and then those that are multiples of $\mathrm{d}(x)$ itself. According to known identities,

$$
\begin{aligned}
x^{3}-1 & =\left(x^{2}+x+1\right)(x-1), \quad \text { therefore } \\
x^{6}-1 & =\left(x^{3}-1\right)\left(x^{3}+1\right)=\left(x^{2}+x+1\right)(x-1)\left(x^{3}+1\right) \\
x^{6}+1 & =\left(x^{2}+1\right)\left(x^{4}-x^{2}+1\right), \quad \text { so } \\
\left(x^{6}-1\right)\left(x^{6}+1\right) & =x^{12}-1=\mathrm{d}(x) \cdot\left(x^{4}-x^{2}+1\right)\left(x^{3}+1\right)(x-1)
\end{aligned}
$$

Proceeding further, if $j$ is a positive integer, $x^{12 j}-1$ is divisible by $x^{12}-1$, and thus also by $\mathrm{d}(x)$; in other words, the remainder of the division $x^{12 j}: \mathrm{d}(x)$ is 1.

Now, $1001=83 \cdot 12+5$, so

$$
\frac{x^{1001}-1}{\mathrm{~d}(x)}=\frac{x^{83 \cdot 12} \cdot x^{5}-x^{5}+x^{5}-1}{\mathrm{~d}(x)}=x^{5} \cdot \frac{x^{83 \cdot 12}-1}{\mathrm{~d}(x)}+\frac{x^{5}-1}{\mathrm{~d}(x)}
$$

The last expression's first term expands to a polynomial because the second factor in the numerator is divisible by the denominator according to the above (and because $x^{5}$ is also a polynomial, and the product of two polynomials is a polynomial), so the sought remainder is identical to the remainder of the division $\left(x^{5}-1\right): \mathrm{d}(x)$. This division can also be avoided based on an observation:

$$
\begin{gathered}
x^{5}-1=(x-1)\left(x^{4}+x^{3}+x^{2}+x+1\right)=(x-1)\left(\mathrm{d}(x)-x^{2}\right)= \\
=\mathrm{d}(x) \cdot(x-1)+x^{2}(1-x)
\end{gathered}
$$

Here, $x^{2}(1-x)$ is of lower degree than $\mathrm{d}(x)$, so this is the sought remainder.

II. The divisor in (2) is $\mathrm{d}\left(x^{2}\right)$, which can be calculated from $x^{2}$ in the same way that (1)'s divisor is calculated from $x$. Therefore, according to the above, for every positive integer $j$, $\left(x^{2}\right)^{12 j}-1=x^{24 j}-1$ is divisible by (2), and since $1001=41 \cdot 24+17$, the remainder of the second division is identical to the remainder of the division $\left(x^{17}-1\right)$ : $\mathrm{d}\left(x^{2}\right)$. This, using the usual division scheme, is $-2 x^{7}-x^{5}-2 x^{3}-1$.

László Szeidl (Budapest, Apáczai Csere J. Practical Grammar IV. Class)