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

|cite|improve this question
$\endgroup$
  • $\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
11
$\begingroup$

For polynomials over any coefficient ring, the high-school polynomial long division algorithm works 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.$

The division algorithm 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, we can generalize the division algorithm to the non-monic case 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 $\,\ $ 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'\\ \qquad\ 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.$

|cite|improve this answer
$\endgroup$
  • $\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
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).$

|cite|improve this answer
$\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.