# Extension of the factor theorem

## Motivation

If you don't care the least bit about motivation, scroll down.

The following is a standard result in a first algebra course:

Factor Theorem. Let $R$ be an integral domain and $p\in R[X]$ with a root $a \in R$. Then there exists a unique $q \in R[X]$ such that $p(x) = (x-a)q(x)$.

From this we deduce:

Extended Factor Theorem. Let $R$ be an integral domain, $S \subseteq R$ a subring and $p \in S[X]$ a polynomial with roots $a_1,\dotsc,a_j \in R$ such that $d(x) = \prod_{i=1}^j (x-a_i) \in S[X]$ then there is a unique $q \in S[X]$ such that $p = dq$.

By repeated application of the factor theorem it follows that there is a unique $q \in R[X]$ such that $p = dq$. Next we appeal to the theorem about division with remainder in $S[X]$: there are unique polynomials $q^*,r^* \in S[X]$, $\deg r^* < \deg d$ such that $p = dq^* + r^*$. Since $S[X] \subseteq R[X]$ we must have $r^*=0$ and $q^*=q$. Thus $q \in S[X]$ as desired. $\quad\blacksquare$

The proof is nice enough as is, but it would be much nicer if we could avoid appealing to what is essentially polynomial long division and have that $q \in S[X]$ just from the fact that $p,d \in S[X]$.

## The Question

Speculation. If $R$ is an integral domain, $S\subseteq R$ a subring, $p,d \in S[X]$ with $d$ monic and $q \in R[X]$ such that $p = dq$, does it follow that $q \in S[X]$?

-

Speculation. If $R$ is an integral domain and $S\subseteq R$ a subring, monic $d \in S[x]$ and $q \in R[x],\:$ does $\:dq\in S[x]\ \Rightarrow\ q \in S[x]$?

Hint: for $R$ any ring, the proof is an easy induction by examining leading coefficients, namely

$$dq\: =\: (x^k+\cdots+s_1 x+s_0)(r_n x^n+\cdots+r_1 x + r_0) \in S[x]\ \Rightarrow\ r_n \in S$$

For $\:\bar q = q-r_n x^n\:$ we have $\: d\:\bar q \in S[x]\:$ so $\:\bar q \in S[x]\:$ by induction on $\:\deg q,\:$ so $\:q\in S[x].\$ QED

Remark $\:$ Your Extended Factor theorem depends on $R$ being a domain, but your Factor Theorem does not - it is true for any ring $R$. The extension is false, e.g. $x$ has roots $0,0$ but $x^2\nmid x$ in $\mathbb Q[x]$. The fix is easy: either assume the roots are distinct, or else account for multiplicity of roots.

The domain hypothesis is crucial. In fact a ring $\rm\:D\:$ is a domain iff every polynomial $\rm\ f(x)\in D[x]\$ has at most $\rm\ deg\ f\$ roots in $\rm\:D\:.\:$ For a simple proof see this post, which constructively illustrates this in $\rm\ \mathbb Z/m\$ by showing that, given any $\rm\:f(x)\:$ with more roots than its degree, we can quickly compute a nontrivial factor of $\rm\:m\:$ via a simple $\rm\:gcd\:$ calculation. The quadratic case of this result is at the heart of many integer factorization algorithms, which attempt to factor $\rm\:m\:$ by searching for a nontrivial square root in $\rm\: \mathbb Z/m\:,\:$ e.g. a square root of $1$ that is not $\:\pm 1$.

-

Yes. Given any polynomials $p,d \in S[x]$ where the leading coefficient of $d$ is a unit ($d$ monic guarantees this), there exists some $q',r' \in S[x]$ such that $p=dq'+r'$ and either $r'=0$ or $\mathrm{deg}(r')<\mathrm{deg}(d)$ [Look up any text with a proof of the polynomial division algorithm and you'll find that the proof applies to this situation.]

Now suppose $p=dq$. Then $dq=dq'+r'$ so $d(q-q')=r'$ if $q \not= q'$, then the degree of the left hand side is at least $\mathrm{deg}(d)$ (contradiction). Therefore, $q=q'$ (and $r'=0$). Thus $q=q' \in S[x]$.

Note: I get the feeling that you wanted to avoid polynomial long division. But any proof of this fact is going to involve the division algorithm (either explicitly or implicitly). Why? The condition that must be placed on $d$ to make sure this statement holds is "the leading coefficient is invertible." So you're tinkering around with $d$'s polynomial structure and then asking about a divisibility property -- that's essentially going to force the division algorithm to appear.

Sketch of Division Algorithm Proof:

Let $p=p_nx^n+\cdots+p_0,d=ux^m+d_{m-1}x^{m-1}+\cdots+d_0 \in S[x]$. Assume $u$ is a unit.

Then either $n<m$ and so $p=0d+p$ (done), or $n \geq m$. In this case $p-p_nu^{-1}x^{n-m}d = (p_n-p_nu^{-1}u)x^n+O(x^{n-1})=O(x^{n-1})$. Assume by induction we've have $p'=dq'+r'$ ($r'=0$ or of degree less than $d$) for $p'$ of lower degree. Then $p-p_nu^{-1}x^{n-m}d=p'=dq'+r'$ so $p=(p_nu^{-1}x^{n-m}+q')d+r'$ (where $r'=0$ or is of degree less than $d$).

Notice that the operations keep us inside $S[x]$ since $u^{-1}\in S$ ($u$ is a unit).

-