1
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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$. $\endgroup$ – Ben Grossmann Nov 22 '16 at 19:02
  • $\begingroup$ 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. $\endgroup$ – Bill Dubuque Nov 22 '16 at 19:28
  • $\begingroup$ Yes, I will change it, its mod p. $\endgroup$ – JonDoeMaths Nov 22 '16 at 19:38
1
$\begingroup$

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. $$

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

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}

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.