\documentclass[fullscreen=true,unicode,bookmarks=false]{beamer}
\usetheme{Boadilla}           % Замовлення теми - стилю презентації  
\usepackage[T2A]{fontenc}
\usepackage[cp1251]{inputenc}
\usepackage[english,ukrainian]{babel}
\usepackage{amsmath,amsfonts,amssymb}
\usepackage{colortbl}
\usepackage{tikz}
\usefonttheme{serif}  % Замовлення шрифта з насічками.
                      % Шрифт без насічок буде при відсутності вказівки
                      % або \usefonttheme{serif} 
\theoremstyle{definition}     % Стиль середовищ 
\newtheorem{du}{\bf Означення}% Задання заголовку нового середовища
\newtheorem{tu}{\bf Теорема}  % для запису висловлювань
\newtheorem{cu}{\bf Наслідок}
\newtheorem{lemu}{\bf Лема}
\newtheorem{notu}{\bf Зауваження}

\theoremstyle{example}
\newtheorem{pu}{\bf Задача}
\newtheorem{exampleu}{\bf Приклад}
\newtheorem{history}{\bf Історична довідка}
\newtheorem{proofu}{\bf Доведення}
\newtheorem{baseu}{\bf База індукції}
\newtheorem{supu}{\bf Припущення індукції}
\newtheorem{stepu}{\bf Крок індукції}
\newtheorem{solu}{\bf Розв'язання}

\newcommand<>{\srccell}{\only#1{\color{blue}}}
\newcommand<>{\rescell}{\only#1{\color{red}}}
\newcommand<>{\colorhide}{\only#1{\color{lightgray}}}
\centering%\let\\\tabularnewline
\newcolumntype{M}{>{\hfill$}p{2em}<{$\hfill}}
\author{\bf Олександр Рудик}
\institute{КУ ім. Б.Грінченка}
\title{\bf Подiльність і корені многочленів}
\subtitle{Приклад подання навчального матеріалу\\
          презентацією у форматі pdf}
\hypersetup{pdfkeywords={схема Горнера, Horner's scheme}}

\AtBeginSection[]% Вставлення даткового слайду з виділеним фрагментом
                 % змісту стососно поточного розділу - \section
{\begin{frame}{\bf План доповіді}
 \tableofcontents[currentsection]\end{frame}
}
\begin{document}
\begin{frame}\titlepage\end{frame}
\begin{frame}{\bf План доповіді}\tableofcontents[pausesections]\end{frame}
\section{Схема Горнера}\subsection{Мотивація запровадження}
\begin{frame}{\bf Мотивація запровадження}
Для зменшення кількості виконуваних операцій\\
і відповідно зменшення ймовірності помилки\\ обчислювати значення многочлена:
\begin{eqnarray*}
f(x)&=&f_0+f_1x+f_2x^2+\cdots +f_{n-1}x^{n-1}+f_nx^n~=\\
    &=&f_nx^n+f_{n-1}x^{n-1}+\cdots +f_2x^2+f_1x+f_0
\end{eqnarray*}
зручно за такою формулою:
$$f(c)=((\cdots ((f_n c+f_{n-1})c+a_{n-2})c+\cdots )c+a_1)c+a_0.$$
\end{frame}
\subsection{Подання таблицею}
\begin{frame}{\bf Подання таблицею}
Проміжні й остаточні  результати записують у таблицю, в якій:\begin{itemize}
\uncover<2->{
\item елементи 1-го рядка, починаючи від 2-го елемента, --- коефіцієнти
      многочлена, записані у порядку спадання степеня змінної;}
\uncover<3->{
\item елемент 2-го рядка, починаючи від 3-го елемента, дорівнює сумі елемента таблиці над
      обчислюваним елементом і попереднім елементом рядка, помноженим на $c$, що є
      1-им елементом 2-го рядка.}\end{itemize}
% Зауважте:
% \uncover<n->{текст} - поява тексту після (n-1)-го
%                       натискання клавіші Enter 
%                       (надалі - текст з № черги n).

\begin{center}\begin{tabular}{|l|l|l|l|l|l|}
\cline{1-6}
&\uncover<2->{$f_n$}
&\uncover<2->{$f_{n-1}}$&
 \uncover<2->{$f_{n-2}$}&
 \uncover<2->{$...$}&
 \uncover<2->{$f_0$}
\\\cline{1-6}
 \uncover<3->{c}
&\uncover<3->{$f_n$}
&\uncover<4->{$f_{n-1}+cf_n$}
&\uncover<5->{$f_{n-2}+c(f_{n-1}+cf_n)$}
&\uncover<6->{$...$}
&\uncover<6->{$f_0+c(...(f_{n-1}+ c f_n)...)$}
\\\cline{1-6}
\end{tabular}\end{center}
\uncover<7->{Таку таблицю і відповідний алгоритм називають схемою Горнера.}
\uncover<8->{\begin{history} Вільямс Джонс Горнер (1786--1837) --- англійський математик.                              Працював у галузі алгебри.\end{history}}
\end{frame}

\section{Ділення многочленів з лишком}
\subsection{Можливість ділення многочленів з лишком}
\begin{frame}%{\bf Можливість ділення многочленів з лишком}
\begin{tu} У множині многочленів над довільним полем можна ділити з лишком на відмінні від 0 многочлени так, щоб лишок дорівнював 0 або
його степінь був менший, ніж степінь дільника.\end{tu}

\uncover<2->{\begin{proofu}  Використаємо метод математичної індукції за степенем діленого для дільника $f(x)$ степеня $n$ зі старшим коефіцієнтом $f_n\not=0$.\end{proofu}}

\uncover<3->{\begin{baseu}Якщо степінь дільника більший, ніж степінь діленого, то частка дорівнює нулю, а лишок --- діленому.\end{baseu}}

\uncover<4->{
\begin{supu} Припустимо, що для всіх многочленів, степінь яких не перевищує $m$, існує подання сумою: $f(x)\cdot q(x)+r(x)$, де $q(x)$ та $r(x)$ --- многочлени змінної $x$, причому $r(x)=0$ або степінь $r(x)$ менший, ніж $n.$\end{supu}}

\end{frame}

\begin{frame}{\bf Можливість ділення многочленів з лишком}

\begin{stepu}
Нехай $g(x)=b_{m+1} x^{m+1}+b_m x^m+b_{m-1} x^{m-1}+\cdots +b_1 x+b_0$ --- довільний много\-член при $m+1\geq n$, $b_{m+1}\not =0.$ Маємо:\uncover<2->{
$$g(x)={b_{m+1}x^{m+1-n}\over a_n}f(x)+ \left(g(x)-{b_{m+1}x^{m+1-n}\over a_n}f(x)\right) ,$$
де вираз у дужках --- многочлен, степінь якого не перевищує $m$, для якого
за припущенням індукції існує подання сумою $f(x)\cdot q(x)+r(x)$.}
\uncover<3->{
$$g(x)=f(x)\left( {b_{m+1}x^{m+1-n}\over a_n}+q(x)\right) +r(x),$$
де $q(x)$ та $r(x)$ --- многочлени змінної $x$, причому $r(x)=0$ або
степінь $r(x)$ менший, ніж $n.$}
\end{stepu}
\end{frame}

\subsection{Запис ділення многочленів з лишком}
\begin{frame}{\bf Запис ділення многочленів з лишком}
Ділення з остачею у многочленів здійснюється так само,\\
як і ділення цілих чисел --- ``у стовпчик''.
\begin{exampleu}\setlength{\tabcolsep} {1.2 pt}% зменшення відстані між стовпцями таблиці
% Зауважте:
% \visible<>{} - перетворення об'єктiв, перелічених у фігурних дужках {} через ;
%                на видимі після збільшеної на 1 кількості натискань у дужках <>
\visible<2->{Подання: $6x^5 -17x^4 +25x^3 -31x^2 +13x+10=$\\
             $=(2x^2 -3x+1)(3x^3 -4x^2+5x-6)-10x+16$ ---}
\visible<3->{\\отримують у результаті виконання  таких дій:}
\begin{tabular}{rrrrrrrrrrrrr|l} % створення таблиці із заданим вирівнюванням 
\visible<6->{$\underline{~~}~$}
\visible<4->{&$6x^5$&$-$&$17x^4$&$+$&$25x^3$&$-$&$31x^2$&$+$&$13x$&$+$&10&&~$2x^2-3x+1$}
\visible<4->{\\\cline{14-14}}
\visible<6->{&$6x^5$&$-$&$ 9x^4$&$+$&$ 3x^3$&&&&&&&}
\visible<4->{&}
\visible<5->{$3x^3$}
\visible<8->{$-~4x^2$}
\visible<11->{$+~5x$}
\visible<14->{$-~6$\vphantom{${1^1}^{1^1}$}}
\visible<6->{\\\cline{2-6}}
\visible<9->{&$\underline{~~}~$}
\visible<7->{&$-$&$ 8x^4$&$+$&$22x^3$&$-$&$31x^2$\vphantom{${1^1}^{1^1}$}}
\visible<9->{\\&&$-$&$ 8x^4$&$+$&$12x^3$&$-$&$ 4x^2$\\\cline{3-8}}
\visible<12->{&&&&$\underline{~~}~$&}
\visible<10->{$10x^3$&$-$&$27x^2$&$+$&$13x$\vphantom{${1^1}^{1^1}$}}
\visible<12->{\\&&&&&$10x^3$&$-$&$15x^2$&$+$&$ 5x$\\\cline{6-10}}
\visible<15->{&&&&&$\underline{~~}~$}
\visible<13->{&$-$&$12x^2$&$+$&$ 8x$&$+$&$10$\vphantom{${1^1}^{1^1}$}}
\visible<15->{\\&&&&&&$-$&$12x^2$&$+$&$18x$&$-$&$ 6$\\\cline{7-12}}
\visible<16->{&&&&&&&&$-$&$10x$&$+$&$16$}
\end{tabular}
\end{exampleu}
\end{frame}

\subsection{Схема Горнера як запис ділення на двочлен}
\begin{frame}{\bf Схема Горнера як запис ділення на двочлен}
Подiлити з лишком многочлен $f(x)$ на двочлен $(x-c)$
означає знайти такі многочлен $q(x)$ і число $r$,
при яких $f(x)=(x-c)q(x)+r.$
\uncover<2->{Запишемо останню рівність детально:}
\begin{tikzpicture}\tikzstyle{every node}=[text centered]

% Зауважте:
% \alert<>{} - змiна кольору тексту у фігурних дужках {}
%              після  такої кількості натискань  клавіші
%              Enter, для якої результат збільшення на 1
%              записано у дужках < >

\uncover<3->{    
\alert<4,5>{\node (f0) at (-5em,0em) {$f_0 x^n$};}
            \node (f0pf1) at (-3.5em,0em) {$+$};
\alert<6,7>{\node (f1) at (-1.5em,0em) {$f_1 x^{n-1}$};}
            \node (f1pf2) at (0.5em,0em) {$+$};
\alert<8,9>{\node (f2) at (2.5em,0em) {$f_2 x^{n-2}$};}
            \node (f2petc) at (4.5em,0em) {$+$};
\alert<10>{\node (etctop) at (6em,0em) {$\ldots\mathstrut$};}
           \node (etcpfn1) at (7em,0em) {$+$};
\alert<11,12>{\node (fn1) at (9em,0em) {$f_{n-1} x\mathstrut$};}
              \node (fn1pfn) at (11em,0em) {$+$};
\alert<13,14>{\node (fn) at (12em,0em) {$f_n\mathstrut$};}
              \node (eqtop) at (13em,0em) {$=$};
              \node (lefteq) at (-6em,-2em) {$=$};
              \node (leftbr1) at (-5.3em,-2em) {$($};
\alert<4,5,6,7,8,9,11,12>{\node (x) at (-4.8em,-2em) {$x\mathstrut$};}
\alert<6,7,8,9,11,12,13,14>{\node (xmc) at (-3.9em,-2em) {$-$};}
\alert<6,7,8,9,11,12,13,14>{\node (c) at (-2.8em,-2em) {$c\mathstrut$};}
                            \node (rightbr1) at (-2.4em,-2em) {$)$};
                            \node (leftbr2) at (-1.7em,-2em) {$($};
\alert<4,5,6,7>{\node (q0) at (0em,-2em) {$q_0 x^{n-1}$};}
                \node (q0pq1) at (2em,-2em) {$+$};
\alert<6,7,8,9>{\node (q1) at (4em,-2em) {$q_1 x^{n-2}$};}
                \node (q1pq2) at (6em,-2em) {$+$};
\alert<8,9>{\node (q2) at (8em,-2em) {$q_2 x^{n-3}$};}
            \node (q2petc) at (10em,-2em) {$+$};
\alert<10>{ \node (etcbot) at (11.2em,-2em) {$\ldots\mathstrut$};}
            \node (etcqn2) at (12.2em,-2em) {$+$};
\alert<11,12>{\node (qn2) at (14.2em,-2em) {$q_{n-2} x\mathstrut$};}
              \node (qn1qfn) at (16.2em,-2em) {$+$};
\alert<11,12,13,14>{\node (qn1) at (17.7em,-2em) {$q_{n-1}\mathstrut$};}
                    \node (rightbr2) at (19em,-2em) {$)$};
                    \node (pc) at (19.8em,-2em) {$+$};
\alert<13,14>{\node (r) at (20.5em,-2em) {$r$};}
              \node (endpunct) at (21em,-2em) {$.\mathstrut$};
}
% Зауважте:
% при першому використанні вказівки \draw
%   \draw[-,red] (x) .. controls +(down:4ex) and +(down:4ex) .. (q0);
%         -           відсутність ефектів;
%           red     - колiр зображення;
%                 x - мітка фрагменту 1;
%                                  down/up  - вказує,  що  лінія   під/над фрагментом 1;
%                                       4ex - відступ по вертикалі під/над фрагментом 1;
%          вказує, що лінія під/над фрагментом 2 - down/up ;
%      відступ по вертикалі під/над фрагментом 2 -       4ex;
%                              мітка фрагменту 2 -               q0;

\visible<4,5>  {\draw[-,red] (x) .. controls +(down:4ex) and +(down:4ex) .. (q0);}
\visible<6,7>  {\draw[-,red] (x) .. controls +(down:5ex) and +(down:5ex) .. (q1);
                \draw[-,red] (c) .. controls +(down:3ex) and +(down:3ex) .. (q0);}
\visible<8,9>  {\draw[-,red] (x) .. controls +(down:5ex) and +(down:5ex) .. (q2);
                \draw[-,red] (c) .. controls +(down:3ex) and +(down:3ex) .. (q1);}
\visible<11,12>{\draw[-,red] (x) .. controls +(down:5ex) and +(down:5ex) .. (qn1);
                \draw[-,red] (c) .. controls +(down:3ex) and +(down:3ex) .. (qn2);}
\visible<13,14>{\draw[-,red] (c) .. controls +(down:4ex) and +(down:4ex) .. (qn1);}
\end{tikzpicture}

\uncover<3->{Прирівняємо коефіцієнти при одинакових степенях:}
\vfill
$\begin{array}{rrlcrl}
\uncover<4->{x^n :}    &\uncover<5->{f_0=&q_0}      &\uncover<15->{\implies & q_0=&f_0}\\
\uncover<6->{x^{n-1} :}&\uncover<7->{f_1=&q_1-c q_0}&\uncover<15->{\implies & q_1=&c q_0+f_1}\\
\uncover<8->{x^{n-2} :}&\uncover<9->{f_2=&q_2-c q_1}&\uncover<15->{\implies & q_2=&c q_1+f_2}\\
                       &\uncover<10->{&\ldots} & & &\\
\uncover<11->{x^1 :}   &\uncover<12->{f_{n-1}=&q_{n-1}-c q_{n-2}}
                       &\uncover<15->{\implies & q_{n-1}=&c q_{n-2}+f_{n-1}}\\
\uncover<13->{x^0 :}   &\uncover<14->{f_n=&r-c q_{n-1}}&\uncover<15->{\implies & r=&c q_{n-1}+f_n}\\
\end{array}$\vfill
\uncover<16->{Праворуч --- запис дій згідно зі схемою Горнера.}
\end{frame}

\subsection{Демонстрація роботи}
\begin{frame}{\bf Демонстрація ділення на двочлен}
\begin{exampleu}
З допомогою схеми Горнера поділимо многочлен\\
$f(x)=x^3-5x^2+8$ на двочлен $x-2$.

\[
\tikzstyle{fcell}=[shape=rectangle,text width=1.5em,text centered,draw]
\tikzstyle{gcell}=[shape=rectangle,text width=1.5em,text centered,draw]
\begin{tikzpicture}
\uncover<2->{\node[fcell][label=above:$f_0$] (a0) at (0,2) {$1$};
             \node[fcell][label=above:$f_1$] (a1) at (1,2) {$-5$};
             \node[fcell][label=above:$f_2$] (a2) at (2,2) {$0$};
             \node[fcell][label=above:$f_3$] (a3) at (3,2) {$8$};
             \node[gcell][label=below:$c$] (c) at (-2,0) {2};}
\uncover<3->{\node[gcell][label=below:$q_0$] (b0) at (0,0) {{\visible<5->{$1$}}};
             \node[gcell][label=below:$q_1$] (b1) at (1,0) {{\visible<7->{$-3$}}};
             \node[gcell][label=below:$q_2$] (b2) at (2,0) {{\visible<9->{$-6$}}};
             \node[gcell][label=below:$r$] (r)  at (3,0) {{\visible<11->{$-4$}}};}
\uncover<4,5>{\draw[->] (a0) to (b0);}
\uncover<6,7>{\draw[->] (c) .. node[above]{$\cdot$} controls +(up:4ex) and +(up:4ex) .. (b0);

              \draw[->] (b0) to node[left]{$+$} (a1);
              \draw[->] (a1) to (b1);}
\uncover<8,9>{\draw[->] (c) .. node[above]{$\cdot$} controls +(up:4ex) and +(up:4ex) .. (b1);
              \draw[->] (b1) to node [left]{$+$} (a2);
              \draw[->] (a2) to (b2);}
\uncover<10,11>{\draw[->] (c) .. node[above]{$\cdot$} controls +(up:4ex) and +(up:4ex) .. (b2);
                \draw[->] (b2) to node[left]{$+$} (a3);
                \draw[->] (a3) to (r);}
\end{tikzpicture}\]
\begin{overlayarea}{\textwidth}{6ex}
\only<2>{Запишемо у верхньому рядку коефіцієнти початкового многочлена $f_0$, $f_1$, $f_2$, $f_3$.
         При діленні на $(x-c)$ у нижньому рядку ліворуч пишемо $c$.}
\only<3>{Готуємо у нижньому рядку порожні клітини для лишку $r$\\ і
         коефіцієнтів частки $q_0$, $q_1$, $q_2$.}
\only<4,5>{$q_0 = f_0 = ${\visible<5>{$1$}}}
\only<6,7>{$q_1 = c\cdot q_0+f_1 = 2\cdot 1-5=${\visible<7>{$-3$}}}
\only<8,9>{$q_2 = c\cdot q_1+f_2 = 2\cdot(-3)+0 =${\visible<9>{$-6$}}}
\only<10,11>{$r = c\cdot q_2+f_3 = 2\cdot(-6)+8=${\visible<11>{$-4$}}}
\only<12>{{\bf Відповідь:}\quad $q(x)=x^2-3x-6$,\quad $r=-4$,\\ $f(x)=(x-2)(x^2-3x-6)-4$.}
\end{overlayarea}
\end{exampleu}
\end{frame}


\section{Застосування}\subsection{Обчислення величини многочлена}
\begin{frame}{\bf Обчислення величини многочлена}
Многочлен $f(x)$ поділимо з лишком на $(x-c)$: \[ f(x)=q(x)\cdot (x-c)+r.\]
\uncover<2->{Підставимо в останню рівність $c$ замість $x$. Маємо:
             $$f(c)=\only<2>{\quad\alert{\text{(поміркуйте!)}}}
                    \only<3->{r.}$$}
\uncover<4->{\begin{tu}[Безу] Величина многочлена $f(x)$ у точці $c$ дорівнює лишку від ділення $f(x)$ на $(x-c)$.\end{tu}}
\uncover<5->{\begin{exampleu}Знайдемо величину $f(x)=x^3-3x^2+7x-5$ при $x=3$:\\\centerline{
\begin{tabular}{|c|c|c|c|c|c|}\hline
      & 1 &$-3$& 7 &  $-5$  \\\hline
    3 & 1 &  0 & 7 &{\bf 16}\\\hline\end{tabular}}\noindent
Відповiдь: $f(3)=16$.
\end{exampleu}}
\end{frame}


\subsection{Розкладання за степенями двочлена}
\begin{frame}{\bf Розкладання за степенями двочлена}
\begin{exampleu}
Використовуючи схему Горнера, разкладемо многочлен $f(x)=x^3+3x^2-2x+4$ за степенями двочлена $(x+2)$.
\begin{center}
\begin{tabular}{c|cccc}
                     & 1 &  3 &$-2$& 4
\visible<2->{\\ $-2$ & 1 &  1 &$-4$& \boxed{12}}
\visible<3->{\\ $-2$ & 1 &$-1$& \boxed{$-2$}}
\visible<4->{\\ $-2$ & 1 & \boxed{$-3$}}
\visible<5->{\\ $-2$ & \boxed{1}}
\end{tabular}
\end{center}
\begin{align*} x^3+3x^2-2x+4
\visible<2->{&= (x^2+x-4)(x+2)+12 =\\}
\visible<3->{&= ((x-1)(x+2)-2)(x+2)+12 =\\}
\visible<4->{&= (((1\cdot(x+2)-3)(x+2)-2)(x+2)+12 =\\}
\visible<5->{&= (x+2)^3-3(x+2)^2-2(x+2)+12.}
\end{align*}
\end{exampleu}
\end{frame}

\begin{frame}{}
\begin{history}Етьєн Безу (1730--1783) --- французький математик. Зробив внесок у теорію лінійних рівнянь і визначників. Розвинув теорію виключення змінних із систем рівнянь вищих степенів.
\end{history}
\end{frame}

\subsection{Кратність кореня}
\begin{frame}{\bf Кратність кореня}
\begin{cu}[теореми Безу]\begin{itemize}
\item Якщо $с$ --- корінь многочлена $f(x),$ то $f(x)$ ділиться без остачі на $(x-c)$.
\item Кількість коренів многочлена не перевищує степеня многочлена.\end{itemize}\end{cu}

\begin{du}\begin{itemize}
\item $b$ є дільником $a$ (позначають так: $a~\vdots~b$ або $b~|~a$),
      якщо існує таке $c$, що a дорівнює добутку $bc$:
      $a~\vdots~b\Leftrightarrow b~|~a\Leftrightarrow~\exists~c\quad a=bc.$
      У даному разі кажуть, що a є кратним b, a ділиться на b без лишку.
\item $c$ є коренем многочлена $f(x)$ натуральної кратності $k$, якщо
      $f(x)~\vdots~(x-c)^k,$ але ~$f(x)\not\vdots~(x-c)^{k+1}.$\end{itemize}\end{du}

Щоб знайти кратність кореня $c$, достатньо поділити многочлен на лінійний вираз
$(x-c)$, використовуючи схему Горнера, до тих пір, поки остача від ділення
перестане дорівнювати 0.
\end{frame}

\section{Раціональні корені многочлена}
\subsection{Основа перебору} 
\begin{frame}{}
\begin{tu} Якщо нескоротний дріб $p/q$ --- корінь многочлена $n$-го степеня з цілими коефіцієнтами, то чисельник $p$ --- дільник вільного члена, а знаменник $q$ --- дільник старшого коефіцієнта.\end{tu} 

\uncover<2->{\begin{proofu} Розглянемо довільний многочлен з цілими коефіцієнтами:
\begin{eqnarray*}
f(x)&=& f_0+f_1x+f_2x^2+\cdots +f_{n-1}x^{n-1}+f_nx^n.\\
\uncover<3->{f\left({p\over q}\right) &=&
f_n {p^n\over q^n}+f_{n-1} {p^{n-1}\over q^{n-1}}+\cdots +f_1 {p\over q}+f_0=0\\
&\Leftrightarrow& f_n p^n+f_{n-1} p^{n-1} q+\cdots +f_1 p q^{n-1}+f_0 q^n=0}\\
\uncover<4->{&\Leftrightarrow&f_n p^n=-q\left( f_{n-1} p^{n-1}+\cdots +f_1 p q^{n-2}+f_0 q^{n-1}\right)~\vdots~q}\\
\uncover<5->{&\Leftrightarrow&f_0 q^n=-p\left( f_n p^{n-1}+f_{n-1} p^{n-2} q+\cdots +f_1 q^{n-1}\right)~\vdots~p.}
\end{eqnarray*}
\uncover<6->{Твердження теореми випливає із взаємної простоти $p$ та $q$}
\end{proofu}}
\end{frame}

\begin{frame}{\bf Основа перебору}
Доведена теорема дає змогу знаходити всі раціональні корені многочлена з цілими коефіцієнтами шляхом перебору скінченної кількості варіантів.

\uncover<2->{\begin{cu} Для многочлена з цілими коефіцієнтами справджуються такі висловлювання:\begin{itemize}
\item цілий корінь --- дільник вільного члена;
\item раціональний корінь многочлена зі старшим коефіцієнтом 1 --- ціле число.
\end{itemize}\end{cu}}
\end{frame}

\subsection{Лема для оптимізації перебору}
\begin{frame}{\bf Лема для оптимізації перебору}
\begin{lemu} Якщо $p$ і $q$ --- взаємно прості цілі числа, то для довільного цілого
$m$ числа $p+mq$ та $q$ --- взаємно прості.
\end{lemu}
\uncover<2->{\begin{proofu} Для довільного цілого $m$ з взаємної простоти $p$ і $q$
випливає існування таких цілих $a$ та $b$, при яких:
$$\textup{ НСД}(p,q)=1=ap+bq=a(p+mq)+(b-am)q=\textup{ НСД}(p+mq,q).$$\end{proofu}}
\uncover<3->{З доведеної леми випливає наступна теорема, яка дає змогу значно зменшити об'єм обчислень
при визначенні всіх раціональних коренів многочлена з цілими коефіцієнтами.}
\end{frame}

\subsection{Основа оптимізації перебору}
\begin{frame}{\bf Основа оптимізації перебору}
\begin{tu} Якщо нескоротний дріб $p/q$ --- корінь многочлена $f(x)$ з цілими
коефіцієнтами, $m$ --- довільне ціле, то $f(m)~\vdots~(p-mq).$\end{tu}
\uncover<2->{\begin{proofu}\vskip -5mm\begin{eqnarray*}
f(m)\!\!&=&\!\!f(m)-f(p/g)~=\\&=&
f_n     \left( m^n-{p^n\over q^n}\right) +
f_{n-1} \left( m^{n-1}-{p^{n-1}\over q^{n-1}}\right)+\cdots +
f_1     \left( m-{p\over q}\right) ,\\\uncover<3->{q^nf(m)\!\!&=&\!\!
f_n (m^n q^n-p^n) +f_{n-1} q(m^{n-1} q^{n-1}-p^{n-1})+\cdots +\\\!\!&+&\!\!
f_2 q^{n-2}(m^2q^2-p^2)+
f_1 q^{n-1}(mq-p),}
\end{eqnarray*}
\uncover<4->{що кратне $mq-p$, бо існує такий розклад на множники:\\
\centerline{$a^k-b^k=(a-b)(a^{k-1}+a^{k-2}b+\cdots +ab^{k-2}+b^{k-1}).$}}
\uncover<5->{
Твердження теореми випливає з доведеної леми про взаємну простоту $q$ і $p-mq$.}
\end{proofu}}
\end{frame}

\subsection{Приклад розв'язання рівняння}
\begin{frame}{\bf Приклад розв'язання рівняння}
\begin{pu} Знайти $x$, якщо ~$12x^4-8x^3-41x^2+41x-10=0.$\end{pu}
\uncover<2->{\begin{solu}Позначимо ліву частину рівняння через $f(x)$.\\
\{1,\hfill 2,\hfill 5,\hfill 10\}  --- множина всіх натуральних дільників вільного члена $f(x)$;\\
\{1,\hfill 2,\hfill 3,\hfill 4,\hfill 6,\hfill 12\}\hfill ---\hfill множина\hfill всіх\hfill натуральних\hfill дільників\hfill старшого\\\rightline{коефіцієнта $f(x)$.}
\uncover<3->{Раціональні корені рівняння будемо шукати серед дробів:\\\centerline{$
\begin{array}{llll}
\pm 1,&\pm 2,&\pm 5,&\pm 10,\\
\pm 1/2,&&\pm 5/2,&\\
\pm 1/3,&\pm 2/3,&\pm 5/3,&\pm 10/3,\\
\pm 1/4,&&\pm 5/4,&\\
\pm 1/6,&&\pm 5/6,&\\
\pm 1/12&&\pm 5/12.&\\
\end{array}$}}
\end{solu}}
\end{frame}

\begin{frame}{{\bf Приклад розв'язання рівняння} (продовження 1)}
\begin{solu}
Обчислимо $f(1)$, використовуючи схему Горнера.\begin{center}
\begin{tabular}{|r|r|r|r|r|r|}\cline{1-6}
 &12&$-$8&$-$41&41&$-$10\\\cline{1-6}
1&12&  4&$-$37& 4&$-$6\\\cline{1-6}\end{tabular}\end{center}

\uncover<2->{Для нескоротного дробу $p/q$, що є коренем рівняння, $(p-q)$ ---
дільник $f(1)=-6$, тобто одне з чисел $\pm 1$, $\pm 2$, $\pm 3$, $\pm 6$.}

\uncover<3->{Звузимо множину можливих раціональних коренів:}
\begin{center}
\uncover<4->{$\left\{\begin{array}{llll}
\pm 1,&\pm 2,&\pm 5,&\pm 10,\\
\pm 1/2,&&\pm 5/2,&\\
\pm 1/3,&\pm 2/3,&\pm 5/3,&\pm 10/3\\
\pm 1/4,&&\pm 5/4,&\\
\pm 1/6,&&\pm 5/6,&\\
\pm 1/12&&\pm 5/12,&\\
\end{array}\right\}$}
\uncover<5->{$\to$
$\left\{\begin{array}{lll}
- 1,&\pm 2,&-5,\\
\pm 1/2,&&+5/2,\\
+ 1/3,&+2/3,&+5/3,\\
+ 1/4,&&+5/4,\\
&&+5/6\\\phantom{1}\end{array}\right\}$}
\end{center}
\end{solu}
\end{frame}


\begin{frame}{{\bf Приклад розв'язання рівняння} (продовження 2)}
\begin{solu}
Обчислимо $f(-1)$ за допомогою схеми Горнера.\begin{center}
\begin{tabular}{|r|r|r|r|r|r|}\cline{1-6}
   &12& $-$8&$-$41&41&$-$10\\\cline{1-6}
$-$1&12&$-$20&$-$21&62&$-$72\\\cline{1-6}\end{tabular}\end{center}
\uncover<2->{Для нескоротного дробу $p/q$, що є коренем рівняння, $(p-(-1)\cdot q)=(p+q)$ --- дільник
$f(-1)=-72$.\\}
\uncover<3->{Для чисел з набору:\\\centerline{$
\begin{array}{lll}
- 1,&\pm 2,&-5,\\
\pm 1/2,&&+5/2,\\
+ 1/3,&+2/3,&+5/3,\\
+ 1/4,&&+5/4,\\
&&+5/6\end{array}$}\noindent
умова: 72 $\vdots$ $(p+q)$ --- справджується лише для таких чисел:\\}
\uncover<4->{\centerline{$\pm 1/2$, 1/3, $\pm 2$, $-5$, 5/3, 5/4.}}
\end{solu}
\end{frame}

\begin{frame}{}
\begin{solu}
Обчислимо $f(2)$, використовуючи схему Горнера.\\\vskip 1mm\centerline{
\begin{tabular}{|r|r|r|r|r|r|}\cline{1-6}
 &12&$-$8&$-$41&41&$-$10\\\cline{1-6}
2&12& 16& $-$9&23&36\\\cline{1-6}\end{tabular}\noindent}
\uncover<2->{\vskip -1mm Для нескоротного дробу $p/q$, що є коренем рівняння, $36~\vdots~(p-2q)$.}

\uncover<3->{З раніше виділених чисел: $\pm 1/2$, 1/3, $\pm 2$, $-5$, 5/3, 5/4 --- цю умову
задовольняють лише такі числа:}
\uncover<4->{1/2, $-$2, 5/3, 5/4}.

\uncover<5->{Використовуючи схему Горнера, поділимо $f(x)$ на $(x-1/2)$.\\\vskip 1mm\centerline{
\begin{tabular}{|r|r|r|r|r|r|}\cline{1-6}
   &12&$-$8&$-$41&41&$-$10\\\cline{1-6}
1/2&12&$-$2&$-$42&20&0\\\cline{1-6}
1/2&12&  4&$-$40&0&\\\cline{1-6}
1/2&12& 10&$-$35&&\\\cline{1-6}
\end{tabular}}}
\vskip-2mm
\begin{eqnarray*}
\uncover<6->{f(x)&=&\left( x- {1\over 2}\right)  (12x^3-2x^2-42x-20)}
\uncover<7->{~=\\ &=&\left( x- {1\over 2}\right)^2(12x^2+4x-40)}
\uncover<8->{~=~(2x-1)^2(3x^2+x-10).}
\end{eqnarray*}
\end{solu}
\end{frame}
\begin{frame}{{\bf Приклад розв'язання рівняння} (завершення)}
\begin{solu}
Поділимо $(3x^2+x-10)$ на $(x+2)$ за допомогою схеми Горнера:\begin{center}
\begin{tabular}{|r|r|r|r|}\cline{1-4}
   &3&  1&$-$10\\\cline{1-4}
$-$2&3&$-$5&   0\\\cline{1-4}
\end{tabular}~.\end{center}
\uncover<2->{У результаті маємо розклад: $f(x)=(2x-1)^2(x+2)(3x-5).$}
\end{solu}
\uncover<3->{{\bf Відповідь.} $-$2, 3/5, 1/2 (останній корінь має кратність 2).}
\uncover<4->{\begin{notu}
Якби многочлен $(x-1/2)$ не виявився дільником $f(x)$, то ділили б $f(x)$ по
черзі на $(x+2)$, $(x-5/3)$, $(x-5/4)$.\end{notu}}
\end{frame}
\end{document}
