Пусть $ \mathbb A_{} $ означает какое-то из множеств $ \mathbb Q, \mathbb R $ или $ \mathbb C_{} $.

Теорема. Для полиномов $ f_{}(x) $ и $ g(x)\not \equiv 0 $ из $ \mathbb A[x] $ существует единственная пара полиномов $ q_{}(x) $ и $ r(x) $ из $ \mathbb A[x] $ таких, что

$$ f(x) \equiv g(x) q(x) + r(x) \quad \mbox{ и } \quad \deg r < \deg g \ . $$

Доказательство. Пусть $$f(x)=a_0x^n+a_1x^{n-1}+\dots +a_n,\ g(x)=b_0x^m+b_1x^{m-1} + \dots + b_m \quad \mbox{ и } \quad a_0\ne 0, b_0 \ne 0 \ . $$ Если $ n_{}< m $, то можем задать искомые полиномы равенствами: $ q(x) \equiv 0, r(x) \equiv f(x) $. Если же $ n \ge m $, то рассмотрим полином $$f_1(x) = f(x) - \frac{a_0}{b_0} x^{n-m}g(x) \ .$$ Очевидно, что $ n_1 = \deg f_1 (x) < n $. Если $ n_1<m $, то условиям теоремы удовлетворяет пара $$ q(x) = \frac{a_0}{b_0} x^{n-m},\ r(x) = f_1(x)\ . $$ Если $ n_1 \ge m $, то обозначим старший коэффициент $ f_{1}(x) $ через $ a_{1,0} $ и к этому полиному применим те же рассуждения, что и к $ f_{}(x) $, именно, составим $$f_2(x) = f_1(x) - \frac{a_{1,0}}{b_0} x^{n_1-m}g(x) \ .$$ Очевидно, что $ n_2 = \deg f_2 (x) < n_1<n $. Если $ n_2 < m $, то условиям теоремы удовлетворяет пара $$q(x) = \frac{a_0}{b_0} x^{n-m} + \frac{a_{1,0}}{b_0} x^{n_1-m} ,\ r(x) = f_2(x) \ .$$ Если же $ n_2 \ge m $, то обозначим старший коэффициент $ f_2(x) $ через $ a_{2,0} $ и к этому полиному применим те же рассуждения, что и к $ f_{1}(x) $, именно, составим $$f_3(x) = f_2(x) - \frac{a_{2,0}}{b_0} x^{n_2-m}g(x) \ .$$ И так далее. Поскольку степени полиномов $ f_1(x),f_2(x),\dots $ убывают, то за конечное число шагов $ k_{} $ мы дойдем до такого полинома $$f_k(x) = f_{k-1}(x)- \frac{a_{k-1,0}}{b_0} x^{n_{k-1}-m}g(x) \ ,$$ степень которого $ n_k = \deg f_k(x) $ будет меньше $ m_{} $. Тогда пара $$q(x) = \frac{a_0}{b_0} x^{n-m} + \frac{a_{1,0}}{b_0} x^{n_1-m} + \dots + \frac{a_{k-1,0}}{b_0} x^{n_{k-1}-m} ,\ r(x) = f_k(x) $$ будет удовлетворять условиям теоремы.

Покажем теперь единственность полученной пары полиномов $ q_{}(x) $ и $ r_{}(x) $, удовлетворяющих этим условиям. Если существуют еще одна пара, такая, что $$f(x) \equiv g(x) \tilde{q}(x) + \tilde{r}(x) \quad \mbox{ и } \ \deg \tilde{r} < \deg g \ , $$ то $ g(x)(q(x)-\tilde{q}(x)) \equiv \tilde{r}(x)-r(x) $. Однако из последнего тождества следует, что правая его часть должна быть тождественным нулем, т.к., в противном случае, поскольку $ \deg (\tilde{r}(x)-r(x)) < \deg g $, и мы приходим к противоречию с теоремой о степени произведения полиномов. Из условия $ r(x) \equiv \tilde{r}(x) $ будет, однако, следовать, что и $ q(x) \equiv \tilde{q}(x) $. ♦

В терминологии теоремы полином $ f_{}(x) $ называется делимым, $ g_{}(x) $ — делителем, $ r_{}(x) $ — остатком от деления $ f_{}(x) $ на $ g_{}(x) $, а $ q_{}(x) $ — частным¹⁾. При $ r(x) \equiv 0 $, говорят, что полином $ f_{}(x) $ делится (нацело) на $ g_{}(x) $, а полином $ g_{}(x) $ называется делителем $ f_{}(x) $. Тривиальными делителями полинома $ f_{}(x) $ называют сам полином $ f_{}(x) $ и полином тождественно равный $ 1_{} $ (оба — с точностью до домножения на ненулевую константу). Любой другой делитель полинома (если существует) называется нетривиальным.

Частное и остаток от деления $ f(x) = \sum_{j=0}^n a_jx^{n-j} $ на $ g(x)\equiv x- c $ равны соответственно

$$ q(x) \equiv a_0x^{n-1}+(a_0c+a_1)x^{n-2}+(a_0c^2+a_1c+a_2)x^{n-2}+\dots+ (a_0c^{n-1}+a_1c^{n-2}+\dots+a_{n-1})\, , $$ $$ r(x)\equiv f(c) \, . $$ Коэффициенты $ q(x) $ и $ r(x) $ могут быть вычислены рекурсивно по схеме Хорнера.

Пусть $ \deg f(x) = n > \deg g(x)=m $. Доказать, что частное от деления $ f_{}(x) $ на $ g_{}(x) $ может быть представлено в любом из двух эквивалентных видов

$$ q(x)\equiv - \frac{1}{b_0^{n-m+1}} \left| \begin{array}{lllll} b_0 & 0 & \dots & 0 & a_0 \\ b_1 & b_0 & \dots & 0 & a_1 \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ b_{n-m} & b_{n-m-1} & \dots & b_0 & a_{n-m} \\ x^{n-m} & x^{n-m-1} & \dots & 1 & 0 \end{array} \right|_{(n-m+2)\times (n-m+2)} \equiv $$ $$ \equiv \left( x^{n-m} , x^{n-m-1} , \dots , 1 \right) \left(\begin{array}{llll} b_0 & 0 & \dots & 0 \\ b_1 & b_0 & \dots & 0 \\ \vdots & & \ddots & \vdots \\ b_{n-m} & b_{n-m-1} & \dots & b_0 \end{array} \right)_{(n-m+1)\times (n-m+1)}^{-1} \left(\begin{array}{l} a_0 \\ a_1 \\ \vdots \\ a_{n-m} \end{array} \right)\, . $$ Матрица из последней строки — тёплицева.

Доказать, что если $ f_{}(x) $ и $ g_{} (x) $ — полиномы с целыми коэффициентами и старший коэффициент полинома $ g_{} (x) $ равен $ 1_{} $, то частное и остаток от деления $ f_{}(x) $ на $ g_{} (x) $ будут полиномами с целыми коэффициентами.