description/proof of that over field, polynomial and nonzero polynomial divisor have unique quotient and remainder
Topics
About: ring
The table of contents of this article
- Starting Context
- Target Context
- Orientation
- Main Body
- 1: Structured Description
- 2: Natural Language Description
- 3: Proof
- 4: Note
Starting Context
- The reader knows a definition of field.
- The reader knows a definition of polynomials ring over commutative ring.
Target Context
- The reader will have a description and a proof of the proposition that over any field, any polynomial and any nonzero polynomial divisor have the unique quotient and remainder.
Orientation
There is a list of definitions discussed so far in this site.
There is a list of propositions discussed so far in this site.
Main Body
1: Structured Description
Here is the rules of Structured Description.
Entities:
\(F\): \(\in \{\text{ the fields }\}\)
\(F [x]\): \(= \text{ the polynomials ring over } F\)
\(p' (x)\): \(\in F [x]\)
\(p (x)\): \(\in F [x]\), \(\neq 0\)
//
Statements:
\(!\exists q (x), r (x) \in F [x] (deg (r (x)) \lt deg (p (x)) \land p' (x) = p (x) q (x) + r (x))\), where \(!\exists\) denotes unique existence
//
2: Natural Language Description
For any field, \(F\), and the polynomials ring over \(F\), \(F [x]\), any polynomial, \(p' (x) \in F [x]\), and any nonzero polynomial, \(p (x) \in F [x]\) have the unique polynomials, \(q (x), r (x) \in F [x]\), such that \(deg (r (x)) \lt deg (p (x))\) and \(p' (x) = p (x) q (x) + r (x)\).
3: Proof
Whole Strategy: Step 1: think of the case, \(deg (p' (x)) \lt deg (p (x))\), and conclude the proposition for that case; Step 2: think of the case, \(deg (p (x)) \le deg (p' (x))\) and conclude the proposition for that case.
In fact, the logics for the 2 cases are not essentially different, but the divisions of the cases ease our notations.
Let us suppose that \(p (x) = p_m x^m + ... + p_0\) with \(p_m \neq 0\).
Step 1:
Let us suppose that \(deg (p' (x)) \lt deg (p (x))\).
\(q (x) = 0\) is inevitable, because if \(q (x)\) had a term, \(q_l x^l\), with \(q_l \neq 0\), \(p (x) q (x)\) would have the term, \(p_m q_l x^{m + l}\), which would be degree equal to or larger than \(m\), but as the degree of \(p' (x)\) was smaller than \(m\), \(p_m q_l x^{m + l}\) would have to be eliminated by \(r (x)\), but that would be impossible because \(r (x)\) could have only smaller-than-\(m\)-degree terms.
Then, inevitably, \(p' (x) = p (x) 0 + r (x) = r (x)\).
So, \(q (x) = 0, r (x) = p' (x)\) is the unique solution.
Step 2:
Let us suppose that \(deg (p (x)) \le deg (p' (x))\).
Step 2 Strategy: Step 2-1: suppose that \(p' (x), q (x), r (x)\) have certain coefficients; Step 2-2: expand \(p (x) q (x) + r (x)\) and group the monomials by degrees; Step 2-3: compare the coefficients of \(p' (x)\) and the coefficients of \(p (x) q (x) + r (x)\) and see that the coefficients of \(q (x)\) and \(r (x)\) are uniquely determined.
Step 2-1:
Let us suppose without loss of generality that \(p' (x) = p'_n x^n + ... + p'_0\), \(q (x) = q_l x^l + ... + q_0\), and \(r (x) = r_{m - 1} x^{m - 1} + ... + r_0\), with \(p'_n, q_l \neq 0\) but some leading coefficients of \(r (x)\) may be \(0\). The assumption is valid, because as \(deg (p (x)) \le deg (p' (x))\), \(p' (x) \neq 0\), and also \(q (x) \neq 0\), because \(p' (x) = p (x) 0 + r (x) = r (x)\) is impossible.
Step 2-2:
\(p (x) q (x) + r (x) = (p_m x^m + ... + p_0) (q_l x^l + ... + q_0) + (r_{m - 1} x^{m - 1} + ... + r_0) = p_m q_l x^{m + l} + (p_m q_{l - 1} + p_{m - 1} q_{l}) x^{m + l - 1} + ... + (p_m q_0 + p_{m - 1} q_1 + ... + p_{m - l} q_l) x^m + (p_{m - 1} q_0 + p_{m - 2} q_1 + ... + p_{m - 1 - l} q_l + r_{m - 1}) x^{m - 1} + ... + (p_0 q_0 + r_0)\). Note, of course, if \(l = 0\), \(q_{l - 1}\) does not really exist, if \(m = 0\), \(p_{m - 1}\) does not really exist, etc., but as such case divisions would rather bother you than help you, the notation is left like that, assuming that you will understand what it means: the impossible terms are meant be just nonexistent. The notations hereafter are likewise.
Step 2-3:
Inevitably, \(n = m + l\), and \(p'_n = p_m q_l\), which uniquely determines \(q_l = {p_m}^{-1} p'_n\).
If \(n = m\), \(q_l = q_0\), and \(q (x)\) has been uniquely determined.
Otherwise, \(m \le n - 1\), and we are going to look at \(p'_{n - 1}, ..., p'_m\) in that order.
For \(p'_{n - 1}\), inevitably, \(p'_{n - 1} = p_m q_{l - 1} + p_{m - 1} q_l\), which uniquely determines \(q_{l - 1} = {p_m}^{-1} (p'_{n - 1} - p_{m - 1} q_l)\): \(q_l\) has been already determined.
Let us suppose that we have looked at \(p'_{n - 1}, ..., p'_{n - (j - 1)}\) and have determined \(q_{l - 1}, ..., q_{l - (j - 1)}\), and let us look at \(p'_{n - j}\).
\(p'_{n - j} = p_m q_{l - j} + p_{m - 1} q_{l - j + 1} + ... + p_{m - j} q_l\). Inevitably, \(q_{l - j} = {p_m}^{-1} (p'_{n - j} - p_{m - 1} q_{l - j + 1} - ... - p_{m - j} q_l)\).
Note that the last \(p'_m\) corresponds to \(q_0\), because \(n - j = m\) implies that \(l - j = l + m - n = 0\).
After all, \(q_l, ..., q_0\) have been uniquely determined.
If \(m = 0\), inevitably, \(r (x) = 0\).
Otherwise, \(0 \le m - 1\), and we are going to look at \(p'_{m - 1}, ..., p'_0\) in that order.
For \(p'_{m - 1}\), inevitably, \(p'_{m - 1} = p_{m - 1} q_0 + p_{m - 2} q_1 + ... + p_{m - 1 - l} q_l + r_{m - 1}\), and inevitably, \(r_{m - 1} = p'_{m - 1} - p_{m - 1} q_0 - p_{m - 2} q_1 - ... - p_{m - 1 - l} q_l\), which is uniquely determined.
Let us suppose that we have looked at \(p'_{m - 1}, ..., p'_{m - (j - 1)}\) and have determined \(r_{m - 1}, ..., r_{m - (j - 1)}\), and let us look at \(p'_{m - j}\).
Inevitably, \(p'_{m - j} = p_{m - j} q_0 + p_{m - (j + 1)} q_1 + ... + p_{m - (j + l)} q_l + r_{m - j}\), which uniquely determines \(r_{m - j} = p'_{m - j} - p_{m - j} q_0 - p_{m - (j + 1)} q_1 - ... - p_{m - (j + l)} q_l\).
Note that the last \(p'_0\) corresponds to \(r_0\).
After all, \(r_{m - 1}, ..., r_0\) have been uniquely determined. Some or all of them can be \(0\).
\(p' (x) = p (x) q (x) + r (x)\) indeed holds, because all the coefficients of the left hand side equal the corresponding coefficients of the right hand side.
4: Note
As an immediate corollary, when \(p' (s) = 0\), \(p' (x) = (x - s) q (x)\), which means that \(p' (x)\) can be divided by \(x - s\). That is because while \(p' (x) = (x - s) q (x) + r (x)\), \(r (x)\) is degree \(0\), so, \(r (x) = r\), and \(p' (s) = (s - s) q (s) + r = r = 0\).
