My textbook states that $f(x)$ can always be written as $$f(x) = q(x)g(x) + r(x)$$ but it doesn't provide any proof of this and I cannot seem to find it anywhere.
And what does it actually say, that there always must exist some combination of $g(x), q(x) $ and $r(x)$ to satisfy the equation, or does it say that for any $g(x)$ there always must exist some combination of $r(x) , q(x) $ to satisfy the equation? I.e is there a solution for every $g(x)$ or is there a fixed amount of $g(x), q(x) , r(x)$ that satisfy it?
$\endgroup$ 14 Answers
$\begingroup$Suppose the polynomial $f(x)$ has degree $n$ and $g$ has degree $m\ge 1$
If $m\gt n$ then $f(x)=0\cdot g(x) +f(x)$ with $q(x)=0$ and $r(x)=f(x)$
What we are looking for is the degree of $r(x)$ being less than the degree of $g(x)$, so this works.
We treat this as a base case and assume that we have dealt with all cases in which deg$(f)\ge n-1$ and that $n\ge m$
Let the polynomials be $f(x)=a_nx^n+f_n(x)$ and $g(x)=b_mx^m+g_m(x)$ where $a_n, b_m \neq 0$ and deg$(f_n)\lt n$, deg$(g_m)\lt m$
Then we want to write $f(x)=\cfrac {a_n}{b_m}\cdot x^{n-m}g(x)+f_n(x)-\cfrac {a_n}{b_m}\cdot x^{n-m}g_m(x)$ so we need a context in which we can divide by $b_m$ - the coefficients are usually from a field or division ring to make this work. Here we are just dividing to get rid of the highest power of $x$.
The point is that the degree of $f_n(x)-\cfrac {a_n}{b_m}\cdot x^{n-m}g_m(x)$ is less than $n$ so we can write it as $q_n(x)g(x)+r_n(x)$ and we have $$f(x)=\left(\cfrac {a_n}{b_m}\cdot x^{n-m}+q_n(x)\right)g(x)+r_n(x)$$
As we required.
Now that is all a bit wordy and long for a simple division, but I hope it highlights the assumptions involved.
$\endgroup$ $\begingroup$What this proof is saying is that there is a $q(x)$ (the quotient) for every $g(x)$, and there is also an $r(x)$ if there is a remainder.
e.g. Show the following in the form: $$ f(x) = g(x)q(x) + r(x) $$ where $g(x) = x+1 $
and $f(x) = x^{2} + x + 1 $.
So here we apply either the division transformation or synthetic division.
In the end, we get $$f(x) = (x+1)(x) + 1$$
Here, $g(x) = x+1$, $q(x) = x$, and $r(x) = 1$.
See for a more detailed explanation.
$\endgroup$ $\begingroup$The theorem of Euclidean division for polynomials states that
Let $K$ be a field. For any polynomials $f(x),\, g(x)\in K[x]$, $g(x)\neq 0$, there exists a pair of polynomials $q(x), r(x)$ such that
- $g(x)=q(x)g(x)+r(x)$
- $r(x)=0\;$ or $\;\deg r(x)<\deg g(x)$.
Furthermore, the pair $\bigl(q(x),r(x)\bigr)$ satisfying these conditions is unique.
The existence proof is easy by strong induction on the degree of $f(x)$:
- If $f(x)=0$ or $\deg f(x)<\deg g(x)$, there an obvious solution: $q(x)=0$, $r(x)=f(x)$.
- If $n=\deg f(x)\ge \deg g(x)=d$, suppose the assertion is true for all polynomials of degree $<n$, and write: \begin{align*} f(x)&=\sum^{n-1}_{i=0}a_ix^i+a_nx^n,& g(x)&=\sum^{d-1}_{i=0}b_ix^i+b_dx^d \end{align*} The polynomial $$ f_1(x)=f(x)-\dfrac{a_n}{b_d}x^{n-d}g(x)=\sum^{n-1}_{i=0}a_ix^i+a_nx^n - \sum^{d-1}_{i=0}\frac{a_nb_i}{b_d}x^{n-d+i}-a_n x^n$$ has degree $\le n-1$. By the inductive hypothesis, we can write: $$f_1(x)=q_1(x)g(x)+r_1(x),\quad r_1(x)=0\enspace\text{or}\enspace\deg r_1(x)<\deg(x)$$ whence $$f(x)=f_1(x)+\dfrac{a_n}{b_d}x^{n-d}g(x)=\Bigl(\underbrace{q_1(x)+\dfrac{a_n}{b_d}x^{n-d}}_{\textstyle q(x)}\Bigr)g(x)+\underbrace{r_1(x)}_{r(x)}$$
Unicity:
Suppose we have $f(x)=q(x)g(x)+r(x)=q_1(x)g(x)+r_1(x)$. We rewrite the last equality as $$\bigl(q_1(x)-q(x)\bigr)g(x)=r(x)-r_1(x)$$ This implies $q_1(x)=q(x)$, hence $r(x)=r_1(x)$.
Indeed, if $q_1(x)\neq q(x)$, $\deg\bigl(q_1(x)-q(x)\bigr)g(x)\ge\deg g(x)$, whereas $$\deg\bigl(r(x)-r_1(x)\bigr)\le\max\bigl(\deg r(x),\deg r_1(x)\bigr)<\deg g(x).$$
Note: If we drop the condition on the degree of $r(x)$, unicity is no more true.
$\endgroup$ $\begingroup$Suppose the leading term of $f$ is $a_nx^n$ and the leading term of $g$ is $b_mx^m$ where $m \leq n$. If $m>n$, then it suffices to pick $q(x)=0$ and $r(x)=g(x)$.
Notice that if we take $f(x)-\frac{a_n}{b_m}x^{n-m}g(x)$, then the leading term in $f$ goes away and the difference, which we'll call $r_1(x)$, is now a polynomial whose degree is one less than $f$. So we have, $f(x) = \frac{a_n}{b_m}x^{n-m}g(x)+r_1(x)$. Do you see a way we can continue this process? (Hint: Try to see the connection between the proof and the steps involved in polynomial long division.)
$\endgroup$
