[proofplan] We prove existence by strong induction on $\deg(f)$ and uniqueness by a standard cancellation argument. Existence: if $\deg(f) < \deg(g)$ we take the immediate decomposition $q = 0$, $r = f$. Otherwise we subtract off the leading term of $f$ using the polynomial $ab^{-1} X^{m-n} g$, where $a$ and $b$ are the leading coefficients of $f$ and $g$. This reduction requires $b$ to be a unit (so that $ab^{-1}$ exists in $R$), and produces a polynomial $f_1$ of strictly smaller degree, to which the inductive hypothesis applies. Uniqueness: if two pairs $(q, r)$ and $(q', r')$ both satisfy the division identity, then $(q - q')g = r' - r$, and the degree bound on the remainders forces $q = q'$ (using again that the leading coefficient of $g$ is a unit, so it is not a zero-divisor). [/proofplan] [step:Set up the induction and adopt the convention for the zero polynomial] We adopt the convention $\deg(0) = -\infty$, so that $\deg(r) < \deg(g)$ is satisfied by $r = 0$ regardless of $\deg(g)$, and the identity $\deg(fg) = \deg(f) + \deg(g)$ holds whenever $g \neq 0$ has unit leading coefficient (see below). We prove existence by strong induction on $\deg(f)$, for $f$ ranging over $R[X]$ and $g \in R[X]$ fixed with unit leading coefficient. The inductive hypothesis at degree $m$ is: for every polynomial $\tilde{f} \in R[X]$ with $\deg(\tilde{f}) < m$, there exist $\tilde{q}, \tilde{r} \in R[X]$ with $\tilde{f} = g\tilde{q} + \tilde{r}$ and $\deg(\tilde{r}) < \deg(g)$. [/step] [step:Handle the base case where $\deg(f) < \deg(g)$] Suppose $\deg(f) < \deg(g)$. Take $q = 0$ and $r = f$. Then \begin{align*} f &= g \cdot 0 + f = gq + r, \qquad \deg(r) = \deg(f) < \deg(g). \end{align*} This disposes of all $f$ with degree below $\deg(g)$, including in particular $f = 0$ (since $\deg(0) = -\infty < \deg(g)$). [/step] [step:Reduce the degree by subtracting a multiple of $g$] Suppose $\deg(f) = m \geq n = \deg(g)$, so we are in the inductive step. Write \begin{align*} f(X) &= a X^m + \text{(lower-degree terms)}, \qquad g(X) = b X^n + \text{(lower-degree terms)}, \end{align*} with $a \neq 0$ the leading coefficient of $f$ and $b$ the leading coefficient of $g$. By hypothesis, $b \in R^\times$, so $b^{-1} \in R$ exists. Define \begin{align*} f_1(X) &:= f(X) - a b^{-1} X^{m-n} g(X) \in R[X]. \end{align*} We claim $\deg(f_1) < m$. The leading term of $a b^{-1} X^{m-n} g(X)$ is $a b^{-1} X^{m-n} \cdot b X^n = a X^m$, which exactly cancels the leading $a X^m$ of $f$. Therefore the coefficient of $X^m$ in $f_1$ is zero, and $\deg(f_1) \leq m - 1 < m$. [guided] We are reducing the degree of $f$ by subtracting a carefully chosen multiple of $g$. The choice of the multiplier $a b^{-1} X^{m-n}$ is dictated by what is needed to cancel the leading term of $f$: - We want the leading term of $(\text{multiplier}) \cdot g$ to equal $a X^m$. - $g$ has leading term $b X^n$, so the multiplier must produce a leading term $a b^{-1} X^{m-n}$ when multiplied by $b X^n$. Why do we need $b$ to be a unit? Because we need to divide by $b$: the multiplier is $a b^{-1} X^{m-n}$, which only makes sense in $R[X]$ if $b^{-1} \in R$. Without this, we could not reduce the degree — this is why the hypothesis "leading coefficient of $g$ is a unit" is essential. (Over a field, every nonzero element is a unit, so any $g \neq 0$ works.) The polynomial $f_1 := f - a b^{-1} X^{m-n} g$ then has its $X^m$-coefficient equal to zero, so $\deg(f_1) \leq m - 1$, strictly less than $\deg(f) = m$. This is the degree-reducing step that feeds the induction. [/guided] [/step] [step:Invoke the inductive hypothesis on $f_1$] Since $\deg(f_1) < m = \deg(f)$, the inductive hypothesis applies to $f_1$: there exist $q_1, r \in R[X]$ with \begin{align*} f_1 &= g q_1 + r, \qquad \deg(r) < \deg(g). \end{align*} Substituting the definition of $f_1$: \begin{align*} f - a b^{-1} X^{m-n} g &= g q_1 + r, \\ f &= g\!\left(q_1 + a b^{-1} X^{m-n}\right) + r. \end{align*} Setting $q := q_1 + a b^{-1} X^{m-n} \in R[X]$, we have $f = gq + r$ with $\deg(r) < \deg(g)$. This completes the inductive step and establishes existence. [/step] [step:Prove uniqueness via degree comparison] Suppose $f = gq + r = gq' + r'$ with $\deg(r), \deg(r') < \deg(g)$. Rearranging, \begin{align*} g(q - q') &= r' - r. \end{align*} We show $q - q' = 0$. Suppose for contradiction that $q - q' \neq 0$. Since the leading coefficient $b$ of $g$ is a unit (in particular, $b \neq 0$ and $b$ is not a zero-divisor), the leading term of $g(q - q')$ is $b \cdot (\text{leading coefficient of } q - q') \cdot X^{\deg(g) + \deg(q-q')}$, with the leading coefficient nonzero since $b$ is not a zero-divisor. Therefore \begin{align*} \deg(g(q - q')) &= \deg(g) + \deg(q - q') \geq \deg(g). \end{align*} On the other hand, \begin{align*} \deg(r' - r) &\leq \max(\deg(r'), \deg(r)) < \deg(g). \end{align*} This contradicts $g(q - q') = r' - r$. Therefore $q - q' = 0$, so $q = q'$, and consequently $r = r'$. [guided] The uniqueness argument rests on a degree inequality. If two decompositions $f = gq + r = gq' + r'$ exist, subtracting gives \begin{align*} g(q - q') &= r' - r. \end{align*} The right side has degree strictly less than $\deg(g)$ (being a difference of polynomials each with that property, and the degree of a difference does not exceed the maximum degree of the summands). The left side, if $q \neq q'$, has degree at least $\deg(g)$. To see why the leading coefficient does not vanish — which would allow the product's degree to collapse — we use that $b$, the leading coefficient of $g$, is a unit. If the leading coefficient of $q - q'$ is $c \neq 0$, then the leading coefficient of $g(q - q')$ is $bc$, and $bc = 0$ would force $c = b^{-1} \cdot bc = b^{-1} \cdot 0 = 0$, contradicting $c \neq 0$. Thus $bc \neq 0$ and $\deg(g(q - q')) = \deg(g) + \deg(q - q') \geq \deg(g)$. We have a polynomial of degree $\geq \deg(g)$ equal to a polynomial of degree $< \deg(g)$, which is impossible unless both sides are zero. Hence $q - q' = 0$ and $r' - r = 0$. Why does this argument need $b$ to be a unit rather than merely nonzero? In a ring with zero-divisors (e.g., $R = \mathbb{Z}/6\mathbb{Z}$ with $b = 2$, $c = 3$), the product of leading coefficients could vanish and the degree of a product could drop. The unit hypothesis on $b$ prevents this: units are never zero-divisors in a nonzero ring. So both existence (we needed to invert $b$) and uniqueness (we needed $b$ not to be a zero-divisor) require the unit hypothesis. [/guided] [/step] [step:Assemble the existence and uniqueness conclusions] The induction of the preceding steps produces, for any $f \in R[X]$, a pair $(q, r) \in R[X] \times R[X]$ with $f = gq + r$ and $\deg(r) < \deg(g)$. The uniqueness step shows that any two such pairs must coincide. Therefore there exist unique $q, r \in R[X]$ with $\deg(r) < \deg(g)$ and $f = gq + r$, completing the proof. [/step]