Теорема. Деление с остатком

Теорема

Для любых многочленов $f,g$ можно осуществить деление с остатков $f$ на $g$, причём единственным образом. Иначе говоря:

$$\forall f,g\in P[x]\exists !q(x)\in P[x]\wedge \exists !r(x)\in P[x]:\mathrm{deg}r(x)<\mathrm{deg}g(x),(f(x)=g(x)\cdot q(x)+r(x))$$

Доказательство

Пусть $f=a_n{x}^n+a_{n-1}{x}^{n-1}+\dots +a_{1}x+a_0,g=b_m{x}^m+b_{m-1}{x}^{m-1}+\dots +b_{1}x+b_0$

Зафиксируем степень многочлена $g(x)$, считая её большей 0 , и будем строить доказательство методом математической индукции по степени многочлена $f(x)$.

1. Пусть $n<m$:
   Тогда $f(x)=0\cdot g(x)+f(x)$
   Здесь $q(x)=0,r(x)=f(x),\mathrm{degr}(x)<\mathrm{deg}g(x)$

2. Допустим теперь, что $n\ge m$ и утверждение доказано для всех $k<n$. Покажем его выполнение и для $k=n$.:
   Рассмотрим многочлен

   $$h(x)=f(x)-\frac{a_n}{b_m}\cdot x^{n-m}\cdot g(x)$$

   Нетрудно видеть, что его степень меньше $n$, а значит к нему применимо индуктивное предположение:

   $$h(x)=g(x)\cdot q_h(x)+r_h(x),{\mathrm{degr}}_h(x)<\mathrm{degg}(x)$$

   Следовательно

   \begin{array}{l} f(x)=h(x)+\frac{a_{0}}{b_{0}} \cdot x^{n-m} \cdot g(x)=g(x) \cdot q_{h}(x)+r_{h}(x)+\frac{a_{0}}{b_{0}} \cdot x^{n-m} \cdot g(x)= \\

= \ g(x)\left(q_{h}(x)+\frac{a_{0}}{b_{0}} \cdot x^{n-m}\right)+r_{h}(x) \
q(x)=q_{h}(x)+\frac{a_{0}}{b_{0}} \cdot x^{n-m}, r(x)=r_{h}(x) \text { и } \operatorname{degr}(x)<\operatorname{deg} g(x) \end{array}

Существование представления доказано, теперь докажем его единственность. Пусть $f(x)=g(x) \cdot q(x)+r(x)=g(x) \cdot q_{1}(x)+r_{1}(x)$. Отсюда:

0=\left(q(x)-q_{1}(x)\right) g(x)+r(x)-r_{1}(x)

Поскольку степень первого слагаемого выше степени второго, это возможно, только если $q(x)-q_{1}(x)=0$ и $r(x)-r_{1}(x)=0$, откуда и получаем единственность представления. Теорема доказана.

многочлены