How to calculate the quotient and the remainder?

Question

Let g(x)=3x+2 and $f(x)=x^3+2x+4$ in $F=\mathbb Z_5[x]$.Determine the quotient and the remainder upon dividing $f(x)$ by $g(x)$.

Division Algorithm says that, for any field $F$ and for $f(x),g(x)(\neq 0)\in F[x]$$~\exists$ unique $q(x),r(x)\in F[x]$ such that $f(x)=g(x)q(x)+r(x)$ where $\deg r(x)<\deg g(x)$ or $r(x)=0.$

On simple division of $f(x)$ by $g(x)$,I got $q(x)=\frac{x^2}{3}-\frac{2}{9}x+\frac{22}{27}$ and $r(x)=\frac{64}{27}$.But neither $q(x)\in \mathbb Z_5[x]$ nor $r(x)=\frac{64}{27}\in \mathbb Z_5[x]$

Please tell me where i'm wrong?

Answer 1

Hint

What is $1/3$ in $\mathbb Z_5$? It is the multiplicative inverse of $3$, which is $2$ as in $\mathbb Z_5$, $2\cdot 3= 5+1=1$.

Do the same for $1/9$. In $\mathbb Z_5$, $9=2\cdot 5-1=-1$. And as $-1 \cdot (-1)=1$ you have $1/9= -1=4$.

You can follow on like that to find all the inverses involved in your polynomial division to find the result.

Answer 2

$\!\bmod 5\!:\ 1/3\equiv 6/3\equiv 2\,$ so you can clear denonimators. But it is much easier done as below.

Tip $ $ Divide fraction-free by scaling the divisor to be monic (lead coef $=1)$ then adjust the result.

Here, long divide $\,f\,$ by $\,2g\equiv x\!-\!1\,$ then double its quotient $\,\color{#C00}{q'=q/2}\,$ to get $\,\color{#0a0}q$

$$\begin{align}\bmod 5\!:\ \ \ \ f\, &\equiv\, \ \ \overbrace{(\color{#c00}{x^2+x-\!2})\,\ (x-1)}^{\Large \color{#c00}{q/2}\,\ \times\,\ 2g\ \,} + 2\\[.2em] &\equiv\, \underbrace{(\color{#0a0}{2x^2\!+\!2x\!+\!1})(3x+2)}_{\Large\ \color{#0a0}q\,\ \times\,\ g^{\phantom{:}}} + 2\end{align}\qquad\qquad$$

adjusting $\,\color{#0a0}q \equiv 2(\color{#c00}{q/2})$ $\equiv 2(\color{#c00}{x^2\!+\!x\!-\!2}) \equiv \color{#0a0}{2x^2\!+2x\!+\!1},\ $ i.e. $\ f = \color{#c00}{q'} (2g)+r = \color{#0a0}{2q'}g + r$

Remark $ $ We can view this method as conjugating non-monic division into monic division (similar to how the AC-method reduces factorization of non-monic to monic polynomials by conjugation, i.e. scale the problem to the monic case, then invert the scaling at the end, i.e. $\,\cal F f\, = a^{-1}\cal F\, a\,f,\,$ where $\cal F$ is the factorization algorithm).

Answer 3

A variant with Horner's scheme:

Note first that in $\mathbf F_5[X]$, one has $\; g(X)=-2X+2=-2(X-1)$, so we'll divide first by $X-1$ via Horner's scheme: \begin{array}{r|rrr|r} &1&0&2&4 \\ &\downarrow&1&1 &3\\\hline \times 1\quad&1&1&3 & 2 \end{array} Thus $\;X^3+2X+4 =(X-1)(X^2+X+3)+2$. Now write $1=-2\cdot 2$. The previous equality can be rewritten as $$f(X)=-2(X-1)\cdot 2(X^2+X+3)+2=g(X)(\color{red}{2X^2+2X+1})+\color{lime}2.$$