# Distinct-degree factorization in finite fields

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.

-
What do you mean with "is this random"? The result of a diviosn should be deterministic ... –  Hagen von Eitzen Sep 3 '12 at 17:11
I wonder because the dividend is monoic. –  joachim Sep 3 '12 at 17:12
Doesn't mak much of a difference, as in $\mathbb Z_p$ all non-zero elements are invertible. $2x^9:x^4+x^3+x^2+2x+1=2x^5+x^4+x^2+x$ remainder $2x$ –  Hagen von Eitzen Sep 3 '12 at 17:21
Products of monic polynomials will again be monic, as (therefore) will quotients of monic polynomials (in such cases that the quotient is a polynomial at all). –  Cameron Buie Sep 3 '12 at 17:23
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.