\documentclass{../../common/topic}

\TopicSetup
{
  number=3,
  title={Полиноми на една променлива. Теорема за деление с остатък. Най-голям общ делител на полиноми - тъждество на Безу и алгоритъм на Евклид. Зависимост между корени и коефициенти на полиноми (формули на Виет).},
  basedate={15 юни 2019},
  author={Янис Василев}
}

% Packages
\usepackage{polynom} % Polynomial long division

% Bibliography
\addbibresource{./references.bib}

\begin{document}

\maketitle

\section{Теория}

Някои твърдения и доказателства са заимствани от \cite{Knapp2016BasicAlgebra} и \cite{RoyachkiNotes}.

\subsection{Анотация}

Изложената анотацията е взета от \cite{Syllabus}.

\begin{enumerate}
  \item Полином с коефициенти над поле.
  \item Степен на полином.
  \item Корени на полиноми.
  \item Теорема за деление с остатък.
  \item Схема на Хорнер.
  \item Всеки идеал в \( F[x] \) е главен.
  \item Принцип за сравняване на коефициенти.
  \item Определение на най-голям общ делител на два полинома.
  \item Теорема за съществуване на най-голям общ делител на два полинома с коефициенти над поле.
  \item Изразяване на НОД чрез полиномите (тъждество на Безу).
  \item Алгоритъм на Евклид.
  \item Формули на Виет.
\end{enumerate}

\subsection{Основни понятия}

Нека \( F \) е фиксирано поле. За удобство ще означаваме с \( 0 \) и \( 1 \) съответно нулевият и единичният елемент на полето. Ще дефинираме полиноми като чисто алгебрични обекти вместо като функции. Причината за това е, че ако дефинираме полиноми като функции от вида
\begin{equation*}
  p(x) \coloneqq a_n x^n + a_{n-1} x^{n-1} + \cdots + a_2 x^2 + a_1 x + a_0,
\end{equation*}
тогава в общия случай една и съща функция може да се дефинира по няколко различни начина. Например, в полето \( F_2 \) с два елемента, имаме равенството
\begin{equation*}
  x^2 = x, x \in \set{ 0, 1 },
\end{equation*}
тоест \( x \mapsto x^2 \) и \( x \mapsto x \) съвпадат като функции.

Това ни пречи да говорим без двусмислица за \enquote{степен}, \enquote{старши член}, \enquote{коефициент} на полином и подобни понятия.

\begin{definition}
  \textbf{Полином} \( p \) на една променлива над \( F \) наричаме редица
  \begin{equation*}
    p = (a_0, a_1, \ldots)
  \end{equation*}
  от елементи на \( F \), наречени коефициенти, само краен брой от които са различни от \( 0 \). Ако всички елементи на редицата са нули, наричаме полинома нулев и също както нулевия елемент на полето го бележим с \( 0 \).

  \textbf{Степен \( \deg(p) \)} на полинома \( p \) наричаме най-малкия индекс, след който всички елементи на редицата са \( 0 \). Формално,
  \begin{equation*}
    \deg(p) \coloneqq \min \set[\Big]{ k \in \set{ 0, 1, \ldots } \given* a_{k + m} = 0 \text{ за всички } m = 1, 2, \ldots}.
  \end{equation*}

  По конвенция оставяме степента \( \deg(0) \) на нулевия полином да бъде неопределена, макар и горната дефиниция да ни дава \( \deg(0) = 0 \).

  \textbf{Старшият коефициент} \( \op{LC}(p) \) на полинома \( p \) от степен \( n \) наричаме последната ненулева стойност в редицата от коефициенти и полагаме \( \op{LC}(p) \coloneqq 0 \).

  Полинома \( p \) наричаме \textbf{унитарен}, ако \( \op{LC}(p) = 1 \).
\end{definition}

Нека \( p = (a_0, a_1, \ldots) \) и \( q = (b_0, b_1, \ldots) \) са два полинома. Сума на \( p \) и \( q \) дефинираме покоординатно, т.е.
\begin{equation*}
  (p + q) = (a_0 + b_0, a_1 + b_1, \ldots),
\end{equation*}

а произведението им дефинираме като полинома \( pq = (c_0, c_1, \ldots) \), където:
\begin{equation*}
  c_k = \sum_{i+j=k} a_i b_j.
\end{equation*}

Сумата на ненулеви полиноми \( p + q \) е полином, при това \( p + q \) или е нулевият полином, или \( \deg(p + q) \leq \max(\deg(p), \deg(q)) \). Произведението на ненулеви полиноми е ненулев полином, при това \( \deg(pq) = \deg p + \deg q \).

Полиноми със само един ненулев коефициент наричаме \textbf{мономи}.

Нека сега изберем символ, да речем \( X \), с който ще означаваме монома \( (0, 1, 0, 0, \ldots) \). Забелязваме, че от определението за умножение на полиноми, може да изразим коефициентите \( c_0, c_1, \ldots \) на \( X^2 = X \cdot X \) чрез коефициентите \( a_0, a_1, \ldots \) на \( X \) като
\begin{align*}
  c_0 &= a_0 \cdot a_0 = 0 \\
  c_1 &= a_0 \cdot a_1 + a_1 \cdot a_0 = 0 + 0 = 0 \\
  c_2 &= a_0 \cdot a_2 + a_1 \cdot a_1 + a_2 \cdot a_0 = 0 + 1 + 0 = 1 \\
  c_3 &= a_0 \cdot a_3 + a_1 \cdot a_2 + a_2 \cdot a_1 + a_0 \cdot a_3 = 0 + 0 + 0 + 0 = 0 \\
  c_4 &= \cdots = 0 \\
  c_5 &= \cdots = 0 \\
  \vdots
\end{align*}

По индукция така получаваме, че
\begin{equation*}
  X^k = (\underbrace{0, \ldots, 0}_{k \text{ пъти}}, 1, 0, 0, \ldots).
\end{equation*}

За удобство полагаме \( X^0 \coloneqq 1 \). Това ни позволява да записваме ненулевите полиноми \( p = (a_0, a_1, \ldots) \) от степен \( \deg(p) = n \) като линейна комбинация на мономи:
\begin{equation*}
  p(X) = \sum_{k=0}^n a_k X^k.
\end{equation*}

За променливата сме избрали главна буква, за да подчертаваме, че \( p(X) \) не е функция. Бележим с \( F[X] \) множеството на всички полиноми над \( F \) със свободна променлива \( X \).

Относно въведените операции \( F[X] \) е комутативен пръстен с единица \( 1 \), тъй като
\begin{enumerate}
  \item \( F[X] \) наследява нулата си \( 0 \) и единицата си \( 1 \) от полето \( F \).
  \item Събирането на произволни полиноми наследява асоциативността и комутативността си директно от събирането в полето \( F \).
  \item Ако \( p(X) = \sum_{k=0}^n a_k X^k \), то \( -p(X) = \sum_{k=0}^n (-a_k) X^k \) е обратен на \( p(X) \) относно събиране.
  \item Произведението на ненулеви полиноми \( p = (a_0, a_1, \ldots) \), \( q = (b_0, b_1, \ldots) \) и \( r = (c_0, c_1, \ldots) \) е асоциативно, тъй като
  \begin{equation*}
    \sum_{k+m=n} \parens*{\sum_{i+j=k} a_i b_j } c_m
    =
    \sum_{i+j+m=n} a_i b_j c_m
    =
    \sum_{i+l=n} a_i \parens*{ \sum_{j+m=l} b_j c_m },
  \end{equation*}
  където всички индекси са неотрицателни цели числа.
  \item Произведението на ненулеви полиноми наследява комутативността си и дистрибутивността си относно събирането директно от полето \( F \).
\end{enumerate}

Това ни позволява да разглеждаме \( F \) като подпръстен на \( F[X] \) и да разглеждаме \( F[X] \) като алгебра над полето \( F \).

Нулевият полином и полиномите от степен \( 0 \) наричаме константи и чрез каноничната проекция \( \pi: (a_0, 0, \ldots) \mapsto a_0 \) ги отъждествяваме с първия им коефициент. Аналогично, каноничното влагане \( \iota: a_0 \mapsto (a_0, 0, \ldots) \) влага \( F \) във \( F[x] \).

Нека \( (F \mapsto F) \) е пръстенът от функции над \( F \) с операция композиция. Дефинираме хомоморфизма
\begin{align*}
  &\Phi: F[X] \mapsto (F \mapsto F) \\
  &\Phi\parens*{(a_0, a_1, \ldots, a_n, 0, 0, \ldots) } \coloneqq \parens*{ u \mapsto \sum_{k=0}^n a_k u^k },
\end{align*}
който на всеки полином съпоставя \textbf{полиномиална функция}. Както споменахме по-горе, този хомоморфизъм в общия случай не е инективен. Когато имаме предвид функцията \( x \mapsto \Phi(p)(x) \) вместо редицата от коефициенти \( p \), ще пишем \( p(x) \), като подобно означение ще използваме за стойността \( p(u) \) на функцията \( p(x) \) пресметната в точката \( u \).

\subsection{Делимост на полиноми}

\begin{theorem}[Делене с остатък]\label{thm:polynomial_division}
  \begin{hfuzzpar}{3pt}
    Нека са дадени ненулевите полиноми \( p(X) = \sum_{k=0}^n a_k X^k \) и \( q(X) = \sum_{k=0}^m b_k X^k \), където \( q(X) \neq 0 \). Тогава съществуват единствени полиноми \( s \) и \( r \), където \( r = 0 \) или \( \deg(r) < m \), такива че
    \begin{equation*}
      p = sq + r.
    \end{equation*}
  \end{hfuzzpar}
\end{theorem}
\begin{proof}
  Първо ще докажем единствеността. Нека
  \begin{equation*}
    p = sq + r = \hat sq + \hat r.
  \end{equation*}

  Тогава \( 0 = p - p = (s - \hat s) q + (r - \hat r) \) и \( (s - \hat s) q = \hat r - r \).

  Тъй като \( q \neq 0 \), то \( s - \hat s = 0 \iff \hat r - r = 0 \). Ако сега допуснем, че \( \hat r \neq r \) (и следователно \( \hat s \neq s \)), получаваме, че \( \deg[(s - \hat s) q] = \deg(s - \hat s) + m > m \). Но по условие \( \deg(\hat r - r) \leq \max(\deg \hat r, \deg r) < m \). Тъй като степента на полинома в двете страни на равенството трябва да бъде равна, получаваме противоречие от допускането, че \( \hat r \neq r \). Следователно \( r = \hat r \) и \( s = \hat s \).

  Сега ще докажем съществуване. Ако \( n < m \), полагаме \( s(X) \coloneqq 0 \) и \( r(X) \coloneqq p(X) \). Нека \( n \geq m \). Ще докажем теоремата с индукция по \( n \). Случаят \( n = 0 \) е тривиален, тъй като тогава полагаме \( s(X) \coloneqq \frac {b_0} {a_0} \) и \( r(X) \coloneqq 0 \). Да предположим, че теоремата е вярна за всички полиноми с \( \deg < n \) и да означим \( g(X) \coloneqq \frac {a_n} {b_m} X^{n-m} q(X) \).

  Тъй като \( \deg(p) = \deg(g) \) и \( \op{LC}(p) = \op{LC}(g) \), то \( \deg(p - g) < \deg(p) = n \) и индукционното предположение ни дава полиноми \( \hat s \) и \( \hat r \), такива че \( p - g = \hat s q + \hat r \) и \( \hat r = 0 \) или \( \deg(\hat r) < m \). Но ние имаме
  \begin{equation*}
    p(X)
    =
    g(X) + \hat s(X) q(X) + \hat r(X)
    =
    \parens*{ \frac {a_n} {b_m} X^{n-m} + \hat s(X) } q(X) + \hat r(X).
  \end{equation*}

  Полагаме \( s(X) \coloneqq \hat s(X) + \frac {a_n} {b_m} X^{n-m} \) и \( r(X) \coloneqq \hat r(X) \). Очевидно \( \deg(r) = \deg(\hat r) < m \). С това и съществуването е доказано.
\end{proof}

\begin{definition}
  Казваме, че полиномът \( q \in F[X] \) \textbf{дели} \( p \in F[X] \) и че \( p \) е \textbf{кратен} на \( q \), ако съществува ненулев полином \( s \in F[X] \), такъв че \( p = sq \), т.е. ако алгоритъмът за делене с остатък дава нулев остатък.

  Множеството от всички полиноми, кратни на \( q \), образува идеал \( \braket q \) на пръстена \( F[X] \). \Cref{thm:polynomial_ideals_are_principal} ни казва, че всеки идеал на \( F[X] \) е от този вид.

  Полиномът \( q \) дели \( p \) тогава и само тогава, когато \( p \) да принадлежи на идеала \( \braket q \vartriangleleft F[X] \).
\end{definition}

\begin{theorem}\label{thm:polynomial_ideals_are_principal}
  Всеки идеал в \( F[X] \) е главен.
\end{theorem}
\begin{proof}
  Нулевият идеал \( \braket 0 \vartriangleleft F[X] \) очевидно е главен. Нека \( I \vartriangleleft F[X] \) е ненулев идеал и нека \( q \in I \) е полином от минимална за \( I \) степен. Ще докажем, че идеалът \( \braket q \vartriangleleft F[X] \), породен от \( q \), съвпада с \( I \).

  Нека първо \( p \in \braket q \). Тъй като идеалът \( \braket q \) е устойчив относно умножение, то съществува полином \( s \in F[X] \), за който \( p = sq \). Но тъй като \( q \in I \), то \( p = sq \in I \). Тоест \( \braket q \subseteq I \).

  Нека сега \( p \in I \). Теоремата за делене с остатък ни дава полиноми \( s \) и \( r \) с \( r = 0 \) или \( \deg r < \deg q \), такива че \( p = qs + r \). Но понеже \( I \) е затворен относно събиране, имаме \( r = p - qs \in I \). Ако \( r \) е ненулев, то \( \deg r < \deg q \), което противоречи на минималността на \( q \). Значи \( r = 0 \) и \( p = qs \in \braket q \). Тоест \( I \subseteq \braket q \).

  Доказахме, че \( I = \braket q \). Понеже \( I \) беше произволен ненулев идеал, това означава, че всеки идеал на \( F[X] \) е главен.
\end{proof}

\begin{definition}
  \textbf{Корен} на полинома \( p(X) \) наричаме всяка стойност \( u \in F \), за която съответната функция се анулира, т.е. за която \( p(u) = 0 \).
\end{definition}

\begin{proposition}\label{thm:root_divisor}
  Полиномът \( (X - u) \) дели ненулевия полином \( p(X) \in F[X] \) тогава и само тогава, когато \( u \) е корен на \( p \).
\end{proposition}
\begin{proof}
  \SufficiencySubProof Ако \( (X - u) \) дели \( p(X) \), то \( p(X) \in \braket{(X - u)} \). Тъй като \( u \) е корен на полинома \( (X - u) \), той е корен и на всички полиноми от идеала \( \braket{(X - u)} \) и значи \( u \) е корен на \( p(X) \).

  \NecessitySubProof Нека \( u \) е корен на \( p(X) \).

  \Cref{thm:polynomial_division} ни дава полиноми \( q(X) \) и \( r(X) \), където или \( r(X) = 0 \), или \( \deg r < \deg b \), такива че
  \begin{equation*}
    p(X) = (X - u) q(X) + r(X).
  \end{equation*}

  Да допуснем, че полиномът \( r(X) \) е ненулев. Стойността на \( p(X) \) в \( u \) е
  \begin{equation*}
    0 = p(u) = (u - u) q(r) + r(u) = r(u),
  \end{equation*}
  следователно \( u \) е корен и на \( r(X) \). Но \( \deg r(X) < \deg (X - u) = 1 \), тоест \( r(X) \) е ненулев константен полином и \( r(X) \) не може да има нули. Полученото противоречие доказва твърдението.
\end{proof}

\begin{proposition}\label{thm:root_inexact_divisor}
  За всеки полином \( p(X) \in F[X] \) и за всеки скалар \( u \in F \) съществува полином \( q(X) \) със степен \( \deg q < \deg p \), за който \( p(X) = (X - u) q(X) + p(u) \).
\end{proposition}
\begin{proof}
  Тъй като \( u \) непременно е корен на \( p(X) - p(u) \), по \cref{thm:root_divisor} полиномът \( (X - u) \) дели \( p(X) - p(u) \). Следователно съществува полином \( q(X) \) със степен \( \deg q < \deg p \), такъв че \( p(X) - p(u) = (X - u) q(X) \).
\end{proof}

\begin{proposition}
  Схемата (или правилото) на Хорнер за пресмятане на стойността на ненулевия полином \( p \) в дадена точка се дължи на следното представяне на \( p(X) \):
  \begin{equation*}
    p(X) = \sum_{k=0}^n a_k X^k = a_0 + X \sum_{k=1}^n a_k X^{k-1} = \cdots = a_0 + X (a_1 + \cdots + X(a_{n-1} + X a_n) + \cdots).
  \end{equation*}
\end{proposition}
\begin{proof}
  Формално правилото се основава на следното наблюдение:

  Нека \( u \in F \). Искаме да пресметнем \( p(u) \). От \cref{thm:root_inexact_divisor} знаем, че съществува \( q(X) \), така че

  \begin{equation*}
    p(X) = (X - u) q(X) + p(u).
  \end{equation*}

  Ако \( q(X) \) има представяне \( \sum_{k=0}^{n-1} b_k X^k \), то
  \begin{align*}
    p(X)
    &=
    (X - u) \sum_{k=0}^{n-1} b_k X^k + p(u),
    \\
    \sum_{k=0}^n a_k X^k
    &=
    \sum_{k=0}^{n-1} b_k X^{k+1} - u \sum_{k=0}^{n-1} b_k X^k + p(u),
    \\
    0
    &=
    (p(u) - u b_0 - a_0) + \sum_{k=1}^{n-1} (b_{k-1} - u b_k - a_k) X^k + (b_{n-1} - a_n) X^n
  \end{align*}

  Като приравним коефициентите пред съответните едночлени, получаваме следната рекурентна зависимост за коефициентите \( b_k, k = 0, \ldots, n - 1 \):
  \begin{align*}
    \begin{cases}
      p(u) &= u b_0 + a_0 \\
      b_{k-1} &= a_k + u b_k, k = 1, \ldots, n - 1 \\
      b_{n-1} &= a_n.
    \end{cases}
  \end{align*}

  Правилото на Хорнер изисква само \( n \) умножения и \( n \) събирания, докато директното пресмятане на \( p(u) \) изисква \( \frac {n(n+1)} 2 \) умножения и \( n \) събирания.
\end{proof}

\begin{lemma}\label{thm:maximal_number_of_roots}
  Ненулев полином от степен \( n \) има най-много \( n \) корена, броейки кратностите.
\end{lemma}
\begin{proof}
  Ще използваме индукция по степента \( n \). В случая \( n = 0 \) имаме ненулев константен полином, а такъв полином не може да има корени, т.е. има най-много \( 0 \) корени.

  Да допуснем, че твърдението е вярно за \( 1, \ldots, n - 1 \). Нека \( p \in F[X] \) е полином от степен \( n \) и нека \( r \) е негов корен. От \cref{thm:root_divisor} следва, че съществува полином \( q(X) \) от степен \( n - 1 \), такъв че
  \begin{equation*}
    p(X) = (X - r) q(X).
  \end{equation*}

  Фиксираме елемент \( t \in F \), различен от \( r \) и от корените на \( q(X) \). Разглеждаме
  \begin{equation*}
    p(t) = (t - r) q(t).
  \end{equation*}

  Имаме \( (t - r) \neq 0 \) и \( q(t) \neq 0 \). Понеже \( F \) няма делители на нулата, произведението \( p(t) \) на ненулевите елемент \( (t - r) \) и \( q(t) \) също е ненулев елемент. Следователно единствените корени на \( p(X) \) са \( r \) и корените на \( q(X) \).

  По индукционно предположение, \( q(X) \) има най-много \( n - 1 \) корена, броейки кратностите. Следователно \( p(X) \) има най много \( (n - 1) + 1 = n \) корена.
\end{proof}

\begin{theorem}[Принцип за сравняване на коефициентите]\label{thm:coefficient_comparison_principle}
  Нека \( p \) и \( q \) са полиноми от степен \( n \) и нека \( u_0, \ldots, u_n \in F \) са различни скалари (това изисква в полето има поне \( n+1 \) елемента). Ако е изпълнено \( p(u_i) = q(u_i), i = 0, \ldots, n \), то полиномите \( p \) и \( q \) съвпадат.
\end{theorem}
\begin{proof}
  Дефинираме полинома \( r \coloneqq p - q \). Това е полином от степен най-много \( n \), който има \( n + 1 \) корена: стойностите \( u_0, u_1, \ldots, u_n \). Според \cref{thm:maximal_number_of_roots}, това не е възможно за ненулев полином. Тоест \( r = 0 \) и \( p = q \).
\end{proof}

\subsection{Най-голям общ делител на полиноми}

\begin{definition}
  Казваме, че един полином \( d \in F[X] \) е \textbf{най-голям общ делител} (НОД) на \( p \in F[X] \) и \( q \in F[X] \) и пишем \( d = \gcd(p, q) \), ако \( d \) дели \( p \) и \( q \) и ако всеки общ делител на \( p \) и \( q \) дели \( d \). Тъй като всички НОД на \( p \) и \( q \) се различават по умножение с ненулева константа, ако не е казано иначе, за определеност взимаме \( \gcd(p, q) \) да бъде унитарен.

  Казваме, че полиномите \( p \) и \( q \) са \textbf{взаимно прости}, ако \( \gcd(p, q) = 1 \).

  Оставяме НОД на два нулеви полинома да бъде неопределен.
\end{definition}

\begin{theorem}
  За всеки два полинома \( p, q \in F[X] \) съществува единствен с точност до умножение с ненулева константа \( \gcd(p, q) \).
\end{theorem}
\begin{proof}
  От \cref{thm:polynomial_ideals_are_principal} следва, че идеалът \( I = \braket p + \braket q \vartriangleleft F[x] \) е главен, т.е. съществува унитарен полином \( d \in I \), който го поражда.
  Тогава \( d \) е общ делител на \( p \) и \( q \).

  Но \( d \in I \), следователно съществуват полиноми \( u, v \in F[X] \), такива че \( u p + v q = d \).

  Тогава за всеки общ делител \( g \) на \( p \) и \( q \) имаме \( p, q \in \braket g \) и следователно \( d = u p + v q \in \braket g \), т.е. \( g \) дели \( d \). Ако \( \deg g = \deg d \), то те се различават с ненулева константа.

  Тогава \( d \) е най-голям общ делител на \( p \) и \( q \).
\end{proof}

Като част от горното доказателство ние доказахме и следната
\begin{theorem}[Тъждество на Безу]
  За всеки два полинома \( p, q \in F[X] \) съществуват полиноми \( u \) и \( v \), такива че \( u p + v q = \gcd(p, q) \).
\end{theorem}

Ако \( p \) е нулев и \( q \) е ненулев, имаме \( \gcd(p, q) = p \) (и обратно). За ненулеви полиноми имаме явен алгоритъм за намиране на НОД.
\begin{theorem}[Алгоритъм на Евклид]
  Нека \( p \) и \( q \) са произволни ненулеви полиноми.

  Полагаме
  \begin{align*}
     f_{-1} \coloneqq p &&
     f_0 \coloneqq q.
  \end{align*}

  Алгоритъм на Евклид (\( k \)-та стъпка): Деленето с остатък ни дава полиноми \( s \) и \( r \), такива че \( f_{k-2} = p_{k-1} s + r \).
  \begin{enumerate}
    \item Ако \( r = 0 \), алгоритъмът приключва.
    \item Ако \( r \neq 0 \) и \( \deg r < \deg f_{k-1} \), полагаме \( f_k \coloneqq r \) и алгоритъмът преминава към стъпка \( k + 1 \).
  \end{enumerate}

  Твърдим, че така построената редица е крайна с дължина \( m \), при това \( \gcd(p, q) = f_m \).
\end{theorem}
\begin{proof}
  Тъй като построяваме редица със строго намаляващи степени (с евентуално изключение \( \deg f_{-1} < \deg f_0 \)), тази редица непременно е крайна. Нека \( m \) е дължината ѝ.

  С индукция по \( i = 2, \ldots, m + 1 \) ще докажем, че \( f_m \) дели \( f_{m-i} \). Разглеждаме базовия случай \( i = 2 \):
  \begin{enumerate}
    \item \( f_{m-1} = f_m s \) за някой полином \( s \) и значи \( f_m \) дели \( f_{m-1} \).
    \item \( f_{m-2} = f_{m-1} t + f_m = f_m (s t + 1) \) за някой полином \( t \) и значи \( f_m \) дели и \( f_{m-2} \).
  \end{enumerate}

  Сега допускаме, че \( f_m \) дели \( f_{m-j} \) за \( j < i \). Но \( f_{m-i} = f_{m-(i-1)} s + f_{m-(i-2)} \) за някой полином \( s \) и по индукционно предположение \( f_m \) дели \( f_{m-(i-1)} \) и \( f_{m-(i-2)} \), следователно \( f_m \) дели и \( f_{m-i} \).

  В частност, доказахме, че, \( f_m \) дели \( p \) и \( q \).

  Нека сега \( g \) е произволен общ делител на \( p \) и \( q \), т.е. съществуват полиноми \( h_1 \) и \( h_2 \), така че \( p = g h_1 \) и \( q = g h_2 \). Тогава за някой полином \( s \) е изпълнено
  \begin{equation*}
    f_1 = p - qs = g h_1 - g h_2 s = g (h_1 - h_2 s),
  \end{equation*}
  следователно \( g \) дели \( f_1 \). Със същото разсъждение и с индукция по \( i = 1, \ldots, m \) стигаме до извода, че \( g \) дели \( f_i \), в частност \( g \) дели \( f_m \). Следователно \( \gcd(p, q) = f_m \).
\end{proof}

\subsection{Формули на Виет}

\begin{theorem}[Формули на Виет]
  Нека е даден унитарен неконстантен полином \( p(X) = \sum_{k=0}^n a_k X^k \in F[X] \) и нека всичките му корени \( u_1, \ldots, u_n \) (с евентуални повторения) са от \( F \).

  Тогава \( a_n = 1 \) и за \( k = 0, \ldots, n-1 \) имаме следната връзка между коефициентите и корените на полинома \( p \):
  \begin{equation*}
    a_{n-k} = {(-1)}^k \sum_{1 \leq i_1 < \cdots < i_k \leq n} u_{i_1} \ldots u_{i_k}.
  \end{equation*}
\end{theorem}
\begin{proof}
  След като всички корени на \( p \) са във \( F \), то \( p \) се разлага на линейни множители над \( F[X] \), т.е.
  \begin{equation*}
    p(x) = (X - u_1) \cdots (X - u_n).
  \end{equation*}

  Ще докажем теоремата с индукция по \( n = \deg p \). Базовият случай \( n = 1 \) е тривиален, тъй като тогава \( p(X) = (X - u_1) \) и \( a_0 = {(-1)}^1 u_1 = -u_1 \).

  Нека теоремата е вярна за всички полиноми от степен \( n \) и \( p = (X - u_1) \cdots (X - u_{n+1}) \). Полагаме
  \begin{equation*}
    q(X) \coloneqq (X - u_1) \cdots (X - u_n).
  \end{equation*}
  Нека коефициентите на \( q \) са \( q = (b_0, \ldots, b_n) \).

  Индукционното предположение е изпълнено за \( q(X) \) и освен това имаме връзката
  \begin{align*}
    (X - u_{n+1}) q(X)
    &=
    (X - u_{n+1}) \sum_{k=0}^n b_k X^k
    = \\ &=
    \sum_{k=1}^{n+1} b_{k-1} X^k + \sum_{k=0}^n (-u_{n+1}) b_k X^k
    = \\ &=
    (-u_{n+1}) b_0 + \sum_{k=1}^n (b_{k-1} - u_{n+1} b_k) X^k + b_n X^{n+1}
    = \\ &=
    \sum_{k=0}^{n+1} a_k X^k
    =
    p(X).
  \end{align*}

  Като приравним коефициентите пред съответните едночлени, получаваме
  \begin{align*}
    a_0
    &=
    (-u_{n+1}) b_0
    =
    (-u_{n+1}) {(-1)}^n \sum_{1 \leq i_1 < \cdots < i_n \leq n} u_{i_1} \ldots u_n
    =
    {(-1)}^{n+1} u_1 \ldots u_{n+1}
    = \\ &=
    {(-1)}^n \sum_{1 \leq i_1 < \cdots < i_n < i_{n+1} \leq n + 1} u_{i_1} \ldots u_{n+1},
    \\ \\
    a_{n+1-k}
    &=
    b_{n-k} - u_{n+1} b_{n+1-k}
    = \\ &=
    {(-1)}^k \sum_{1 \leq i_1 < \cdots < i_k \leq n} u_{i_1} \ldots u_{i_k} - u_{n+1} {(-1)}^{k-1} \sum_{1 \leq i_1 < \cdots < i_{k-1} \leq n} u_{i_1} \ldots u_{i_{k-1}}
    = \\ &=
    {(-1)}^k \parens*{ \sum_{1 \leq i_1 < \cdots < i_k \leq n} u_{i_1} \ldots u_{i_k} + u_{n+1} \sum_{1 \leq i_1 < \cdots < i_{k-1} \leq n} u_{i_1} \ldots u_{i_{k-1}} }
    = \\ &=
    {(-1)}^k \sum_{1 \leq i_1 < \cdots < i_{k-1} \leq n} u_{i_1} \ldots u_{i_{k-1}} \parens*{\sum_{i_k=i_{k-1}+1}^n u_{i_k} + u_{n+1} }
    = \\ &=
    {(-1)}^k \sum_{1 \leq i_1 < \cdots < i_k \leq n + 1} u_{i_1} \ldots u_{i_k},
    \\ \\
    a_{n+1} &= b_n = 1.
  \end{align*}
\end{proof}

\section{Примерни задачи}

Условията на представените задачи са взети от \cite{PolynomialExercises}.

\subsection{Анотация}

\begin{enumerate}
  \item Намиране на НОД на два полинома - алгоритъм на Евклид, тъждество на Безу
  \item Прилагане на формулите на Виет за полином с числови коефициенти
\end{enumerate}

\subsection{Най-голям общ делител на полиноми}

\begin{problem}
  \hfill
  \begin{enumerate}
    \item Да се намери най-големият общ делител \( d(X) \) на полиномите
    \begin{align*}
      f(X) &\coloneqq X^3 + X^2 + X + 1, \\
      g(X) &\coloneqq X^2 - X + 2.
    \end{align*}

    \item Да се намерят полиноми \( u(X) \) и \( v(X) \), за които е изпълнено тъждеството на Безу
    \begin{equation*}
      d(X) = f(X) u(X) + g(X) v(X).
    \end{equation*}
  \end{enumerate}
\end{problem}
\begin{solution}
  \hfill
  \begin{enumerate}
    \item Делим \( f(X) \) на \( g(X) \):
    \begin{displaymath}
      \polylongdiv {X^3 + X^2 + X + 1} {X^2 - X + 2},
    \end{displaymath}

    Делим \( g(X) \) на \( f_1(X) \coloneqq X - 3 \):
    \begin{displaymath}
      \polylongdiv {X^2 - X + 2} {X - 3},
    \end{displaymath}

    Полиномът \( f_2(X) \coloneqq 8 \) дели \( f_1(X) \), следователно \( d(X) = f_2(X) = \gcd(f, g) = 8 \) и \( f(X) \) и \( g(X) \) са взаимно прости.

    \item Изразяваме остатъците от деленето при алгоритъма на Евклид:
    \begin{align*}
      f_1(X)
      &=
      f(X) - (X + 2) g(X),
      \\
      d(X)
      &=
      g(X) - (x + 2) f_1(X)
      = \\ &=
      g(X) - (x + 2) [f(X) - (X + 2) g(X)]
      = \\ &=
      (X + 2) f(X) + [{(X + 2)}^2 + 1] g(X)
      = \\ &=
      \boxed{(X + 2) f(X) + (X^2 + 4X + 5) g(X)}.
    \end{align*}
  \end{enumerate}
\end{solution}

\subsection{Формули на Виет}

\begin{problem}
  За кои стойности на параметъра \( p \in \BbbR \) корените \( u_1, \ldots, u_4 \) на полинома
  \begin{equation*}
    f(X) = X^4 - 8X^3 + 22X^2 + pX + 16
  \end{equation*}
  изпълняват равенството \( u_1 + u_2 + u_3 = u_4 \)?
\end{problem}
\begin{solution}
  Заместваме \( u_4 = u_1 + u_2 + u_3 \) във формулите на Виет:
  \begin{align*}
    8 &= (u_1 + u_2 + u_3) + u_4 = 2u_4 = 8
    \\&\implies
    u_4 = 4,
    \\ \\
    22 &= u_1 u_2 + u_1 u_3 + u_1 u_4 + u_2 u_3 + u_2 u_4 + u_3 u_4 = \\ &= u_1 u_2 + u_1 u_3 + u_2 u_3 + (u_1 + u_2 + u_3) u_4
    \\&\implies
    u_1 u_2 + u_1 u_3 + u_2 u_3 = 6,
    \\ \\
    -p &= u_1 u_2 u_3 + u_1 u_2 u_4 + u_1 u_3 u_4 + u_2 u_3 u_4 = \\ &= u_1 u_2 u_3 + (u_1 u_2 + u_1 u_3 + u_2 u_3) u_4 \\&\implies
    u_1 u_2 u_3 = -p - 24,
    \\ \\
    16 &= (u_1 u_2 u_3) u_4
    \\&\implies
    (-p - 24) 4 = 16 \implies p = -28.
  \end{align*}
\end{solution}

\begin{sloppypar}
  \printbibliography
\end{sloppypar}

\end{document}
