Why polynomial division algorithm works for $x-a$ or any monic polynomial? 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.
 A: 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  generally fails if $\,{a}\,$ is not invertible
e.g. $\rm\: x = ax\:q + r,\  \color{#c00}{a\nmid 1}\,$ has no solution  since evaluating at $\rm\:x=0\:$ $\Rightarrow$ $\rm\:r=0,\:$ then eval at $\rm\:x=1\:$ $\Rightarrow$ $\rm\,1 = aq\,\Rightarrow\,\color{#c00}{a\mid 1\Rightarrow\!\Leftarrow}\,$  Conversely, if $\rm\,a\,$ is a unit, then $\rm\,ab = 1$ for some $\rm\,b\,$ so the division is possible: $\rm\: x = ax\cdot b + 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}{\bf +}$ rest $ $ terms:
$\begin{array}{lrl}
\ G = b x^{k+j\!}\color{#c00}{\bf +}  g,\ \deg g<k\!+\!j\!\!\!\!\!\! &\Rightarrow\quad aG\!\!\!\! &=\,abx^{k+j}+ag\\ 
\ F = a x^k\color{#c00}{\bf +}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.$
A: 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).$ 
