11
$\begingroup$

In Theorem 5.2.3 in these notes, it is said that

Since $x − a$ has leading coefficient $1$, which is a unit, we may use the Division Algorithm...

Why is this true? I thought that the Division Algorithm is only guaranteed to work in Euclidean domains not any integral domain.

Thanks.

$\endgroup$
5
  • $\begingroup$ (x-a) clearly devides any linear polynomial. Try to prove the statement more generally using induction on the degree of the polynomial. The key point is that the coefficient of the polynomial you divide by is 1. This allows you to get the leading coefficient of any other polynomial, when you divide by (x-a). $\endgroup$ – Rankeya Mar 3 '12 at 17:56
  • $\begingroup$ @Dominic: We are looking at polynomials with coefficients in a certain ring. Imagine carrying out the usual process of polynomial division of $f(x)$ by $g(x)$, where the lead coefficient of $g(x)$ is $1$, or more generally a unit. There will never be a need for coefficients outside the ring. $\endgroup$ – André Nicolas Mar 3 '12 at 17:56
  • 2
    $\begingroup$ This statement holds not just for (x-a) but for more general polynomials whose leading coefficient is 1, or for that matter any unit in the ring. $\endgroup$ – Rankeya Mar 3 '12 at 17:58
  • $\begingroup$ Dear Dominic: Rankeya made (I think) the key comment (see his/her second comment). In the case of a division by $x-a$, it suffices to observe that a polynomial $x-a$ divides $f(x)-f(a)$ for any polynomial (or even any monomial) $f(x)$. $\endgroup$ – Pierre-Yves Gaillard Mar 3 '12 at 18:09
  • 1
    $\begingroup$ For polynomials over any ring with unity (commutative or not), the division algorithm will work for any polynomial with leading coefficient a unit as the divisor. The usual proof works. $\endgroup$ – Arturo Magidin Mar 3 '12 at 21:47
19
$\begingroup$

For polynomials over any commutative coefficient ring, the high-school polynomial long division algorithm works to divide with remainder by any monic polynomial, i.e any polynomial $\,F\,$ whose leading coefficient $\,a=1$ (or a unit = invertible), since this implies that the leading term of $\,F\,$ divides all monomials $\,x^k\,$ so the division algorithm works to kill all higher degree monomials in the dividend, leaving a remainder of degree $ < \deg F,\,$ i.e. as below we scale $F$ by $\,\color{#c00}{(b/a)x^k}$ so its leading term equals the leading term of $G$, so they cancel upon subtraction, leaving a result of lower degree than $G$. By induction (recursion) we can iterate this till we obtain a remainder with smaller degree than the dividend $F$.

$$\begin{align} G - \color{#c00}{\frac{b}a x^{\large j}} F \,\ = \,\ (\overbrace{b x^{\large k+j} + g}^{\large {\rm dividend}\ G})\ -\ &\color{#c00}{\frac{b}a x^{\large j}} (\overbrace{a x^{\large k} + f}^{\large {\rm divisor}\ F})\ =\ \overbrace{\color{#0a0}{g-\frac{b}a x^j f}}^{\large {\rm deg}\ <\ k+j}\\[.4em] \Longrightarrow\ \ \ \dfrac{b x^{\large k+j}+g}{ax^{\large k}+f}\, =\ &\color{#c00}{\frac{b}a x^{\large j}}\ \ +\ \underbrace{\dfrac{\color{#0a0}{g-\frac{b}a x^{\large j} f}}{ax^k + f}}_{\large\rm recurse\ on\ this}\end{align}\qquad\qquad$$

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

However, we can generalize the division algorithm to the non-monic case by scaling the above division step by $\,a,\,$ i.e. using $\,\color{#c00}aG-\color{#c00}{bx^j} F,\,$ which inductively yields the following

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 $\,\ $ If $\ \deg G < \deg F\,$ then let $\, Q = 0 ,\ R = a^i G.\, $ Else we induct on $\,\deg G.\,$ Let $\, k = \deg F,\,$ so $\,\deg G = k+j\,$ for $\, j \geq 0.\,$ Splitting $\,G,F\,$ into $ $ lead $\color{#c00}+$ rest $ $ terms:

$\begin{array}{lrl} \ G = b x^{k+j\!}\color{#c00} + g,\ \deg g<k\!+\!j\!\!\!\!\!\! &\Rightarrow\quad aG\!\!\!\! &=\,abx^{k+j}+ag\\ \ F = a x^k\color{#c00}+f,\quad \deg f \!< k & bx^jF\!\!\!\! &=\, abx^{k+j}+bx^jf\\ \ {\rm with}\ \,a,b\neq 0\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! & aG-bx^jF\!\!\!\! &=\, ag-bx^jf\ \ {\rm has\ \ deg} < k\!+\!j \end{array}$

$\begin{array}{lrl}{\rm Therefore,\, by\ \ induction}\!\! &a^j(aG-bx^jF) =&\!\!\! Q F + R\ \ {\rm for}\ \ Q,R\in A[x], \ \deg R < k\\ &\Rightarrow\quad a^{j+1} G\, =&\!\!\! \bar QF + R\ \ {\rm for}\ \ \bar Q = Q\!+b(ax)^j\end{array}$

Remark $\ $ Alternatively, if localizations are known, we can divide by the monic $\,a^{-1} F\in A[a^{-1}][x]\,$ then pullback the result to $\,A[x].$

Or, as in the AC-method, we can conjugate to the monic case: scaling $\,F\,$ by $\,a^{k-1}\,$ for $\,k = {\rm deg} F,\,$ we can rewrite $\,F\,$ as a monic polynomial in $\,X = ax,\,$ and similarly we can scale $\,G\,$ by $\,a^i\,$ to make it a polynomial in $\,X.\,$ Then we divide $\,G(X)\,$ by the monic $\,F(X),\,$ and finally replace $\,X\,$ by $\,ax.$

$\endgroup$
6
  • $\begingroup$ The localization method can fail if $a$ is nilpotent. $\endgroup$ – user26857 Jun 23 '17 at 17:02
  • 1
    $\begingroup$ @user26857 Not if you do it generically. $\endgroup$ – Bill Dubuque Jun 23 '17 at 17:51
  • $\begingroup$ The localization argument in the "Remark" only shows that there exists some $j$ such that $a^j G = QF + R$, but not that every $j \geq \max \left\{ 0, 1 + \deg G - \deg F \right\}$ works. $\endgroup$ – darij grinberg Jul 18 '19 at 7:31
  • $\begingroup$ @darij Not true. We can easily get the degree bound that way too. Hint: as per my prior comment, do it for $\,a\,$ an indeterminate, and check that each step in the division algorithm increases the power of $\,a\,$ in the denominators by at most $1$, and there are at most $\,1 + \deg G - \deg F\,$ steps. $\endgroup$ – Bill Dubuque Jul 18 '19 at 13:28
  • $\begingroup$ Okay, but at that point you're looking inside the proof rather than just applying the result. $\endgroup$ – darij grinberg Jul 18 '19 at 13:54
2
$\begingroup$

That's the point really. It isn't guaranteed to work for EVERY polynomial in the ring $R[x]$ you are dealing with, but it will work for some polynomials, and the polynomial $x-a$ is never a problem. A polynomial of the form $ax +b$ with $a$ a non-unit of $R$ would cause a problem. To deal explicitly with $x-a$ and a polynomial $p(x) \in R[x]$, we can work by induction on the degree of $p(x).$ Suppose that this is $n > 1$ and we can write polynomials of degree $n-1$ in the expected form (note that when $p(x) = cx+d$ has degree $1,$ we have $cx+d = c(x-a) + (ac+d)$, which starts the induction). We can certainly write $p(x) = xq(x) + r$ for some polynomial $q(x) \in R[x]$ of degree $n-1$ and some $r \in R.$ By assumption, we may write $q(x) = (x-a)s(x) + t$ where $s(x)\in R[x]$ has degree $n-1$ and $t \in R$. For the sake of space I omit some steps, but you can then see that $p(x) = (x-a) [xs(x) + t ] + (at+r).$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.