# Division algorithm for polynomials in R[x], where R is a commutative ring with unity.

Is there a division algorithm for polynomials in R[x], where R is a commutative ring with unity?

All the algebra books I read mention division algorithm for polynomials in F[x], where F is a field. Since the leading coefficient of a non zero polynomial in R[x] is not necessarily invertible, I find it difficult to proceed the same way we do for polynomials in F[x]. Can I get some help?

• It does depend on the ring R. For instance you would require R[x] to be an Euclidean Domain, which would need R to be minimally an integral domain. – Chris C Feb 12 '17 at 5:15
• And yeah , for any such R , you need the polynomial to be monic, which is not required in a field. – Chirantan Chowdhury Feb 12 '17 at 8:34
• There do exist rings $R$ (even nice rings like $R = \mathbb R[y]$ and $R = \mathbb Z$) for which $R[x]$ does not have a division algorithm; i.e. is not a Euclidean domain. This can be proved, for example, by finding a non-principal ideal in $R[x]$. (Recall that Euclidean domains are necessarily principal ideal domains.) However, the usual proof for $F[x]$ does provide a division algorithm for dividing by monic polynomials (or, slightly more generally, those with unit leading coefficients) if $R$ is any commutative ring with 1. – Ravi Fernando Feb 14 '17 at 7:36

## 1 Answer

For polynomials over any commutative coefficient ring, the high-school polynomial long division algorithm shows how to divide with remainder by any monic polynomial, i.e any polynomial $\rm\:f\:$ whose leading coefficient $\rm\:c =1\:$ (or a unit), since $\rm\:f\:$ monic implies that the leading term of $\rm\:f\:$ divides all higher degree monomials $\rm\:x^k,\ k\ge n = deg\ f,\:$ so the division algorithm works to kill all higher degree terms in the dividend, leaving a remainder of degree $\rm < n = deg\ f.$

But this generally fails if $\rm\:f\:$ is not monic, e.g. $\rm\: x = 2x\:q + r\:$ has no solution for $\rm\:r\in \mathbb Z,\ q\in \mathbb Z[x],\:$ since evaluating at $\rm\:x=0\:$ $\Rightarrow$ $\rm\:r=0,\:$ evaluating at $\rm\:x=1\:$ $\Rightarrow$ $\:2\:|\:1\:$ in $\mathbb Z\:$ $\Rightarrow\!\Leftarrow\,$ Notice that the same proof works in any coefficient ring $\rm\:R\:$ in which $2$ is not a unit (invertible). Conversely, if $\,2\,$ is a unit in $\rm\:R,$ say $\rm\:2u = 1\:$ for $\rm\:u\in R,\:$ then division is possible: $\rm\: x = 2x\cdot u + 0.$

However, it is possible to divide with remainder by non-monic polynomials 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 $\$ See here for a few proofs.

• Thanks. Did you get this proof from Nathan Jacobson? – tony Feb 16 '17 at 3:28
• @Tony No, I wrote the proof from scratch (it is straightforward if you know the idea). – Bill Dubuque Feb 16 '17 at 3:55
• Mr. Dubuque, where could one find a reference for the non-monic version of the division algorithm? textbooks usually gives the monic version and even many of them only state the result when $A$ is a field. – Xam Jul 9 '17 at 18:35
• @Xam I don't recall at the moment, but the above comment seems to indicate it may appear in one of Jacobson's Algebra textbooks. In any case, I give a complete proof in the linked answer, so one can always refer to that. – Bill Dubuque Jul 9 '17 at 18:50
• @Xam, try Basic ALgebra 1 by Nathan Jacobson. You will find the proof in chapter 2.11 , page128 – tony Jul 29 '17 at 11:40