Polynomial long division with mod. Trouble with fractions. For example $4x^4 + x + 1$ divided by $3x + 1$ is $\frac{4x^3}{3} - \frac{4x^2}{9} + \frac{4x}{27} + \frac{23}{81}$ remainder $\frac{58}{81}$.
Now I want to do the same division mod $9$, but I can't because the denominators are not coprime to it.
Is there a way to get around this somehow or is the quotient/remainder not defined mod $9$?
 A: The polynomial division algorithm only works in general for polynomials with coefficients in a field. It will work for divisors whose leading coefficient is a unit for coefficients over an arbitrary commutative ring. $3$ is not a unit in the ring $\mathbb{Z}/9\mathbb{Z}$ of integers modulo $9$, so you can't expect the division algorithm to work for a divisor with leading coefficient $3$ when the coefficients are in $\mathbb{Z}/9\mathbb{Z}$. The quotient and remainder you are looking for in your example don't exist: there are no polynomials $q$ and $r$ over $\mathbb{Z}/9\mathbb{Z}$, such that $4x^4 + x + 1 = q\times(3x+1) + r$ and $\deg(r) = 0$.
A: It is easy to prove that the division is impossible if $\,3\,$ doesn't divide the lead coef of $\,f.\,$  
For  $\ f  \equiv  (3x\! +\! 1)q + r\pmod{\color{#c00}9},\ r\in \Bbb Z\,$ $\Rightarrow$   $\ f = (3x\!+\!1)q + r + \color{#c00}{9g}\ $ for $\,q,g\in \Bbb Z[x]\,$  therefore $\, {\rm mod}\ 3\!:\ f\equiv q+r\,$ has reduced degree $(\le \deg q),\,$ so the lead coef of $\,f\,$ is $\,\equiv 0$
The same idea works more generally to disprove certain nonmonic divisions.
Remark $ $ The division algorithm works for nonmonic divisors too if one scales the dividend by a (sufficiently large) power of the lead coeff of the divisor, see the nonmonic division algorithm. In your example this amounts to scaling the division by $3^4$ to make everything integral. Whether or not this proves useful depends on the context.
