# Polynomial long division modulo 7,

I need to determine the quotient and remainder using polynomial long division in $Z_7[x]$. I'm not sure how to tackle it with the polynomials given, and I'm growing frustrated by it.

I need to divide $f(x) = 5x^4 + 3x^3 + 1$ by $g(x)=3x^2 + 2x + 1$. This seems easy enough using normal long division but I'm unable to solve it in $Z_7[x]$. Please see the following:

https://i.imgur.com/IhJwmu4.jpg

The specific problem I'm dealing with is $\frac{5x^4}{3x^2}$. Obviously this answer is $\frac{5}{3}x^2$. Under $\mod 7$ we can simplify this to $x^2$. However, now we're stuck with $2x^4$, which we can't possibly eliminate as $2 / 3 \mod 7 = 0$.

I tried solving this by ignoring mod up until the very last moment, but this doesn't yield correct results. (It should be $4x^2+3x+6$ and $6x+2$ for the quotient and remainder, respectively.)

I haven't found examples which deal with this problem; can anybody help me?

• Hint: Try the first step doing $f(x)-4x^2g(x)$ and see what happens – Carlos Laguillo Mar 18 '15 at 9:54
• mind=blown. Thank you so much! – Martijn Mar 18 '15 at 10:05
• HINT: modulo $7$ you have $3 \cdot 5 =1$, so $3^{-1}=5$, and $5 \cdot 3^{-1} = 5 \cdot 5 = 25=4$. – Crostul Mar 18 '15 at 10:15

Scale $\,g\,$ by $\,3^{-1}\equiv -2\pmod 7\,$ to get a $\,\color{#c00}{\bar g = (-2) g}\,$ that is monic (leading coef $=1).$
Then divide by the monic $\,\bar g\,$ to get $\, f = q\, \color{#c00}{\bar g} + r = (\color{#c00}{-2}\,q)\,\color{#c00}g + r,\$ as desired.