polynomials.tex

\section{Кольцо многочленов}

\subsection{Определение и первые свойства}

\literature{[F], гл. III, \S~1, пп. 1--3; [K1], гл. 5, \S~2, п. 1;
  [vdW], гл. 3, \S~14.}

Мы воспринимаем многочлен просто как последовательность его
коэффициентов: то, что в привычной записи выглядит как
$2x^3-5x+4$, для нас является бесконечной последовательностью
$(4,-5,0,2,0,0,\dots)$.

\begin{definition}
Пусть $R$~--- кольцо (коммутативное, ассоциативное, с $1$).
\dfn{Многочленом над $R$}\index{многочлен} (или
\dfn{многочленом с коэффициентами из $R$}) называется бесконечная
последовательностью элементов $R$, в которой все элементы, кроме
конечного числа, равны нулю. Иными словами~--- это последовательностью
$(a_0,a_1,a_2,\dots)$, где $a_i\in R$ со следующим свойством:
существует натуральное $N\in\mb N$ такое, что $a_i=0$ для всех $i>N$.
Введем следующие операции сложения и умножения на множестве всех
многочленов над $R$:
пусть $a=(a_0,a_1,a_2,\dots)$, $b=(b_0,b_1,b_2,\dots)$.
Положим $a+b=(a_0+b_0,a_1+b_1,a_2+b_2,\dots)$,
$ab=(a_0b_0,a_0b_1+a_1b_0,a_0b_2+a_1b_1+a_2b_2,\dots)$.
Формально: $(a+b)_k=a_k+b_k$, $(ab)_k=\sum_{i=0}^ka_ib_{k-i}$.

Проверим, что сумма многочленов действительно является многочленом, то
есть, что начиная с некоторого места все коэффициенты в $a+b$ равны
нулю. Поскольку $a$ является многочленом, найдется натуральное $M$
такое, что $a_i=0$ при $i>M$. Поскольку $b$ является многочленом,
найдется натуральное $N$ такое, что $b_i=0$ при $i>N$. Но тогда при
$i > \max(M,N)$ выполнено и $a_i=0$, и $b_i=0$, откуда
$(a+b)_i = a_i + b_i = 0$ для всех таких $i$.

Чуть сложнее строго показать, что произведение многочленов является
многочленом. Пусть снова $a_i=0$ при всех $i>M$, и $b_j=0$ при всех
$j>N$. Мы утверждаем, что при $k > M+N$ коэффициент
$(ab)_k$ равен нулю. Действительно, по определению
$$(ab)_k = \sum_{i+j = k}a_ib_j.$$
Заметим, что при $i+j>M+N$ выполнено хотя бы одно из неравенств $i>M$,
$j>N$ (иначе, если $i\leq M$ и $j\leq N$, то $i+j\leq M+N$~---
противоречие). Значит, каждое слагаемое в сумме, стоящей в правой
части, равно нулю, ибо $a_i = 0$ при $i>M$, а $b_j=0$ при
$j>N$. Поэтому и вся сумма $(ab)_k$ равна нулю.

Множество всех многочленов над $R$ с определенными таким образом
операциями обозначим через $R[x]$.
\end{definition}

\begin{remark}
В обозначении $R[x]$ буква $x$ пока не несет никакого смысла; чуть
ниже мы узнаем, что такое каноническая запись многочлена, и $x$ станет
вполне определенным элементом $R[x]$. Тем не менее, на ее место можно
выбрать любую другую букву.
\end{remark}

\begin{theorem}
$R[x]$ является кольцом (ассоциативным, коммутативным, с $1$).
\end{theorem}
\begin{proof}
Необходимо проверить восемь аксиом из определения кольца
(\ref{def:ring}). Сложение в $R[x]$ происходит
покомпонентно, поэтому первые четыре аксиомы, отражающие свойства
сложения (ассоциативность и
коммутативность, наличие нейтрального элемента и
противоположных) сразу следуют из соответствующих свойств сложения в
кольце $R$. Отметим лишь, что роль нейтрального элемента по сложению
играет последовательность $(0,0,0,\dots)$, а роль противоположной к
последовательности $(a_0,a_1,a_2,\dots)$ играет последовательность
$(-a_0,-a_1,-a_2,\dots)$.

Ассоциативность умножения: пусть $a=(a_0,a_1,\dots)$,
$b=(b_0,b_1,\dots)$, $c=(c_0,c_1,\dots)$~--- элементы $R[x]$. Тогда
\begin{align*}
((ab)c)_l&=\sum_{k=0}^l(ab)_kc_{l-k}=\sum_{k=0}^l\sum_{i=0}^ka_ib_{k-i}c_{l-k},\\
(a(bc))_l&=\sum_{i=0}^la_i(bc)_{l-i}=\sum_{i=0}^la_i\sum_{j=0}^{l-i}b_jc_{l-i-j}\\
&=\sum_{i=0}^la_i\sum_{i+j=i}^lb_jc_{l-i-j}.
\end{align*}
Сделав замену $k=i+j$ в последней сумме, получаем
$(a(bc))_l=\sum_{i=0}^l a_i\sum_{k=i}^lb_{k-i}c_{l-k}$. Теперь видно,
что суммы в выражениях для $((ab)c)_l$ и $(a(bc))_l$ равны; можно
считать, что суммирования производятся по парам $(i,k)$ таким, что
$0\leq i\leq k\leq l$.

Покажем, что элемент $e=(1,0,0,\dots)$ является нейтральным по
умножению. Действительно, $(ae)_k=\sum_{i=0}^ka_ie_{k-i}=a_k$ и
$(ea)_k=\sum_{i=0}^ke_ia_{k-i}=a_k$. Умножение коммутативно:
$(ab)_k=\sum_{i=0}^ka_ib_{k-i}$,
$(ba)_k=\sum_{j=0}^kb_ja_{k-j}=\sum_{k-j=0}^{k}b_{k-(k-j)}a_{k-j}$, и
осталось сделать замену $i=k-j$.

Наконец, проверим дистрибутивность:
\begin{align*}
((a+b)c)_k&=\sum_{i=0}^k(a+b)_ic_{k-i}\\
&=\sum_{i=0}^k(a_i+b_i)c_{k-i}\\
&=\sum_{i=0}^k(a_ic_{k-i}+b_ic_{k-i})\\
&=\sum_{i=0}^k(a_ic_{k-i})+\sum_{i=0}^k(b_ic_{k-i})\\
&=(ac)_k+(bc)_k.
\end{align*}
\end{proof}

\begin{remark}\label{rem_r_in_poly}
Можно считать, что кольцо $R$ является подмножеством кольца $R[x]$;
действительно, каждому элементу $a\in R$ соответствует многочлен
$(a,0,0,\dots)$, и операции на таких элементах в $R[x]$ соответствуют
операциям в $R$. В силу этого, многочлен $(0,0,0,\dots)$, являющийся
нейтральным элементом по сложению кольца $R[x]$, мы обозначаем просто
через $0$, а многочлен $e=(1,0,0,\dots)$~--- через $1$. Поэтому мы
часто будем писать $a$ вместо многочлена $(a,0,0,\dots)$ для элементов
$a\in R$. При этом, как нетрудно видеть,
$a\cdot (b_0,b_1,b_2,\dots)=(ab_0,ab_1,ab_2,\dots)$.
\end{remark}

\begin{remark}
Как и в других кольцах, для натурального $n$ и $f\in R[x]$ мы
обозначаем через $f^n$ многочлен
$\underbrace{f\cdot\dots\cdot f}_{n}$; если $n=0$, положим $f^0=1\in
R[x]$.
\end{remark}

\begin{definition}
Пусть $a=(a_0,a_1,a_2,\dots)$~--- многочлен над кольцом $R$.
\dfn{Степенью}\index{степень многочлена} многочлена $a$ называется
наибольшее $d$ такое, что
$a_d\neq 0$. Удобно считать, что степень нулевого многочлена
$(0,0,\dots)$ равна $-\infty$. Если же $a\neq 0$, то степень $a$~---
натуральное число. Обозначение: $d=\deg(f)$. Заметим, что многочлены
степени $0$~--- это в точности ненулевые константы из $R$.
\end{definition}

\begin{remark}
Обозначим через $x$ элемент $(0,1,0,0,\dots)\in R[x]$. Нетрудно
видеть, что $x^2=(0,0,1,0,0,\dots)$, и вообще
$x^n=(\underbrace{0,\dots,0}_{n},1,0,0,\dots)$ для всякого
натурального $n$.
С учетом замечания~\ref{rem_r_in_poly} любой элемент
$a=(a_0,a_1,a_2,\dots)\in R[x]$ можно записать как
\begin{align*}
a&=(a_0,a_1,a_2,a_3,\dots)\\
&=(a_0,0,0,0,\dots)+(0,a_1,0,0,\dots)+(0,0,a_2,0,\dots)+\dots\\
&=a_0\cdot(1,0,0,0,\dots)+a_1\cdot(0,1,0,0,\dots)+a_2\cdot(0,0,1,0,\dots)+\dots\\
&=a_0+a_1x+a_2x^2+\dots.
\end{align*}
Конечно, в полученной сумме лишь конечное число ненулевых слагаемых;
если $\deg(a)=d$, можно записать $a=a_0+a_1x+\dots+a_dx^d$. Такая
запись называется \dfn{канонической записью
  многочлена}\index{каноническая запись многочлена}.
\end{remark}

\begin{theorem}
Пусть $R$~--- область целостности. Тогда
$\deg(f\cdot g)=\deg(f)+\deg(g)$ для любых $f,g\in R[x]$.
\end{theorem}
\begin{proof}
Пусть $m=\deg(f)$, $n=\deg(g)$. Запишем $f=a_0+a_1x+\dots+a_mx^m$,
$g=b_0+b_1x+\dots+b_nx^n$. По определению степени имеем $a_m\neq 0$ и
$b_n\neq 0$. Нетрудно видеть, что $fg=a_0b_0+\dots+a_mb_nx^{m+n}$ и
$a_mb_n\neq 0$, поскольку $R$~--- область целостности.
\end{proof}

\begin{remark}
Заметим, что теорема верна и для случая $f=0$ или $g=0$ за счет нашего
соглашения $\deg(0)=-\infty$.
\end{remark}

\begin{corollary}\label{cor:r[x]_is_domain}
Если $R$~--- область целостности, то $R[x]$~--- область целостности.
\end{corollary}
\begin{proof}
Пусть $fg=0$; предположим, что $f\neq 0$, $g\neq 0$, тогда $\deg(f)$ и
$\deg(g)$~--- натуральные числа, поэтому и $\deg(fg)$~--- натуральное число.
\end{proof}

\begin{corollary}
Пусть $R$~--- область целостности.
Многочлен $f\in R[x]$ является обратимым тогда и только тогда, когда
он имеет степень $0$, то есть является элементом $f=r\in R$, и $r$
обратим в $R$. Иными словами, $R[x]^*=R^*$.
\end{corollary}
\begin{proof}
Пусть $f\in R[x]^*$ и $g\in R[x]$~--- обратный элемент к $f$:
$fg=1$. При этом $\deg(f)+\deg(g)=\deg(fg)=\deg(1)=0$. Если одна из
степеней $f,g$ равна $-\infty$, то и $\deg(fg)$ равнялась бы
$-\infty$; поэтому оба числа $\deg(f)$, $\deg(g)$ натуральны и,
следовательно, равны $0$. Значит, $f,g\in R$~--- константы,
произведение которых равно $1\in R$. Поэтому $f\in R^*$.

Обратно, если $f\in R^*$, обозначим через $g\in R^*$ обратный элемент
к $f$ в $R$. Тогда $fg=1$, и если рассмотреть $f,g$ как многочлены,
получим, что $f\in R[x]^*$.
\end{proof}

% 12.11.2014

\subsection{Делимость в кольце многочленов}

\literature{[F], гл. VI, \S~1, п. 1--2; [K1], гл. 5, \S~2, п. 3; \S~3,
п. 1; [vdW], гл. 3, \S~14.}

Начиная с этого места мы считаем, что кольцо $R$ является областью
целостности (тогда по теореме~\ref{cor:r[x]_is_domain} и $R[x]$
является областью целостности).

Сейчас мы перенесем основные определения из
раздела~\ref{subsect_divide} на случай кольца многочленов.

\begin{definition}
Пусть $f,g\in R[x]$. Говорят, что многочлен $g$
\dfn{делит}\index{делимость!многочленов}
многочлен $f$ (или что $f$ \dfn{делится на} $g$), если $f=gp$ для
некоторого $p\in R[x]$. Обозначение:
$g\divides f$.
\end{definition}
\begin{proposition}[Свойства делимости в кольце многочленов]
Пусть $f,g,h\in R[x]$. Тогда
\begin{enumerate}
\item $f\divides f$ и $f\divides 1$;
\item если $h\divides f$, $h\divides g$, то $h\divides f+g$;
\item если $h\divides f$, то $h\divides fg$;
\item если $h\divides g$, $g\divides f$, то $h\divides f$.
\end{enumerate}
\end{proposition}
\begin{proof}
\begin{enumerate}
\item $f=f\cdot 1=1\cdot f$.
\item если $f=hp$, $g=hq$, то $f+g=h(p+q)$.
\item если $f=hp$, то $fg=hgp$.
\item если $g=hp$, $f=gq$, то $f=hpq$.
\end{enumerate}
\end{proof}

\begin{definition}
Два элемента $f,g\in R[x]$ называются
\dfn{ассоциированными}\index{ассоциированность!многочленов}, если
$g\divides f$ и $f\divides g$.
\end{definition}
\begin{proposition}
Ассоциированность является отношением эквивалентности.
\end{proposition}
\begin{proof}
Очевидно.
\end{proof}

\begin{proposition}
$f,g\in R[x]$ ассоциированы тогда и только тогда, когда $f=cg$ для
некоторой обратимой константы $c\in R^*$.
\end{proposition}
\begin{proof}
Если $f=cg$ для $c\in R^*$, то $g\divides f$ и $g=c^{-1}f$, поэтому
$f\divides g$. Обратно, из $g\divides f$ следует, что $f=gp$, а из
$f\divides g$ следует, что $g=fq$. Поэтому $f=gp=fqp$, откуда
$f(1-pq)=0$. Заметим, что $R[x]$~--- область целостности, поэтому
$f=0$ или $1-pq=0$. Если
$f=0$, то и $g=0$, и доказывать нечего. Иначе получаем, что $1=pq$,
откуда $p\in R[x]^*=R^*$. Значит,
$p$~--- ненулевая константа, что и требовалось доказать.
\end{proof}

\begin{theorem}[О делении с остатком в кольце многочленов]
Пусть $R$~--- область целостности, $f,g\in R[x]$, $g\neq 0$,
и старший коэффициент многочлена $g$ обратим. Существуют единственные
многочлены $h,r\in R[x]$ такие, что $f=gh+r$ и $\deg(r)<\deg(g)$.
\end{theorem}
\begin{proof}
Сначала докажем существование индукцией по $\deg(f)$. Если
$\deg(f)<\deg(g)$, можно записать $f=g\cdot 0+f$, то есть, взять $h=0$
и $r=f$.

Пусть теперь $\deg(f)\geq\deg(g)$. Запишем $f=a_mx^m+\dots$,
$g=b_nx^n+\dots$, где $m=\deg(f)$, $n=\deg(g)$. Таким образом,
$a_m\neq 0$, $b_n\neq 0$ и $m\geq n$. Более того, по нашему
предположению коэффициент $b_n$ обратим в $R$.
Рассмотрим многочлен
$f_0=f-g\cdot a_m b_n^{-1} x^{m-n}$. Степень $g$ равна $n$,
степень монома
$a_m b_n^{-1}x^{m-n}$ равна $m-n$, поэтому степень многочлена
$g\cdot a_m b_n^{-1}x^{m-n}$ равна $m$, как и степень $f$. Значит,
степень $f_0$ не превосходит $m$.

Посмотрим на коэффициент многочлена
$f_0$ при $x^m$. Он равен разности коэффициентов $f$ и
$g\cdot a_m b_n^{-1}x^{m-n}$ при $x^m$, то есть,
$a_m-b_n\cdot a_m b_n^{-1}=0$. Значит, степень $f_0$ строго
меньше $m=\deg(f)$. Поэтому к $f_0$ можно применить
предположение индукции и записать $f_0=gh_0+r_0$,
где $\deg(r)<\deg(g)$. Тогда $f=f_0+g\cdot a_m b_n^{-1}x^{m-n}
= gh_0+r_0+g\cdot a_m b_n^{-1}x^{m-n}
= g(h_0+a_mb_n^{-1}x^{m-n})+r_0$. Возьмем
$h=h_0+a_m b_n^{-1}x^{m-n}$ и $r=r_0$; тогда $f=gh+r$ и
все еще $\deg(r)=\deg(r_0)<\deg(g)$.

Осталось доказать единственность: предположим, что $f=gh+r$ и
$f=g\widetilde{h}+\widetilde{r}$. Тогда
$g(h-\widetilde{h})=\widetilde{r}-r$. Степени
многочленов $r$ и $\widetilde{r}$ меньше степени $g$, поэтому степень
правой части равенства меньше степени $g$; в то же время, степень
правой части равна сумме степеней $g$ и $h-\widetilde{h}$. Такое
возможно только если степень $h-\widetilde{h}$ равна $-\infty$, то
есть, $h=\widetilde{h}$, откуда и $r=\widetilde{r}$.
\end{proof}

\begin{remark}
Заметим, что условие обратимости старшего коэффициента многочлена $g$
автоматически выполняется, если $R$~--- поле. Таким образом,
над полем можно делить любой многочлен на любой ненулевой.
\end{remark}

\subsection{Многочлен как функция}

\literature{[F], гл. III, \S~1, пп. 4--7; [K1], гл. 6, \S~1, п. 1--2; [vdW], гл. 5, \S~28.}

\begin{definition}\label{dfn:poly-value}
Пусть $f=a_0+a_1x+\dots+a_nx^n\in R[x]$,
$c\in R$. \dfn{Значением}\index{значение многочлена}
многочлена $f$ в точке $c$ называется
$f(c)=a_0+a_1c+\dots+a_nc^n=\sum_{i=0}^\infty a_ic^i\in R$.
\end{definition}

\begin{remark}\label{rem_poly_function}
Таким образом, с каждым многочленом $f\in R[x]$ связано отображение
$\widetilde{f}\colon R\to R$, $c\mapsto f(c)$.
Мы называем это отображение \dfn{полиномиальной
  функцией}\index{полиномиальная функция}, заданной
многочленом $f$.
\end{remark}

\begin{proposition}\label{prop:evaluation-properties}
Для любых $f,g\in R[x]$, $c\in R$, выполнено
\begin{enumerate}
\item $(f+g)(c)=f(c)+g(c)$;
\item $(fg)(c)=f(c)\cdot g(c)$;
\item если $f=r\in R$, то $f(c)=r$
\end{enumerate}
\end{proposition}
\begin{proof}
Пусть $f=\sum_{i=0}^\infty a_ix^i$, $g=\sum_{i=0}^\infty
b_ix^i$.
\begin{enumerate}
\item $f+g=\sum_{i=0}^\infty (a_i+b_i)x^i$, поэтому
$(f+g)(c)=\sum_{i=0}^\infty
(a_i+b_i)c^i=\sum_{i=0}^\infty(a_ic^i)+\sum_{i=0}^\infty(b_ic^i)=f(c)+g(c)$.
\item $fg=\sum_{m=0}^\infty\sum_{i+j=m}^\infty (a_ib_jx^m)$, поэтому
$f(c)g(c)=(\sum_{i=0}^\infty a_ic^i)(\sum_{j=0}^\infty
b_jc^j)=\sum_{i,j=0}^\infty
(a_ib_jc^{i+j})=\sum_{m=0}^\infty\sum_{i+j=m}(a_ib_jc^{m})=(fg)(c)$.
\item $f(c)=r+0\cdot c+\dots=r$.
\end{enumerate}
\end{proof}

\begin{definition}
Пусть $f\in R[x]$, $c\in R$. Говорят, что $c$ является
\dfn{корнем}\index{корень многочлена}
многочлена $f$, если $f(c)=0$.
\end{definition}

\begin{theorem}[Лемма Безу]\label{thm_bezout}
Пусть $f\in R[x]$, $c\in R$.
Многочлен $f$ делится на многочлен $(x-c)$ тогда и только тогда, когда
$c$ является корнем $f$. Более точно, остаток от деления многочлена
$f$ на $(x-c)$ равен $f(c)$.
\end{theorem}
\begin{proof}
Поделим $f$ на $x-c$ с остатком (заметим, что это можно сделать,
поскольку старший коэффициент многочлена $x-c$ обратим).
$f = (x-c)h + r$. Заметим, что $\deg(r) < \deg(x-c) = 1$, поэтому
$r\in R$~--- константа. Подставим $c$ в обе части этого равенства:
$$f(c) = ((x-c)h + r)(c) = ((x-c)h)(c) + r(c) = 0\cdot h(c) + r = r.$$
Если $f$ делится на $x-c$, то $r=0$, и потому $f(c) = 0$. Обратно,
если $f(c) = 0$, то и $r=0$, и потому $f$ делится на $(x-c)$.
\end{proof}

\begin{proposition}\label{prop_linear_factors}
Пусть $f\in R[x]$, $f\neq 0$. Тогда $f$ можно записать в виде
$f=(x-c_1)\dots (x-c_m)h$, где $c_1,\dots,c_m\in R$~--- все корни $f$
(возможно, с повторениями), а $h\in R[x]$~---
многочлен, у которого нет корней в кольце $R$.
\end{proposition}
\begin{proof}
Доказываем индукцией по $\deg(f)$. База: $\deg(f)=0$, то есть, $f$~---
ненулевая константа. Это многочлен без корней, поэтому можно взять
$m=0$ и $h=f$. Теперь пусть $\deg(f)>0$. Если у $f$ нет корней, опять
можно взять $m=0$, $h=f$. Если же $c$~--- корень $f$, то (по
теореме~\ref{thm_bezout}) $f=(x-c)f_1$, $\deg(f_1)<\deg(f)$, и к
$f_1$ можно
применить предположение индукции. Поэтому $f_1$ имеет нужное
разложение, и, дописывая к нему скобку $(x-c)$, получаем разложение
для $f$.

Теперь мы получили, что $f = (x-c_1)\dots (x-c_m)h$ для некоторых
$c_1,\dots,c_m\in R$ и многочлена $h\in R[x]$ без корней.
Очевидно, что каждый $c_i$, $i=1,\dots,m$, является корнем
$f$. Осталось показать, что среди $c_1,\dots,c_m$ встречаются все
корни $f$. Если $c$~--- некоторый корень $f$, то
$0=f(c)=(c-c_1)\dots(c-c_m)h(c)$. При этом $h(c)\neq 0$, поскольку у
$h$ нет корней, значит (поскольку $R$~--- область целостности),
одна из скобок вида $(c-c_i)$ равна $0$,
поэтому $c$ содержится среди $c_1,\dots,c_m$.
\end{proof}

\begin{corollary}\label{cor_number_of_roots}
Число различных корней ненулевого многочлена над областью целостности
не превосходит его степени.
\end{corollary}
\begin{proof}
Посмотрим на разложение из предложения~\ref{prop_linear_factors}.
Все корни $c$ многочлена $f\in R[x]$ содержатся среди $c_1,\dots,c_m$,
поэтому их число не больше $m$, а $m=\deg(f)-\deg(h)\leq\deg(f)$.
\end{proof}

Позже (см. замечание~\ref{rem_number_of_roots_with_multiplicities}) мы
уточним это следствие с помощью понятия {\it кратности} корня.

\begin{definition}
Пусть $f,g\in R[x]$~--- многочлены над областью целостности
$R$. Говорят, что многочлен $f$ \dfn{функционально
  равен}\index{функциональное равенство многочленов}  многочлену $g$,
если $f(c)=g(c)$ для
любого $c\in R$. Иными словами, многочлены функционально равны, если
задаваемые ими функции равны: $\widetilde{f}=\widetilde{g}$
(см.~замечание~\ref{rem_poly_function}). Обычное равенство многочленов
при этом иногда называют
\dfn{формальным равенством}\index{формальное равенство многочленов}:
многочлены $f$ и $g$ формально равны, если $f=g$.
\end{definition}

\begin{example}
Пусть $R=\mb Z/2\mb Z=\{\ol{0},\ol{1}\}$. Рассмотрим многочлен
$f=x^2-x$. Заметим, что $f(\ol{0})=f(\ol{1})=\ol{0}$. Поэтому
многочлен $f$ функционально равен многочлену $0$, но, конечно, $f\neq
0$. Этот пример обобщается на поле $R=\mb Z/p\mb Z$: достаточно взять
$f=x^p-x$ и вспомнить малую теорему Ферма
(следствие~\ref{cor_fermat}).
\end{example}

\begin{remark}
Очевидно, что из формального равенства многочленов следует
функциональное: если $f=g$, то $f(c)=g(c)$ для любого $c\in R$.
\end{remark}

\begin{theorem}
Если область целостности $R$ бесконечна, то из функционального
равенства многочленов над $R$ следует их формальное равенство.
\end{theorem}
\begin{proof}
Пусть $f,g\in R[x]$ и $f(c)=g(c)$ для всех $c\in R$. Посмотрим на
разность $h=f-g\in R[x]$. Для любого $c\in R$ выполнено
$h(c)=f(c)-g(c)=0$, поэтому $c$~--- корень $h$. Если $h$ ненулевой, то
по следствию~\ref{cor_number_of_roots} число корней $h$ не превосходит
его степени; с другой стороны, как мы только что видели, любой элемент
бесконечного кольца $R$ является корнем $h$~--- противоречие. Значит,
$h=0$, поэтому и $f=g$.
\end{proof}

\subsection{Многочлены над $\mb R$ и $\mb C$}

\literature{[F], гл. III, \S~1, п. 8; гл. VI, \S~1, п. 7;  [K1],
  гл. 6, \S~3, п. 1; \S~4, п. 1.}

Сейчас мы уточним разложение из предложения~\ref{prop_linear_factors}
для случая многочленов над полями $\mb R$ и $\mb C$.

\begin{definition}
Поле $k$ называется \dfn{алгебраически
  замкнутым}\index{поле!алгебраически замкнутое}, если у любого
многочлена $f\in k[x]$ степени выше нулевой имеется корень в $k$.
\end{definition}

\begin{example}
Поле комплексных чисел $\mb C$ является алгебраически замкнутым. Это
утверждение называется \dfn{основной теоремой алгебры}\index{основная
  теорема алгебры}; в нашем курсе
мы будем пользоваться им без доказательства. С другой стороны, поле
вещественных чисел $\mb R$ не алгебраически замкнуто: например, у
многочлена $x^2+1$ нет вещественных корней.
\end{example}

\begin{theorem}[Разложение многочлена над алгебраически замкнутым
  полем]\label{thm_irreducible_complex}
Пусть $k$~--- алгебраически замкнутое поле. Тогда любой ненулевой
многочлен $f\in k[x]$ представляется в виде
$f=c_0(x-c_1)\dots(x-c_n)$, где $c_0,c_1,\dots,c_n\in k$.
\end{theorem}
\begin{proof}
По следствию~\ref{prop_linear_factors} можно записать $f=(x-c_1)\dots
(x-c_m)h$, где у $h\in k[x]$ нет корней; по определению алгебраической
замкнутости из этого следует, что $\deg(h)\leq 0$, поэтому $h=c_0\in
k$~--- константа.
\end{proof}

\begin{theorem}[Разложение многочлена над полем вещественных чисел]\label{thm_irreducible_real}
Пусть $f\in\mb R[x]$, $f\neq 0$. Тогда $f$ можно представить в виде
$f=c_0(x-c_1)\dots (x-c_s)(x^2+a_1x+b_1)\dots(x^2+a_rx+b_r)$, где
$c_0,c_1,\dots,c_s,a_1,\dots,a_r,b_1,\dots,b_r\in\mb R$ и $a_i^2-4b_i<0$
для всех $i=1,\dots,r$.
\end{theorem}
\begin{proof}
Доказываем индукцией по степени $f$. Если $\deg(f)=0$, то $f=c_0$,
$s=0$, $r=0$. Пусть теперь $\deg(f)>0$. Рассмотрим $f$ как многочлен
над комплексными числами. По основной теореме алгебры у $f$ есть
корень $\lambda\in\mb C$.

Если $\lambda\in\mb R$, то $f$ делится на
$x-\lambda$, и можно записать $f=(x-\lambda)g$. При этом
$\deg(g)<\deg(f)$, и по предположению индукции $g$ раскладывается в
произведение нужного вида; дописывая к этому разложению скобку
$(x-\lambda)$, получаем и разложение для $f$.

Если же $\lambda\in\mb C\setminus\mb R$, рассмотрим $f(\ol{\lambda})$:
\begin{align*}
f(\ol{\lambda})&=a_0+a_1\ol{\lambda}+\dots+a_n\ol{\lambda}^n\\
&=\ol{a_0}+\ol{a_1\lambda}+\dots+\ol{a_n\lambda^n}\\
&=\ol{f(\lambda)}\\
&=\ol{0}\\
&=0.
\end{align*}
Значит, и $\lambda$, и $\ol{\lambda}$ являются корнями $f$. Поэтому
$f$ делится на $(x-\lambda)(x-\ol{\lambda})$. Запишем
$f=(x-\lambda)(x-\ol{\lambda})g$. Заметим, что 
$(x-\lambda)(x-\ol{\lambda})=
x^2-(\lambda+\ol{\lambda})x+\lambda\ol{\lambda}=
x^2-(2\Ree(\lambda))+|\lambda|^2$~--- квадратичный многочлен с
вещественными коэффициентами. Поэтому коэффициенты многочлены $g$
также вещественны, $\deg(g)<\deg(f)$ и можно применить предположение
индукции. Кроме того, дискриминант квадратичного многочлена
$(x-\lambda)(x-\ol{\lambda})$ меньше $0$, поскольку у него нет
вещественных корней. Поэтому нужное разложение многочлена $f$
получается приписыванием к разложению $g$ указанного квадратичного
многочлена.
\end{proof}

\subsection{Кратные корни и производная}

\literature{[F], гл. VI, \S~2, пп. 1, 3; [K1], гл. 6, \S~1, п. 3--4;
  [vdW], гл. 5, \S\S~27--28.}

Мы возвращаемся к рассмотрению многочленов над произвольной областью
целостности $R$.

\begin{definition}
Пусть $f\in R[x]$, $c\in R$. Говорят, что $c$ является корнем
многочлена $f$
\dfn{кратности $m$}\index{корень многочлена!кратности $m$}, если $f$
делится на $(x-c)^m$, но
не делится на $(x-c)^{m+1}$. Корень $f$ кратности $1$ называют
\dfn{простым корнем $f$}\index{корень многочлена!простой}, а корень
кратности $>1$~--- \dfn{кратным корнем $f$}\index{корень многочлена!кратный}.
\end{definition}

\begin{lemma}\label{lem_root_multiplicity_equiv}
Пусть $f\in R[x]$, $c\in R$, $m\geq 1$. Элемент $c$ является корнем
$f$ кратности
$m$ тогда и только тогда, когда $f$ можно представить в виде
$f=(x-c)^m\cdot g$, где многочлен $g\in R[x]$ таков, что $g(c)\neq 0$.
\end{lemma}
\begin{proof}
Если $c$~--- корень $f$ кратности $m$, то $f=(x-c)^m\cdot g$ для
некоторого $g\in R[x]$. Если $g(c)=0$, то по теореме Безу $g$ делится
на $(x-c)$, поэтому $g=(x-c)h$ и $f=(x-c)^{m+1}h$, то есть, $f$
делится на $(x-c)^{m+1}$~--- противоречие.

Обратно, если $f=(x-c)^m\cdot g$ и $g(c)\neq 0$, то $f$ делится на
$(x-c)^m$. Если при этом $f$ делится на $(x-c)^{m+1}$, то
$f=(x-c)^{m+1}\cdot h$. Сравнивая два выражения для $f$,получаем
$(x-c)^m\cdot g=(x-c)^{m+1}\cdot h$, откуда $(x-c)^m(g-(x-c)h)=0$. Так
как $R[x]$~--- область целостности, получаем $g-(x-c)h=0$, откуда
$g=(x-c)h$ и $g(c)=0$~--- противоречие.
\end{proof}

\begin{remark}\label{rem_number_of_roots_with_multiplicities}
Таким образом, если в выражении для многочлена $f$ из
следствия~\ref{prop_linear_factors} собрать скобки,
соответствующие одинаковым корням, вместе, то скобка $(x-c)$ окажется
с показателем, в точности равным кратности $c$ как корня $f$.
В частности, из этого немедленно следует, что сумма кратностей корней
многочлена $f$ не превосходит его степени.
\end{remark}

\begin{definition}
Пусть $f\in R[x]$, $f=\sum_{s=0}^\infty a_sx^s$.
\dfn{Производным многочленом} от многочлена $f$
(или его \dfn{производной}\index{производная}) называется многочлен
$f'=\sum_{s=1}^\infty sa_sx^{s-1}$.
\end{definition}
\begin{remark}
Напомним, что для элемента $c\in R$ и натурального числа $n$ можно
положить
$nc=\underbrace{c+\dots+c}_{n}=\underbrace{(1+\dots+1)}_{n}\cdot c\in R$.
\end{remark}

% 19.11.2014

\begin{proposition}[Свойства производной]\label{prop:derivative-properties}
Пусть $f,g\in R[x]$, $c\in R$, $m\geq 1$. Тогда
\begin{enumerate}
\item $(f+g)'=f'+g'$
  (\dfn{аддитивность}\index{аддитивность!производной});
\item $(cf)'=cf'$;
\item $(fg)'=f'g+fg'$ (\dfn{тождество Лейбница}\index{тождество
    Лейбница});
\item $(g^m)'=mg^{m-1}g'$.
\end{enumerate}
\end{proposition}
\begin{proof}
Пусть $f=\sum_{s=0}^\infty{a_sx^s}$, $g=\sum_{s=0}^\infty{b_sx^s}$.
\begin{enumerate}
\item $f+g=\sum_{s=0}^\infty{(a_s+b_s)x^s}$, поэтому
$$(f+g)'=\sum_{s=1}^\infty{s(a_s+b_s)x^{s-1}}=
\sum_{s=1}^\infty(sa_sx^{s-1})+\sum_{s=1}^\infty(sb_sx^{s-1})=
f'+g'.$$
\item $cf=\sum_{s=0}^\infty ca_sx^s$, поэтому
$(cf)'=\sum_{s=1}^\infty{sca_sx^{s-1}}=
c\sum_{s=1}^\infty{sa_sx^{s-1}}= cf'$.
\item Докажем сначала тождество Лейбница для {\it мономов}
(многочленов вида $ax^n$): если $f=ax^n$, $g=bx^m$, то $fg=abx^{m+n}$
и $(fg)'=(m+n)abx^{m+n-1}$, в то время как $f'=nax^{n-1}$,
$g'=mbx^{m-1}$, откуда $f'g+fg'=nabx^{m+n-1}+mabx^{m+n-1}=(fg)'$.
Пусть теперь $f,g$ произвольны. Запишем их в виде суммы мономов (это
можно сделать с любым многочленом): $f=f_1+\dots+f_r$,
$g=g_1+\dots+g_s$.
Тогда 
\begin{align*}
fg&=(f_1+\dots+f_r)(g_1+\dots+g_s)\\
&=\sum_{\substack{1\leq i\leq r\\1\leq j\leq s}}f_ig_j.
\end{align*}
Возьмем производную и воспользуемся уже доказанным свойством
аддитивности. Кроме того, заметим, что мы доказали тождество Лейбница
для мономов $f_i$ и $g_j$, поэтому
$(f_ig_j)'=f'_ig_j+f_ig'_j$. Получаем:
\begin{align*}
(fg)'&=\sum_{\substack{1\leq i\leq r\\1\leq j\leq
    s}}(f_ig_j)'\\
&=\sum_{\substack{1\leq i\leq r\\1\leq j\leq
    s}}(f'_ig_j+f_ig'_j)\\
&=\sum_{\substack{1\leq i\leq r\\1\leq j\leq
    s}}(f'_ig_j) + \sum_{\substack{1\leq i\leq r\\1\leq
    j\leq s}}(f_ig'_j)\\
&=(f'_1+\dots+f'_r)(g_1+\dots+g_s)+(f_1+\dots+f_r)(g'_1+\dots+g'_s)\\
&=(f_1+\dots+f_r)'(g_1+\dots+g_s)+(f_1+\dots+f_r)(g_1+\dots+g_s)'\\
&=f'g+fg'
\end{align*}
\item Проведем индукцию по $m$. Для $m=1$ получаем тождество $g'=g'$.
Пусть теперь $m>1$, тогда $(g^m)'=(g\cdot g^{m-1})'=g'\cdot g^{m-1}
+ g\cdot (g^{m-1})'=g^{m-1}g'+g\cdot (m-1)g^{m-2}g'=mg^{m-1}g'$, что и
требовалось.
\end{enumerate}
\end{proof}

\begin{proposition}[Связь между корнями многочлена и его производной]\label{prop_roots_and_derivative}
Пусть $f\in R[x]$, $c\in R$. Элемент $c$ является кратным корнем
многочлена $f$ тогда и только тогда, когда $c$ является корнем и $f$,
и $f'$.
\end{proposition}
\begin{proof}
Если $c$~--- кратный корень $f$, то $f$ делится на $(x-c)^2$. Запишем
$f=(x-c)^2\cdot g$ и посчитаем производную от обеих частей:
$f'=((x-c)^2\cdot g)' = ((x-c)^2)'g+(x-c)^2g' = 2(x-c)g+(x-c)^2g' =
(x-c)(2g+(x-c)g')$.
Значит, $c$ является и корнем $f'$.

Обратно, если $c$ корень $f$ и $f'$, запишем $f=(x-c)g$ и $f'=(x-c)h$.
При этом $(x-c)h=f'=((x-c)g)'=(x-c)'g+(x-c)g'=g+(x-c)g'$. Значит,
$(x-c)(h-g')=g$, откуда $f=(x-c)g=(x-c)^2(h-g')$, и $c$~--- кратный
корень $f$.
\end{proof}

Для исследования более тонких вопросов, касающихся кратностей корней,
нам удобно будет предположить, что основное кольцо $R$ является полем.

\begin{definition}
Пусть $k$~--- поле. \dfn{Характеристикой}\index{характеристика поля}
поля $k$ называется
наименьшее число $p$ такое, что $\underbrace{1+\dots+1}_{p}=0$ в $k$,
если оно существует; в противном случае говорят, что характеристика
$k$ равна $0$. Обозначение: $\cchar(k)=p$.
\end{definition}

\begin{examples}
Поля $\mb Q$, $\mb R$, $\mb C$ имеют характеристику $0$: никакая сумма
единиц не равна нулю. Поле $\mb
Z/p\mb Z$ имеет характеристику $p$: действительно,
$\underbrace{\overline{1}+\dots+\overline{1}}_{m}=\ol{m}$, причем
$\ol{p}=\ol{0}$ и $\ol{m}\neq\ol{0}$ при $1\leq m\leq p-1$.
\end{examples}

\begin{lemma}
Характеристика поля равна $0$ или простому числу.
\end{lemma}
\begin{proof}
Заметим, что характеристика поля не может равняться $1$, поскольку в
поле $1\neq 0$ (см. определение~\ref{def:field}). Если же
$\cchar(k)=ab$~--- составное число ($a,b>1$), заметим, что
$0=\underbrace{1+\dots+1}_{ab} =
(\underbrace{1+\dots+1}_a)(\underbrace{1+\dots+1}_b)$. Поле является
областью целостности, поэтому одна из двух получившихся скобок равна
$0$, но $a,b<ab$, что противоречит минимальности в определении
характеристики.
\end{proof}

\begin{theorem}\label{root_multiplicity_and_derivative_exact}
Пусть $f\in k[x]$, $c\in k$~--- корень $f$, $m\geq 1$, и
характеристика поля $k$ равна 
нулю. Если $c$ является корнем $f$ кратности $m$, то $c$ является
корнем $f'$ кратности $m-1$. Обратно, если $c$~--- корень $f'$
кратности $m-1$, то $c$~--- корень $f$ кратности $m$.
\end{theorem}
\begin{proof}
Пусть $c$~--- корень $f$ кратности $m$; по
лемме~\ref{lem_root_multiplicity_equiv} это означает, что
$f=(x-c)^mg$ и $g(c)\neq 0$. Возьмем производную:
$f'=(x-c)^mg'+m(x-c)^{m-1}g=(x-c)^{m-1}((x-c)g'+mg)$. Мы утверждаем,
что многочлен $(x-c)g'+mg$ в точке $c$ не равен нулю. Действительно,
его значение в точке $c$ равно $0\cdot g'(c)+mg(c)=mg(c)$.
При этом $g(c)\neq 0$ и характеристика поля $k$ равна нулю, поэтому
$m\neq 0$. Снова применяя лемму~\ref{lem_root_multiplicity_equiv},
получаем, что $c$~--- корень $f'$ кратности $m-1$.

Обратно, если $c$~--- корень $f'$ кратности $m-1$, пусть $n$~---
кратность $c$ как корня $f$. По условию $c$ является корнем $f$,
поэтому $n\geq 1$. По уже доказанному теперь $c$ является корнем $f'$
кратности $n-1$, поэтому $n-1=m-1$, откуда $n=m$, что и требовалось.
\end{proof}

\begin{remark}
Теорема~\ref{root_multiplicity_and_derivative_exact} не выполняется
для полей положительной характеристики. Пусть, например,
$k = \mb Z/p\mb Z$~--- поле из $p$ элементов. Рассмотрим многочлен
$f = x^p(x-1) = x^{p+1} - x^p$. Элемент $c = 0$ является корнем
многочлена $f$ кратности $p$, но у его
производной $f' = (p+1)x^p - px^{p-1} = x^p$ элемент $c$ снова
является корнем кратности $p$.
\end{remark}

\begin{theorem}
Пусть $f\in k[x]$, $c\in k$, $m>1$, и характеристика поля $k$ равна
нулю. Элемент $c$ является корнем $f$ кратности $m$ тогда и только
тогда, когда $f(c)=f'(c)=\dots=f^{(m-1)}(c)=0$ и $f^{(m)}(c)\neq 0$.
\end{theorem}
\begin{proof}
Если $c$ является корнем $f$ кратности $m$, то $c$ является корнем
$f'$ кратности $m-1$, \dots, корнем $f^{(m-1)}$ кратности $1$, и не
является корнем $f^{(m)}$.

Обратно, если $f(c)=f'(c)=\dots=f^{(m-1)}(c)=0$ и $f^{(m)}(c)\neq 0$,
воспользуемся индукцией по $m$.
База $m=1$: $f(c)=0$ и $f'(c)\neq 0$~--- по
теореме~\ref{prop_roots_and_derivative} из этого
следует, что $c$~--- простой корень $f$.
Многочлен $f'$ таков, что он и его
первые $m-2$ производные имеют корень $c$, а $(m-1)$-ая производная не
равна нулю в точке $c$. По предположению индукции $c$~--- корень $f'$
кратности $m-1$. По
теореме~\ref{root_multiplicity_and_derivative_exact} тогда $c$~---
корень $f$ кратности $m$, что и требовалось доказать.
\end{proof}

\subsection{Интерполяция}

\literature{[F], гл. VI, \S~4, пп. 1--3;  [K1], гл. 6, \S~1, п. 2;  [vdW], гл. 5, \S~29.}

\begin{definition}
Пусть $k$~--- поле, $x_1,\dots,x_n\in k$~--- некоторые попарно различные
элементы $k$, и $y_1,\dots,y_n\in k$. \dfn{Интерполяционной
  задачей}\index{интерполяционная задача}
(или \dfn{задачей интерполяции в $n$ точках}) с
данными $(x_1,\dots,x_n;y_1,\dots,y_n)$ мы будем называть задачу
нахождения многочлена $f\in k[x]$ такого, что $f(x_i)=y_i$ для всех
$i=1,\dots,m$.
\end{definition}

\begin{theorem}
Интерполяционная задача имеет не более одного решения среди
многочленов степени, не превосходящей $n-1$. Более того, если $f$,
$g$~--- два решения одной интерполяционной задачи, то $f-g$ делится на
многочлен $(x-x_1)\dots(x-x_n)$.
\end{theorem}
\begin{proof}
Пусть $f,g\in k[x]$~--- два многочлена,
являющихся решениями одной интерполяционной задачи с
данными $(x_1,\dots,x_n;y_1,\dots,y_n)$. Это означает, что
$f(x_i)=y_i=g(x_i)$ для всех $i=1,\dots,n$. Рассмотрим многочлен
$h=f-g$; тогда $h(x_i)=f(x_i)-g(x_i)=0$ для всех $i$. Все $x_i$
различны, поэтому у многочлена $h$ есть $n$ различных корней
$x_1,\dots,x_n$. По предложению~\ref{prop_linear_factors} из этого
следует, что $h$ делится на $(x-x_1)\dots(x-x_n)$. В частности, если
$f$ и $g$ были многочленами степени не выше $n-1$, то и степень $h$ не
превосходит $n-1$, откуда $h=0$ и $f=g$.
\end{proof}

\begin{remark}
У многочлена степени $n-1$ ровно $n$ коэффициентов; неформально
говоря, эти $n$ <<степеней свободы>> фиксируются выбором его значений
в $n$ точках.
\end{remark}

Сейчас мы покажем, что всякая задача интерполяции в $n$ точках имеет решение,
являющееся многочленом степени не выше $n-1$ (и, стало быть, имеет
единственное решение среди многочленов такой степени). Мы явно
построим по данным интерполяционной задачи нужный многочлен нужной
степени, и даже двумя способами: Лагранжа и Ньютона.

Пусть $(x_1,\dots,x_n;y_1,\dots,y_n)$~--- фиксированная
интерполяционная задача. Обозначим
$$
\ph_i=(x-x_1)\dots\widehat{(x-x_i)}\dots(x-x_n);
$$
здесь знак $\widehat{}$ над скобкой означает, что соответствующий
множитель нужно пропустить. Более формально,
$$
\ph_i=\prod_{\substack{1\leq j\leq n\\j\neq i}}(x-x_j).
$$
Отметим, что $\ph_i$ является многочленом степени $n-1$, а его
корни~--- элементы $x_1,\dots,\widehat{x_i},\dots,x_n$.

Посмотрим теперь на многочлен $\ph_i/\ph_i(x_i)$. Эта запись имеет
смысл, поскольку $\ph_i(x_i)\neq 0$. Указанный многочлен принимает
значение $1$ в точке $x_i$ и значения $0$ во всех остальных точках из
набора $x_1,\dots,x_n$.

Наконец, рассмотрим сумму $f=\sum_{i=1}^n
y_i\ph_i/\ph_i(x_i)$. При подстановке $x_i$ в многочлен $f$ все
слагаемые, кроме $y_i\ph_i/\ph_i(x_i)$, обратятся в $0$, а указанное
слагаемое примет значение $y_i$. Значит, указанный многочлен является
решением нашей интерполяционной задачи. Кроме того, степень $f$ не
превосходит $n-1$, поскольку степень каждого $\ph_i$ равна $n-1$.

Выпишем его еще раз:
$$
f=\sum_{i=1}^n y_i\frac{(x-x_1)\dots\widehat{(x-x_i)}\dots(x-x_n)}{(x_i-x_1)\dots
  \widehat{(x_i-x_i)}\dots(x_i-x_n)}.
$$
Многочлен $f$ называется \dfn{интерполяционным многочленом
  Лагранжа}\index{интерполяционный многочлен!Лагранжа}.

Обратимся теперь ко второму способу, который носит название
\dfn{интерполяционного многочлена
  Ньютона}\index{интерполяционный многочлен!Ньютона}. Он решает ту же самую
задачу интерполяции в $n$ точках и имеет степень не выше $n-1$;
конечно, из единственности решения следует, что он совпадает с
интерполяционным многочленом Лагранжа и отличается лишь формой
записи. Форма Ньютона удобна, когда добавление новых точек к
интерполяционной задаче происходит последовательно.

А именно, мы построим серию многочленов $f_1,f_2,\dots,f_n$ таких, что
многочлен $f_i$ имеет степень не выше $i-1$ и решает задачу
интерполяции в $i$ точках с данными
$(x_1,\dots,x_i;y_1,\dots,y_i)$. Построении будет происходить по
индукции: мы опишем, как строить $f_1$ и как по многочлену $f_i$
строить многочлен $f_{i+1}$; очевидно, что $f_n$ будет решением
исходной интерполяционной задачи.

Задача интерполяции в одной точке проста~--- в качестве многочлена
$f_1$, принимающего значение $y_1$ в точке $x_1$, можно взять
константу: $f_1=y_1$~--- это действительно многочлен степени не выше
$0$, что и требовалось.
Предположим теперь, что многочлен $f_i$ построен, то есть,
$f_j(x_j)=y_j$ для всех $j=1,\dots,i$, и $\deg(f_i)\leq i-1$. Как
построить $f_{i+1}$? Будем искать его в виде
$f_{i+1}=f_i+c_{i+1}(x-x_1)\dots(x-x_i)$, где $c_{i+1}\in k$~--- некоторая
константа. Это гарантирует нам, что значения
$f_i$ в точках $x_1,\dots,x_i$ не испортятся: добавка $c_{i+1}(x-x_1)\dots
(x-x_i)$ обращается в $0$ в этих точках. Это означает, что
$f_{i+1}(x_j)=y_j$ для $j=1,\dots,i$. Кроме того, степень $f_{i+1}$ не
превосходит $i$. Осталось добиться выполнения условия
$f_{i+1}(x_{i+1})=y_{i+1}$ подбором константы $c_{i+1}$.
То есть, нам нужно, чтобы
$f_i(x_{i+1})+c_{i+1}(x_{i+1}-x_1)\dots(x_{i+1}-x_i)=y_{i+1}$. Отсюда
легко находится $c_{i+1}$:
$$
c_{i+1}=\frac{y_{i+1}-f_i(x_{i+1})}{(x_{i+1}-x_1)\dots(x_{i+1}-x_i)}.
$$
Заметим, что знаменатель этой дроби~--- ненулевая константа.

Таким образом, интерполяционный многочлен Ньютона является многочленом
$f_n$ в последовательности
\begin{align*}
f_1&=y_1;\\
f_2&=f_1+\frac{y_2-f_1(x_2)}{x_2-x_1};\\
f_3&=f_2+\frac{y_3-f_2(x_3)}{(x_3-x_1)(x_3-x_2)};\\
&\vdots\\
f_n&=f_{n-1}+\frac{y_n-f_{n-1}(x_n)}{(x_n-x_1)\dots(x_n-x_{n-1})}.
\end{align*}

\subsection{НОД и неприводимость}\label{ssect:polynomial_gcd}

\literature{[F], гл. VI, \S~1, пп. 3--6; [K1], гл. 5, \S~3, п. 1--2.}

Продолжим построение теории делимости в кольце многочленов,
параллельной теории делимости в кольце целых чисел. Начиная с этого
места, мы будем рассматривать многочлены над полем $k$.

\begin{definition}
Пусть $f,g\in k[x]$. Многочлен $d$ называется \dfn{общим
  делителем}\index{общий делитель!многочленов}
многочленов $f$ и $g$, если $d\divides f$ и $d\divides g$.
\end{definition}

\begin{definition}
Пусть $f,g\in k[x]$. Многочлен $d$ называется \dfn{наибольшим общим
  делителем}\index{наибольший общий делитель!многочленов} многочленов
$f$ и $g$ (обозначение: $d=\gcd(f,g)$), если
\begin{enumerate}
\item $d$~--- общий делитель $f$ и $g$;
\item если $d'$~--- еще какой-нибудь общий делитель $f$ и $g$, то
  $d'\divides d$.
\end{enumerate}
\end{definition}

\begin{remark}
Сразу же заметим, что если $d$ и $d'$~--- два наибольших общих
делителя многочленов $f$ и $g$, то по определению имеем $d\divides d'$ и
$d'\divides d$; это означает, что многочлены $d$ и $d'$ ассоциированы, то
есть, отличаются домножением на ненулевую константу. В кольце целых
чисел у каждого элемента не более двух ассоциированных~--- он сам и
противоположный к нему, и поэтому можно выбрать из них
неотрицательный, и считать его наибольшим общим делителем. В кольце
многочленов неизвестно, какой из (возможного) множества
ассоциированных выбирать;
можно, конечно, всегда выбирать многочлен со старшим коэффициентом
$1$, но мы этого не будем делать, и будем говорить, что $\gcd$
многочленов {\em определен с точностью до ассоциированности}.
\end{remark}

% 26.11.2014

\begin{theorem}\label{thm_gcd_polynomials}
Наибольший общий делитель многочленов $f,g\in k[x]$ существует,
определен однозначно с точностью до ассоциированности, и может быть
представлен в виде
$\gcd(f,g)=u_0f+v_0g$ для некоторых $u_0,v_0\in k[x]$
\end{theorem}
\begin{proof}
Заметим, что $\gcd(0,g)=g$, поэтому можно считать, что $f\neq 0$ и
$g\neq 0$. Рассмотрим множество $I$ многочленов вида $uf+vg$ для
всевозможных $u,v\in k[x]$ и выберем из них ненулевой многочлен
$d=u_0f+v_0g$ наименьшей степени (возможно, таких несколько~---
возьмем любой из
них). Мы утверждаем, что $d$ является наибольшим общим делителем $f$ и
$g$. Поделим $f$ на $d$ с остатком: $f=dh+r$, где
$\deg(r)<\deg(d)$. Тогда $r=f-dh=f-(u_0f+v_0g)h=(1-u_0h)f+(-v_0h)g$
лежит в $I$ и имеет меньшую степень; поэтому $r=0$, то есть, $f$
делится на $d$. Аналогично, $g$ делится на $d$. Это означает, что
$d$~--- общий делитель $f$ и $g$. Если же $h$~--- какой-то общий
делитель $f$ и $g$, то и $d=u_0f+v_0g$ делится на $h$.
\end{proof}

\begin{remark}
Представление из теоремы~\ref{thm_gcd_polynomials} называется, как и в
случае целых чисел, \dfn{линейным представлением наибольшего общего
  делителя}\index{линейное представление НОД!многочленов}.
\end{remark}

Совершенно аналогично случаю целых чисел происходит и \dfn{алгорифм
  Эвклида}\index{алгорифм Эвклида} в кольце многочленов: единственное
отличие состоит в том,
что при каждом шаге алгорифма убывает не модуль числа, а степень
многочлена:

\begin{lemma}
Если $f=gq+r$ для $f,g\in k[x]$, то $\gcd(f,g)=\gcd(g,r)$.
\end{lemma}
\begin{proof}
Пусть $d=\gcd(f,g)$; тогда $r=f-gq$ делится на $d$, и если $h$~---
некоторый общий делитель $g$ и $r$, то $f=gq+r$ делится на $h$,
поэтому $h$ является общим делителем $f$ и $g$, и по определению
наибольшего общего делителя должно выполняться $h\divides d$. Поэтому
$d$ является и наибольшим общим делителем $g$ и $r$.
\end{proof}

Теперь для того, чтобы найти $\gcd(f,g)$, можно считать, что
$\deg(f)\geq\deg(g)$ и $g\neq 0$.
Запишем $f=gq_1+r_1$ и заметим, что
$\gcd(f,g)=\gcd(g,r_1)$, причем $\gcd(r_1)<\gcd(g)$, поэтому можно
перейти от пары $(f,g)$ к паре $(g,r_1)$ и повторить операцию:
\begin{align*}
f&=gq_1+r_1\\
g&=r_1q_2+r_2\\
r_1&=r_2q_3+r_3\\
&\dots
\end{align*}
Процесс не может продолжаться бесконечно, поскольку степень остатка
убывает. Стало быть, он остановится, когда очередной остаток окажется
равным $0$; если $r_n$~--- последний ненулевой остаток, то
$\gcd(f,g)=\gcd(g,r_1)=\gcd(r_1,r_2)=\dots=\gcd(r_{n-1},r_n)=\gcd(r_n,0)=r_n$.

Уточним степени
многочленов, входящих в линейное представление НОД из
теоремы~\ref{thm_gcd_polynomials}:
\begin{proposition}
Пусть $f,g\in k[x]$, $d=\gcd(f,g)$, $\deg(f)=m$,
$\deg(g)=n$. Существуют многочлены $u_0,v_0\in k[x]$ такие, что
$\deg(u_0)<n$, $\deg(v_0)<m$, и $d=u_0f+v_0g$.
\end{proposition}
\begin{proof}
Без ограничения общности можно считать, что $m\leq n$.
По теореме~\ref{thm_gcd_polynomials} найдутся {\it какие-то}
$u'_0,v'_0\in k[x]$ такие, что $d=u'_0f+v'_0g$. Поделим $u'_0$ с
остатком на $g$: $u'_0=gq+r$. Тогда $d=u'_0f+v'_0g=(gq+r)f+v'_0g=
rf+(v'_0-qf)g$. Положим $u_0=r$, $v_0=v'0-qf$. Мы знаем, что
$\deg(u_0)<\deg(g)=n$. Наконец, $v_0g=d-u_0f$, причем
$\deg(d)<\deg(f)=m$ и
$\deg(u_0f)=\deg(u_0)+\deg(f)< n+m$; поэтому
$n+m>\deg(v_0g)=\deg(v_0)+\deg(g)=\deg(v_0)+n$ и $\deg(v_0)<m$, что и
требовалось.
\end{proof}

Наконец, определим аналоги простых чисел в кольце многочленов.

\begin{definition}
Многочлен $p\in k[x]$ называется
\dfn{неприводимым}\index{многочлен!неприводимый}, если $p$
ненулевой, необратимый, и из того, что
$p=fg$ для $f,g\in k[x]$, следует, что $f$ ассоциировано с $p$ или $g$
ассоциировано с $p$.
\end{definition}

\begin{lemma}
Пусть $f,g,p\in k[x]$ и $p$ неприводим. Если $p\divides fg$, то
$p\divides f$ или $p\divides g$.
\end{lemma}
\begin{proof}
Если $f$ не делится на $p$, то $\gcd(f,p)=1$. Запишем $1=u_0f+v_0p$ и
домножим это равенство на $g$: $g=u_0fg+v_0pg$. По условию $fg$
делится на $p$, поэтому оба слагаемых в правой части делятся на $p$,
поэтому и $g$ делится на $p$.
\end{proof}

\begin{theorem}
Любой ненулевой необратимый многочлен $f$ из $k[x]$ представляется в
виде $f=p_1\dots p_m$, где $p_1,\dots,p_m\in k[x]$~--- неприводимые
многочлены. Более того, такое разложение однозначно с точностью до
порядка сомножителей и замены их на ассоциированные.
\end{theorem}
\begin{proof}
Для доказательства существования~--- индукция по степени многочлена $f$; если $f$
неприводим, доказывать нечего, иначе же запишем $f=gh$ так, чтобы степени
$g$ и $h$ были меньше степени $f$ и воспользуемся индукционным
предположением.

Доказательство единственности проходит точно так же, как в случае
целых чисел (см. теорему~\ref{theorem_ota}), только индукцию снова
нужно вести не по модулю числа, а по степени многочлена.
\end{proof}

% 27.11.2012

\subsection{Поля частных}

\literature{[F], гл. VI, \S~3, пп. 1--2;  [K1], гл. 5, \S~4, п. 1;
  [vdW], гл. 3, \S~13.}

Пусть $R$~--- область целостности
(см. определение~\ref{def:domain}). Сейчас мы расширим кольцо $R$ до
поля естественным образом. Эта конструкция совершенно аналогична
переходу от целых чисел к рациональным: рациональное число можно
считать дробью, в числителе и знаменателе которой стоят целые
числа. Первая проблема, которую нужно побороть~--- неоднозначность
представления в виде дроби: например, дроби $4/6$, $(-2)/(-3)$ и $2/3$
обозначают одно и то же рациональное число.

Рассмотрим множество $R\times
(R\setminus\{0\})$ и введем на нем следующее отношение: пара
$(a,s)$ считается эквивалентной паре $(b,t)$ тогда и только тогда,
когда $at=bs$ в $R$. Мы будем использовать обычное обозначение для
этого отношения: $(a,s)\sim (b,t)$

\begin{lemma}
Это отношение эквивалентности на $R\times(R\setminus\{0\})$.
\end{lemma}
\begin{proof}
Рефлексивность: $(a,s)\sim (a,s)$, поскольку $as=as$.
Симметричность: если $(a,s)\sim (b,t)$, то $at=cs$, откуда $(b,t)\sim
(a,s)$.
Транзитивность: если $(a,s)\sim (b,t)$ и $(b,t)\sim (c,u)$, то $at=bs$
и $bu=ct$. Поэтому $atu=bsu=cts$, откуда $t(au-cs)=0$ и, поскольку
$t\neq 0$, а $R$~--- область целостности, получаем $au=cs$, что
означает, что $(a,s)\sim (c,u)$.
\end{proof}

Фактор-множество $R\times (R\setminus\{0\})$ по указанному отношению
эквивалентности мы будем обозначать через $\Frac(R)$, а класс пары
$(a,s)$ в $\Frac(R)$ будем обозначать через $\frac{a}{s}$ и называть
\dfn{дробью}\index{дробь}.
Теперь введем на полученном множестве операции по образу и подобию
операций над рациональными числами:
\begin{align*}
\frac{a}{s}+\frac{b}{t}&=\frac{at+bs}{st};\\
\frac{a}{s}\cdot\frac{b}{t}&=\frac{ab}{st}.
\end{align*}
Как всегда при введении операций на фактор-множестве, эта запись a
priori содержит неоднозначность, которую нужно разрешить, проверив
{\it корректность} введенных операций.

Сначала разберемся с произведением: мы определили произведение двух
классов $x,y\in\Frac(R)$ с помощью выбора представителей: если
$(a,s)$~--- представитель класса $x$, а $(b,t)$~--- представитель
класса $y$, мы определили $xy$ как класс, содержащий пару
$(ab,st)$. Для начала заметим, что $st\neq 0$ (поскольку $R$~---
область целостности), поэтому эта пара действительно лежит в $R\times
(R\setminus\{0\})$. Что будет, если мы выберем других
представителей? Пусть, действительно, $(a', s')$~--- еще одна пара из
класса $x$, а $(b', t')$~--- пара из класса $y$. Это означает, что
$(a,s)\sim (a',s')$ и $(b,t)\sim(b',t')$. Верно ли, что пары
$(ab,st)$ и $(a'b',s't')$ попали в один класс? Проверим это:
нам дано $as'=a's$ и $bt'=b't$, а хочется проверить, что
$abs't'=a'b'st$. Для этого нужно лишь перемножить два данных
равенства.

Далее, мы определили сумму двух классов $x$ и $y$ так: если
$(a,s)$~--- представитель класса $x$, а
$(b,t)$~--- представитель класса $y$, мы определили $x+y$ как класс,
содержащий пару $(at+bs,st)$. Что будет при выборе других
представителей? Пусть снова $(a', s')$~--- еще одна пара из 
класса $x$, а $(b', t')$~--- пара из класса $y$, то есть,
$(a,s)\sim (a',s')$ и $(b,t)\sim(b',t')$. Верно ли, что пары
$(at+bs,st)$ и $(a't'+b's',s't')$ попали в один класс? Нам дано
нам дано $as'=a's$ и $bt'=b't$, а хочется проверить, что
$(at+bs)s't'=(a't'+b's')st$.
Но из $as'=a's$ следует $as'tt'=a'stt'$, а из $bt'=b't$ следует
$bss't'=b'ss't$, и сложением получаем $as'tt'+bss't'=a'stt'+b'ss't$,
то есть, $(at+bs)s't'=(a't'+b's')st$, что и требовалось.

Операции на $\Frac(R)$ определены, осталось проверить, что получилось поле.

\begin{theorem}
Пусть $R$~--- область целостности.
Множество $\Frac(R)$ с введенными выше операциями является полем.
\end{theorem}
\begin{definition}
$\Frac(R)$ называется \dfn{полем частных}\index{поле!частных} области целостности $R$.
\end{definition}
\begin{proof}[Доказательство теоремы]
\begin{enumerate}
\item Ассоциативность сложения:
  $(\frac{a}{s}+\frac{b}{t})+\frac{c}{u}=\frac{at+bs}{st}+\frac{c}{u}=\frac{(at+bs)u+cst}{stu}$,
  $\frac{a}{s}+(\frac{b}{t}+\frac{c}{u})=\frac{a}{s}+\frac{bu+ct}{tu}=\frac{atu+(bu+ct)s}{stu}$,
  что то же самое.
\item Нейтральный элемент по сложению~--- дробь
  $\frac{0}{1}$. Действительно, $\frac{a}{s}+\frac{0}{1}=\frac{a\cdot
    1+0\cdot s}{s\cdot 1}=\frac{a}{s}$; перемножение в другом порядке
  можно опустить в силу коммутативности (см. пункт 4). Заметим, что
  $\frac{0}{1}=\frac{0}{s}$ для любого $s\in R\setminus\{0\}$.
\item Противоположной дробью к $\frac{a}{s}$ будет дробь
  $\frac{-a}{s}$:
  $\frac{a}{s}+\frac{-a}{s}=\frac{as+(-a)s}{s\cdot s}=\frac{0}{s\cdot s}=\frac{0}{1}$.
\item Коммутативность сложения:
  $\frac{a}{s}+\frac{b}{t}=\frac{at+bs}{st}$,
  $\frac{b}{t}+\frac{a}{s}=\frac{bs+at}{st}$.
\item Ассоциативность умножения:
  $(\frac{a}{s}\cdot\frac{b}{t})\cdot\frac{c}{u}
=\frac{ab}{st}\cdot\frac{c}{u}=\frac{abc}{stu}=\frac{a}{s}\cdot\frac{bc}{tu}
=\frac{a}{s}(\frac{b}{t}\cdot\frac{c}{u})$.
\item Нейтральный элемент по умножению~--- дробь
  $\frac{1}{1}$. Действительно,
  $\frac{a}{s}\cdot\frac{1}{1}=\frac{a\cdot 1}{s\cdot
    1}=\frac{a}{s}$. Заметим, что $\frac{1}{1}=\frac{s}{s}$ для любого
  $s\in R\setminus\{0\}$.
\item Коммутативность умножения:
  $\frac{a}{s}\cdot\frac{b}{t}=\frac{ab}{st}
=\frac{b}{t}\cdot\frac{a}{s}$.
\item Аксиома поля: у каждой дроби $\frac{a}{s}\neq 0$ есть обратный
  элемент по умножению. Заметим, что если $a=0$, то
  $\frac{a}{s}=0$. Поэтому $a\neq 0$ и можно рассмотреть дробь
  $\frac{s}{a}$, которая и будет обратной:
  $\frac{a}{s}\cdot\frac{s}{a}=\frac{as}{as}=\frac{1}{1}=1$.
\end{enumerate}
Осталось заметить, что в полученном кольце $\Frac(R)$ выполнено
условие $0\neq 1$: условие $\frac{0}{1}=\frac{1}{1}$ означало бы, что
$0\cdot 1=1\cdot 1$ в $R$, то есть, $0=1$, что невозможно, поскольку
$R$~--- область целостности.
\end{proof}

Отметим теперь, что кольцо $R$ можно считать лежащим в поле
$\Frac(R)$: каждому элементу $a\in R$ можно сопоставить дробь
$\frac{a}{1}$; при этом разным элементам $R$ сопоставляются разные
дроби, поскольку из $\frac{a}{1}=\frac{b}{1}$ следует $a\cdot 1=b\cdot
1$, то есть, $a=b$. Сложение и умножение полученных дробей выглядит
так же, как сложение и умножение в $R$:
$\frac{a}{1}+\frac{b}{1}=\frac{a+b}{1}$,
$\frac{a}{1}\cdot\frac{b}{1}=\frac{ab}{1}$.
Таким образом, можно считать, что мы расширили $R$ и у каждого
ненулевого элемента $s\in R$ в новом кольце $\Frac(R)$ оказался
обратный: дробь $\frac{1}{s}$.

\begin{example}
Из конструкции очевидно, что $\Frac(\mb Z)=\mb Q$.
\end{example}

\subsection{Поле рациональных функций}

\literature{[F], гл. VI, \S~3, пп. 1--5, 7;  [K1], гл. 5, \S~2,
  п. 2--3;  [vdW], гл. 5, \S~36.}

\begin{definition}
Применим конструкцию поля частных к кольцу многочленов $k[x]$ над
полем $k$. Полученное поле $\Frac(k[x])$ называется
\dfn{полем рациональных функций (над $k$)}\index{поле!рациональных
  функций} и обозначается через $k(x)$.
\end{definition}

Таким образом, поле рациональных функций состоит из дробей вида $\frac{f}{g}$,
где $f,g$~--- многочлены (с учетом отношения эквивалентности), которые
складываются и перемножаются как привычные дроби. Исходное кольцо
$k[x]$ мы трактуем как подмножество $k(x)$, состоящее из дробей вида
$\frac{f}{1}$.

\begin{remark}
Слово <<функция>> в термине <<поле рациональных функций>> несколько
обманчиво: мы уже убедились, что не стоит отождествлять многочлен
$f\in k[x]$ с функцией $k\to k$, $c\mapsto f(c)$. Точно так же, можно
попытаться сопоставить рациональной функции $\frac{f}{g}\in k(x)$
отображение $k\to k$, $c\mapsto f(c)/g(c)$, однако она не определена
в точках $c$, для которых $g(c)=0$; кроме этого, у разных
представителей класса дроби $f/g$ будут разные области определения:
например, дробь $\frac{1}{x-1}$ не определена в точке $1$, а равная ей
дробь $\frac{x}{x(x-1)}$ не определена в точках $0$ и $1$. Может
оказаться, что указанное отображение не определено вообще ни в одной
точке: для поля $k=\mb Z/p\mb Z$ знаменатель дроби $\frac{1}{x^p-x}$,
например, обращается в $0$ во всех точках $c\in k$. Это показывает,
что с подстановкой значений в дроби нужно быть предельно
аккуратным.
\end{remark}

\begin{definition}
Рациональная функция $\frac{f}{g}\in k(x)$ называется
\dfn{правильной}\index{правильная дробь}, если $\deg(f)<\deg(g)$
\end{definition}

\begin{lemma}
Это определение корректно, то есть, не зависит от выбора
представителей: если
$\frac{f}{g}=\frac{\widetilde{f}}{\widetilde{g}}$, и
$\deg(f)<\deg(g)$, то $\deg(\tld{f})<\deg(\tld{g})$.
\end{lemma}
\begin{proof}
Если $\frac{f}{g}=\frac{\tld{f}}{\tld{g}}$, то $f\tld{g}=\tld{f}g$,
поэтому $\deg(f)+\deg(\tld{g})=\deg(\tld{f})+\deg(g)$.
\end{proof}

\begin{lemma}\label{lem_sum_of_proper}
Сумма, разность и произведение правильных дробей~--- правильные дроби.
\end{lemma}
\begin{proof}
Пусть $\frac{f}{g}$ и $\frac{\tld{f}}{\tld{g}}$~--- правильные
дроби, то есть, $\deg(f)<\deg(g)$ и $\deg(\tld{f})<\deg(\tld{g})$. Тогда
$\frac{f}{g}+\frac{\tld{f}}{\tld{g}}=\frac{f\tld{g}+\tld{f}g}{g\tld{g}}$.
При этом $\deg(f\tld{g})<\deg(g\tld{g})$ и
$\deg(\tld{f}g)<\deg(g\tld{g})$, поэтому и полученная сумма является
правильной дробью. Для случая разности достаточно заметить, что
противоположная дробь к правильной дроби также является
правильной. Наконец, $\deg(f\tld{f})<\deg(g\tld{g})$, поэтому и
произведение $\frac{f\tld{f}}{g\tld{g}}$ является правильной дробью.
\end{proof}

\begin{lemma}\label{lem:proper_fraction_is_not_poly}
Если многочлен равен правильной дроби, то он нулевой.
\end{lemma}
\begin{proof}
Предположим, что $f\in k[x]$~--- некоторый многочлен,
$\psi = \frac{g}{h} \in k(x)$~--- правильная дробь (здесь $g,h\in
k[x]$),
и $f=\psi$. Равенство $f = \frac{g}{h}$ означает, что
$fh = g$, и поэтому $\deg(g) = \deg(f) + \deg(h)$. С другой стороны,
по определению правильной дроби $\deg(g) < \deg(h)$.
Поэтому $\deg(f) < 0$, то есть, $f=0$.
\end{proof}

\begin{proposition}\label{prop_sum_poly_and_proper}
Любую рациональную функцию $\ph\in k(x)$ можно единственным образом
представить в виде суммы многочлена и правильной рациональной функции:
$\ph=f+\psi$, где $f\in k[x]$, $\psi\in k(x)$, и если
$\ph=\tld{f}+\tld{\psi}$, то $f=\tld{f}$ и $\psi=\tld{\psi}$. Более
того, знаменатель $\psi$ можно взять равным знаменателю $\ph$, то
есть, если $\ph=\frac{a}{b}$ для некоторых $a,b\in k[x]$, то
$\psi=\frac{c}{b}$ для некоторого $c\in k[x]$.
\end{proposition}
\begin{proof}
Запишем $\ph=\frac{a}{b}$ для некоторых $a,b\in k[x]$, $b\neq 0$. Поделим $a$ на
$b$ с остатком: $a=bq+r$,  где $q,r\in k[x]$ и $\deg(r)<\deg(b)$. Тогда
$\ph=\frac{a}{b}=\frac{bq+r}{b}=\frac{bq}{b}+\frac{r}{b}=\frac{q}{1}+\frac{r}{b}=q+\frac{r}{b}$,
и дробь $\frac{r}{b}$ правильная.
Докажем единственность:
пусть $f+\psi=\tld{f}+\tld{\psi}$,
тогда $f-\tld{f}=\tld{\psi}-\psi$. В левой части этого равенства стоит
многочлен, в правой~--- правильная дробь (по лемме~\ref{lem_sum_of_proper});
из леммы~\ref{lem:proper_fraction_is_not_poly} следует,
что $f - \tld{f}=0$, то есть, $f=\tld{f}$ и $\psi = \tld{\psi}$.
Заметим, наконец, что в нашем построении знаменатель $\psi$ равен
знаменателю $\phi$.
\end{proof}

Выделение многочлена является первым шагом на пути к выявлению
структуры поля рациональных функций.

\begin{definition}
Рациональная функция $\psi\in k(x)$ называется
\dfn{простейшей}\index{простейшая дробь}, если ее можно представить в
виде
$\psi=\frac{f}{p^m}$, где $f,p\in k[x]$, $p$~--- неприводимый
многочлен, $m\geq 1$~--- натуральное число, и $\deg(f)<\deg(p)$.
\end{definition}

Наша цель~--- доказать, что любая правильная рациональная функция
представляется  (в некотором смысле единственным образом) в виде суммы
простейших.

\begin{lemma}\label{prop_coprime_denominators}
Пусть $\frac{f}{gh}\in k(x)$~--- правильная рациональная функция, и
многочлены $g,h\in k[x]$ взаимно просты: $\gcd(g,h)=1$.. Тогда
$\frac{f}{gh}$ можно представить в виде
$\frac{f}{gh}=\frac{a}{g}+\frac{b}{h}$, где
$\frac{a}{g},\frac{b}{h}\in k(x)$~--- правильные рациональные
функции.
\end{lemma}
\begin{proof}
Запишем $ug+vh=1$. Тогда
$\frac{f}{gh}=f\cdot\frac{1}{gh}=f\cdot\frac{ug+vh}{gh}=f\cdot(\frac{ug}{gh}+\frac{vh}{gh})=f\cdot(\frac{u}{h}+\frac{v}{g})=\frac{fv}{g}+\frac{uf}{h}$. В
силу предложения~\ref{prop_sum_poly_and_proper} можно записать дроби
$\frac{fv}{g}$ и $\frac{uf}{h}$ как суммы многочленов и правильных
дробей с теми же знаменателями. Соединяя многочлены вместе, получаем
$\frac{f}{gh}=c+\frac{a}{g}+\frac{b}{h}$, где $a,b,c\in
k[x]$. Наконец, из этого равенство видно, что $c$ является суммой
правильных дробей, то есть, по лемме~\ref{lem_sum_of_proper},
правильной дробью, и из единственности в
предложении~\ref{prop_sum_poly_and_proper}, $c=0$.
\end{proof}

\begin{lemma}\label{lem_proper_irreducible}
Правильную дробь вида $\frac{f}{p^m}$ (здесь $f,p\in k[x]$, $m>1$)
можно записать в виде суммы
$\frac{a_1}{p}+\frac{a_2}{p^2}+\dots+\frac{a_m}{p^m}$, где $a_i\in
k[x]$, $\deg{a_i}<\deg{p}$.
\end{lemma}
\begin{proof}
Индукция по $m$. База $m=1$ очевидна. Переход: пусть $m>1$. Поделим $f$
на $p$ с остатком: $f=pq+r$, $\deg(r)<\deg(p)$. Теперь можно записать
$\frac{f}{p^m}=\frac{pq+r}{p^m}=\frac{pq}{p^m}+\frac{r}{p^m}=\frac{q}{p^{m-1}}+\frac{r}{p^m}$
и по предположению индукции первую дробь можно записать как сумму
дробей, в которых присутствуют знаменатели $p, p^2,\dots,p^{m-1}$, а
числители имеют степень, меньшую степени $p$. Приписывая слагаемое
$\frac{r}{p^m}$, получаем то, что требовалось.
\end{proof}

% 03.12.2014

Наконец, все готово для доказательства главной теоремы.
\begin{theorem}\label{thm_sum_of_simplest}
Пусть $\frac{f}{g}\in k(x)$~--- правильная дробь, $g=p_1^{m_1}\dots
p_s^{m_s}$~--- каноническое разложение $g$ на неприводимые
множители. Тогда $\frac{f}{g}$ можно представить в виде суммы
простейших дробей, в знаменателях которых стоят
$p_1,p_1^2,\dots,p_1^{m_1}$, $p_2,p_2^2,\dots,p_2^{m_2}$,\dots,
$p_s,p_s^2,\dots,p_s^{m_s}$. Кроме того, такое представление
единственно с точностью до порядка, в котором записаны слагаемые.
\end{theorem}
\begin{proof}
По предложению~\ref{prop_coprime_denominators} можно расщепить
знаменатель правильной дроби на два взаимно простых сомножителя;
применяя ее несколько раз, получаем, что
$\frac{f}{g}=\frac{f_1}{p_1^{m_1}}+\dots+\frac{f_s}{p_s^{m_s}}$. Далее,
по лемме~\ref{lem_proper_irreducible}, каждое слагаемое вида
$\frac{f_i}{p_i^{m_i}}$ представляется в виде суммы простейших.

Для доказательства единственности предположим, что сумма простейших
дробей указанного вида равна другой сумме простейших дробей того же
вида. Докажем, что все числители соответствующих дробей в обеих частях
этого равенства совпадают. Предположим противное~--- нашлись
различные числители в дробях с одинаковыми знаменателями в левой и
правой частях. Без ограничения общности (с точности до нумерации
многочленов $p_1,\dots,p_s$) можно считать, что знаменатели этих
дробей~--- степени многочлена $p_1$. Посмотрим на
все дроби в левой и правой части, знаменатели которых~--- степени
$p_1$: пусть в левой части стоит
$\frac{a_1}{p_1}+\frac{a_2}{p_1^2}+\dots+\frac{a_{m_1}}{p_1^{m_1}}$, а
в правой части~---
$\frac{b_1}{p_1}+\frac{b_2}{p_1^2}+\dots+\frac{b_{m_1}}{p_1^{m_1}}$. По
нашему предположению, $a_n\neq b_n$ для некоторого $n$. Рассмотрим
максимальное такое $n$. Тогда
$a_{n+1}=b_{n+1},\dots,a_{m_1}=b_{m_1}$, поэтому дроби
$\frac{a_{n+1}}{p_1^{n+1}},\dots,\frac{a_{n+1}}{p_1^{n+1}}$ в левой
части равны соответственно дробям
$\frac{b_{n+1}}{p_1^{n+1}},\dots,\frac{b_{n+1}}{p_1^{n+1}}$ в правой
части. Вычеркивая эти дроби, получаем равенство вида
$$
\frac{a_1}{p_1}+\frac{a_2}{p_1^2}+\dots+\frac{a_n}{p_1^n}+A=
\frac{b_1}{p_1}+\frac{b_2}{p_1^2}+\dots+\frac{b_n}{p_1^n}+B,
$$
где $A$ и $B$~--- суммы дробей, в знаменателях которых стоит
степени $p_2,\dots,p_s$. При этом, по предположению, $a_n\neq b_n$.
Домножим указанное равенство на $p_1^np_2^{m_2}\dots p_s^{m_s}$:
\begin{align*}
&(a_1p_1^{n-1}+a_2p_1^{n-2}+\dots+a_n)p_2^{m_2}\dots p_s^{m_s} +
Ap_1^np_2^{m_2}\dots p_s^{m_s} =\\ 
&(b_1p_1^{n-1}+b_2p_1^{n-2}+\dots+b_n)p_2^{m_2}\dots p_s^{m_s} +
Bp_1^np_2^{m_2}\dots p_s^{m_s}.
\end{align*}
Это уже равенство многочленов (мы избавились от всех знаменателей).
Раскроем скобки и заметим, что в левой части лишь одно слагаемое не
содержит множитель $p_1$, а именно, $a_np_2^{m_2}\dots
p_s^{m_s}$. Действительно, по предположению, $A$ не содержит
степени $p_1$ в знаменателях, и остальные слагаемые слева (если они
вообще есть) также делятся на $p_1$. Аналогично, в правой части лишь
слагаемое $b_np_2^{m_2}\dots p_s^{m_s}$ не содержит множитель
$p_1$. Поэтому наше равенство принимает вид
$$
a_np_2^{m_2}\dots p_s^{m_s}+(\dots)\cdot p_1 =
b_np_2^{m_2}\dots p_s^{m_s}+(\dots)\cdot p_1.
$$
Значит, разность $a_np_2^{m_2}\dots p_s^{m_s}-b_np_2^{m_2}\dots
p_s^{m_s}=(a_n-b_n)p_2^{m_2}\dots p_s^{m_s}$ делится на $p_1$; однако,
$p_2,\dots,p_s$ взаимно просты с $p_1$, поэтому $a_n-b_n$ делится на
$p_1$. Но мы начинали с суммы простейших дробей, то есть,
$\deg(a_n)<\deg(p_1)$ и $\deg(b_n)<\deg(p_1)$, откуда
$\deg(a_n-b_n)<\deg(p_1)$ и, стало быть, $a_n=b_n$~--- противоречие.
\end{proof}

\begin{corollary}
\begin{enumerate}
\item Любая правильная дробь из $\mb C(x)$ представляется в виде суммы
дробей вида $\frac{a}{(x-c)^m}$, где $a,c\in\mb C$, $m\geq
1$.
\item Любая правильная дробь из $\mb R(x)$ представляется в виде суммы
дробей вида $\frac{a}{(x-c)^m}$, где $a,c\in\mb R$, $m\geq 1$, и
дробей вида
$\frac{cx+d}{(x^2+ax+b)^m}$, где $a,b,c,d\in\mb R$, $a^2-4b<0$, $m\geq
1$.
\end{enumerate}
\end{corollary}
\begin{proof}
Напрямую следует из теоремы~\ref{thm_sum_of_simplest} и теорем
\ref{thm_irreducible_complex}, \ref{thm_irreducible_real}.
\end{proof}

Теорема~\ref{thm_sum_of_simplest} не указывает явного алгоритма
нахождения разложения правильной дроби в сумму простейших. Этот
алгоритм можно извлечь из доказательства
предложения~\ref{prop_coprime_denominators} и
леммы~\ref{lem_proper_irreducible}, но он несколько замысловат:
например, в доказательстве~\ref{prop_coprime_denominators} требуется
умение находить коэффициенты в линейном представлении наибольшего
общего делителя. На практике для нахождения разложения в сумму
простейших хорошо работает метод неопределенных коэффициентов. Кроме
того, можно выписать и явные формулы (конечно, если известно
разложение знаменателя дроби на неприводимые многочлены). Приведем
формулы для простейшего случая: рациональной функции над комплексными
числами, знаменатель которой не имеет кратных корней.

\begin{proposition}
Пусть $\frac{f}{g}\in\mb C(x)$~--- правильная дробь, и $g=(x-c_1)\dots
(x-c_n)$, где $c_1,\dots,c_n\in\mb C$~--- попарно различные числа.
Тогда $\frac{f}{g}=\frac{a_1}{x-c_1}+\dots+\frac{a_n}{x-c_n}$, где
$a_i=f(c_i)/g'(c_i)$.
\end{proposition}
\begin{proof}
По теореме~\ref{thm_sum_of_simplest} существует разложение вида
$\frac{f}{g}=\sum_{i=1}^n\frac{a_i}{x-c_i}$; осталось
найти коэффициенты $a_j$ для всех $j$.
Домножим это равенство на $g$:
$$
f=\sum_{i=1}^n a_i(x-c_1)\dots\widehat{(x-c_i)}\dots(x-c_n)
$$
(напомним, что крышечка над множителем означает, что его нужно
пропустить в произведении).
Подставим $c_j$; все слагаемые справа, кроме $j$-го, содержат
множитель $(x-c_j)$, поэтому обращаются в нуль. Значит,
$$
f(c_j)=a_j(c_j-c_1)\dots\widehat{(c_j-c_j)}\dots(c_j-c_n).
$$

Посмотрим теперь на производную многочлена
$g=(x-c_1)\dots(x-c_n)$:
\begin{align*}
g'&=((x-c_j)(x-c_1)\dots\widehat{(x-c_j)}\dots(x-c_n))'\\
&=(x-c_j)'(x-c_1)\dots\widehat{(x-c_j)}\dots(x-c_n)+
 (x-c_j)((x-c_1)\dots\widehat{(x-c_j)}\dots(x-c_n))'.\\
&=(x-c_1)\dots\widehat{(x-c_j)}\dots(x-c_n)+
 (x-c_j)((x-c_1)\dots\widehat{(x-c_j)}\dots(x-c_n))'.
\end{align*}
Наконец, подставим $c_j$, и второе слагаемое обратится в $0$:
$g'(c_j)=(c_j-c_1)\dots\widehat{(c_j-c_j)}\dots(c_j-c_n)$.
Сравнивая с полученным выше выражением для $f(c_j)$, получаем, что
$f(c_j)=a_jg'(c_j)$, откуда $a_j=f(c_j)/g'(c_j)$, что и требовалось.
\end{proof}