How to calculate the quotient and the remainder?

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?

• Your argument is totally valid. You just have to ask yourself what does $a/b$ means in $\mathbb{Z}_5$. For instance, $2/9=2\cdot 9^{-1}=2 \cdot 4^{-1} = 2\cdot 4 = 8 = 3$
– J.F
Commented Jan 19, 2019 at 17:53
• Note: I had misread $x^3$ as $x^2$. That is now fixed in my answer. Commented Jan 20, 2019 at 15:36

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.

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

$$\!\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).