# Polynomial division in $\Bbb Z/n\Bbb Z$

So, I know how polynomial division works in principle, but I have currently no Idea what is asked here:

We have to divide two polynomials: f = $4t^4-2t^3-3$ and g = $2t^2-3$ but in the polynomial ring $F_{p}[t]$ with p prime. (F = $\mathbb{Z/pZ}$).

So how does the algorithm for polynomial division change now?

• It's the same algorithm, except that all multiplication and subtraction is done within $\Bbb F_p$. So, for example, if $p = 5$, we would have $2 \cdot 4 = 3$. – Ben Grossmann Nov 22 '16 at 19:02
• Is the coefficient ring the integers mod $p$ or the integers mod $n?\$ You wrote $\,F_p$ with $F = \Bbb Z/n\Bbb Z,\,$ which is probably not what you intended. – Bill Dubuque Nov 22 '16 at 19:28
• Yes, I will change it, its mod p. – JonDoeMaths Nov 22 '16 at 19:38

The algorithm does not change, because the polynomial ring $K[t]$ is Euclidean for an arbitrary field $K$, but of course the result can be different. For $p=2$ for example, the two polynomials are just $f(x)=-3=1$ and $g(x)=-3=1$, so we divide $1$ by $1$, rather trivially. For $p=3$ we have $$\frac{f(x)}{g(x)}=\frac{t^4+t^3}{2t^2}=2t^2+2t.$$

Here is the layout of the division of $f(t)$ by $g(t)$ in $\mathbf F_5$: \begin{alignat}{6} &&&\rlap{2t^2-t-2}\\ &\rlap{\quad——————————}\\ 2t^2-3~&\Big(~& 4t^4&{}-2t^3&&&{}-3\\ &&-4t^4&&+t^2\\ &\rlap{\quad——————————}\\ &&&-2t^3&+t^2&&{}-3\\ &&&\phantom{{}-{}}2t^3&&+2t\\ &&\rlap{\quad———————}\\ &&&&t^2&+2t&-3\\ &&&&-t^2&\phantom{2}-t&\\ &&&\rlap{\qquad\enspace——————}\\ &&&&&\phantom{{}+2}t&-3 \end{alignat}

The high-school polynomial division algorithm works over any commutative coefficient ring, as long as the divisor $g$ has invertible leading coefficient. Then the leading term of $g$ always divides any monomial of higher degree, thus the high-school division algorithm works to kill all higher degree terms in the dividend, leaving a remainder of degree smaller than $\,\deg g$.

Alternatively we can reduce to the case where the divisor $\,g\,$ is monic (lead coef $= 1)$ as follows. Make the divisior $g$ monic by dividing it by its lead coef $c,\,$ then divide by the monic $\,g/c\,$ yielding $\, f = q(g/c)+ r = (q/c) g + r\,$ as desired, after moving the division by $\,c\,$ into the quotient.

The division algorithm generally fails if the lead coef of $\,g\,$ is not invertible, e.g. $\: x = 2x\:q + r\:$ has no solution for $\:r\in \mathbb Z,\ q\in \mathbb Z[x],\:$ since evaluating at $\:x=0\:$ $\Rightarrow$ $\:r=0,\:$ evaluating at $\:x=1\:$ $\Rightarrow$ $\:2\:|\:1\:$ in $\mathbb Z,\,$ contradiction. Notice that the same proof works in any coefficient ring $\:R\:$ in which $2$ is not invertible. Conversely, if $2$ is invertible in $\:R,$ say $\:2u = 1\:$ for $\:u\in R,\:$ then division is possible: $\: x = 2x\cdot u + 0.$

However, we can generalize the division algorithm to the non-monic case as follows.

Theorem (nonmonic Polynomial Division Algorithm) $\$ Let $\,0\neq F,G\in A[x]\,$ be polynomials over a commutative ring $A,$ with $\,a\,$ = lead coef of $\,F,\,$ and $\, i \ge \max\{0,\,1+\deg G-\deg F\}.\,$ Then
$\qquad\qquad \phantom{1^{1^{1^{1^{1^{1}}}}}}a^{i} G\, =\, Q F + R\ \ {\rm for\ some}\ \ Q,R\in A[x],\ \deg R < \deg F$

Proof $\$ Hint: use induction on $\,\deg G.\,$ See this answer for a full proof.