How do I find the quotient of the division of $x^{1993}+x^2+1$ by $x^2+x+1$?

Question

I have an exercise where I need to find the quotient of the division of polynomial $f=x^{1993}+x^2+1$ by $g=x^2+x+1$. I know to do it the long way but I think there is a trick to do it fast. By the way, I know the remainder is $0$.

Answer 1

Since $(x-1)(x^2+x+1)=x^3-1$ you have $x^3\equiv 1 \bmod x^2+x+1$ whence $x^{1993}\equiv x$ and then it is trivial.

---

To expand: $f=X^{1993}+X^2+1=(X^{1993}-X)+(X^2+X+1)$

The first of these factors is $$X(X^{1992}-1)=X(X^3-1)(X^{1989}+X^{1986}+\dots +X^3+1)=$$$$=(X^2+X+1)(X^2-X)(X^{1989}+X^{1986}+\dots +X^3+1)$$ and dividing through by $(X^2+X+1)$ and multiplying through by $(X^2-X)$ gives a sum of pairs of terms of the form $X^{3n+2}-X^{3n+1}$ starting $X^{1991}-X^{1990}+X^{1988}-X^{1987}+\dots$

Answer 2

Just wrote $$X^{1993}+X^2+1=X^{1993}-X+X^2+X+1=X\left(X^{1992}-1\right)+X^2+X+1.$$

Since $$X^{1992}-1=(X^3-1)(X^{1989}+...+X^3+1)=(X-1)(X^2+X+1)(X^{1989}+...X^3+1),$$ we see that $X^{1993}+X^2+1$ is divisible by $X^2+X+1$.

The quotient it's $$X(X-1)(X^{1989}+...X^3+1)+1.$$