Distinct-degree factorization in finite fields

Question

In $\mathbb{Z}_3$

$$ x^9 : x^4+x^3+x^2+2x+1 = x^5+2x^4+2x^2+2x$$

with remainder of $x$.

In $\mathbb{Z}_7$

$$x^7 : x^4+5x^3+x+5 = x^3+2x^2+4x$$

with remainder of $x$.

Is this random? Or is there some kind of trick which I do not see to avoid polynomial long-divison by hand when computing the remainder of polynomials in finite fields of this form. Both calculations occured in example excerises for the calculation of distinct-degree factorization for polynomials in finite fields.

Answer 1

The fact that the dividend is a power of $x$ does not make the division substantially simpler.

It is analogous to long division of $10^n$ by some arbitrary smaller number, say with 5 digits (to correspond to your 4th degree divisor); you cannot just write down the answer in that case either.