Определим ключевые понятие для решения задач.

Определение 1

$f(x), g(x) \in \mathbb{P} { [ x ] },\quad g(x) \neq 0$. $f(x)$ делится на $g(x)$
$\Big( f(x)$ $\vdots$ $g(x)\Big)$ , если $f$ представимо в следующем виде:

$$f(x)=g(x) \cdot h(x),\quad где \quad h(x) \in \mathbb{P} [x].$$

Определение 2

Пусть $f(x), g(x),h(x) \in \mathbb{P} { [ x ] }$, если $h(x)$ $|$ $f(x)$ и $h(x)$ $|$ $g(x)$, то $h(x)$ называется общим делителем $f(x)$, $g(x)$.

Алгоритм Горнера

Алгоритм вычисления значения многочлена, записанного в виде суммы мономов, при заданном значении переменной.
$f(x)=a_{n}x^n+a_{n-1}x^{n-1}+\dots+a_1x+a_0$
$q(x)=b_{n-1}x^{n-1}+b_{n-2}x^{n-2}+\dots+b_1x+b_0$
$f(x)=(x-\alpha)q(x)+f(\alpha)$
Умножаем $q(x)$ на $x-\alpha$ и приравниваем:

	$\large f(x)=(x-\alpha)q(x)+f(\alpha)$
$\large n$	$\large a_n=b_{n-1}$	$\large b_{n-1}=a_n$
$\large n-1$	$\large a_{n-1}=b_{n-2}-\alpha b_{n-1}$	$\large b_{n-2}=a_{n-1}+\alpha b_{n-1}$
$\large n-2$	$\large a_{n-2}=b_{n-3}-\alpha b_{n-2}$	$\large b_{n-3}=a_{n-2}+\alpha b_{n_2}$
$\large \vdots$	$\large \dots$	$\large \dots$
$\large 1$	$\large a_1=b_0-\alpha b_1$	$\large b_0=a_1+\alpha b_1$
$\large 0$	$\large a_0=f(\alpha)-\alpha b_0$	$\large f(\alpha)=a_0+\alpha b_0$

Схема Горнера

	$\large a_n$	$\large a_{n-1}$	$\large a_{n-2}$	$\large \dots$	$\large a_1$	$\large a_0$
$\large \alpha$	$\large b_{n-1}$	$\large b_{n-2}$	$\large b_{n-3}$	$\large \dots$	$\large b_0$	$\large f(\alpha)$

Комбинируя алгоритм Горнера и занося результаты в схему Горнера получаем простой алгоритм нахождения остатка и частного, при делении на заданный линейный двухчлен.

Задача 1

Указать делит ли многочлен $g(x)$ многочлен $f(x).$

Алгоритм:

1. Делим первый элемент делимого на старший элемент делителя, помещаем результат под чертой.
2. Умножаем делитель на полученный выше результат деления. Записываем результат под первыми двумя элементами делимого.
3. Вычитаем полученный после умножения многочлен из делимого, записываем результат под чертой.
4. Если степень полученного многочлена в пункте 3 меньше степени делителя – завершаем процесс, в противном случае – перейти к пункту 5.
5. Повторяем предыдущие 4 шага, используя в качестве делимого многочлен, записанный под чертой.

• $$\large f(x)=x^3-12x^2-42 \quad g(x)=x-3$$
  

  $\large x^3$	$\large —$	$\large 12x^2$	$\large +$	$\large 0x$	$\large -$	$\large 42$	$\large x$	$\large -$	$\large 3$	$\large$	$\large$
  $\large x^3$	$\Large -$	$\large 3x^2$	$\large$	$\large$	$\large$	$\large$	$\large x^2$	$\large -$	$\large 9x$	$\large -$	$\large 27$
  $\large$	$\large -$	$\large 9x^2$	$\large +$	$\large 0x$	$\large -$	$\large 42$	$\large$	$\large$	$\large$	$\large$	$\large$
  $\large$	$\large -$	$\large 9x^2$	$\large +$	$\large 27x$	$\large$	$\large$	$\large$	$\large$	$\large$	$\large$	$\large$
  $\large$	$\large$	$\large$	$\large -$	$\large 27x$	$\large -$	$\large 42$	$\large$	$\large$	$\large$	$\large$	$\large$
  $\large$	$\large$	$\large$	$\large -$	$\large 27x$	$\large +$	$\large 81$	$\large$	$\large$	$\large$	$\large$	$\large$
  $\large$	$\large$	$\large$	$\large$	$\large$	$\large -$	$\large 123$	$\large$	$\large$	$\large$	$\large$	$\large$

  Ответ: $r(x)=-123 \Rightarrow g(x)$ не делит $f(x)$.

• $$\large f(x)=x^2+3x+2 \quad g(x)=x+2$$
  

  $\large x^2$	$\large +$	$\large 3x$	$\large +$	$\large 2$	$\large x$	$\large +$	$\large2$
  $\large x^2$	$\large +$	$\large x$			$\large x$	$\large +$	$\large 1$
  		$\large 2x$	$\large +$	$\large 2$
  		$\large 2x$	$\large +$	$\large 2$
  				$\Large 0$

  Ответ: $r(x)=0 \Rightarrow g(x)$ делит $f(x)$.

 

Задача 2

Найти частное и остаток от деления на линейный двучлен используя метод Горнера.

$$\large f(x)=2x^4-3x^3-x^2+4x+13$$ $$\large Линейный \quad двучлен:\quad x-1$$
Применим предложенный выше алгоритм:

	$\large a_4=2$	$\large a_3=-3$	$\large a_2=-1$	$\large a_1=4$	$\large a_0=13$
$\large \alpha=1$	$\large b_3=a_4$ $b_3=2$	$\large b_2=a_3+\alpha b_3$ $b_2=-1$	$\large b_1=a_2+\alpha b_2$ $b_1=-2$	$\large b_0=a_1+\alpha b_1$ $b_0=2$	$\large f(\alpha)=15$

Ответ: $q(x)=2x^3-x^2-2x+2, \quad f(\alpha)=15$.

Список литературы:

1. Конспект по линейной алгебре и геометрии. 1 курс. Геннадий Сергеевич Белозеров. Глава 3.
2. Сканави М. И. Элементарная математика. — 2-е изд., перераб. и доп. — М.: Наука, 1972. — 142—147 c.
3. Волков Е. А. § 2. Вычисление значений многочлена. Схема Горнера — Учеб. пособие для вузов. — 2-е изд., испр. — М.: Наука, 1987. — 248 с.

Определение 1

Отображение $\large f:X \to Y$ называется биекцией и обозначается $\large f:X \leftrightarrow Y$, если оно:

1.  Переводит элементы множества $X$ в разные элементы множества $Y$ (т.е. выполняется взаимно однозначное отображение — инъекция):
   • $\forall x_{1} \in X$, $\forall x_{2} \in X$, $f(x_{1})=f(x_{2})\Rightarrow x_{1}=x_{2}$.
2. Любой элемент из $Y$ имеет свой прообраз (т.е. выполняется сюръекция):
   • $\forall y \in Y$, $\exists$ $x \in X$, $f(x)=y$.

Пример:

• Изобразим биективное отображение $\large f$, где $f:A \to B$:
  
• Для композиции $g \circ f$, где $f:A \to B,\quad g:B \to C$, рисунок будет выглядеть так:
  

Определение 2

Единичным отображением $e_{X}:X \to X$ называется отображение, переводящие каждый элемент $x \in X$ в себя.

Теорема

Пусть $f: X \to Y$, $h: Y \to Z$ — биективные отображения. Тогда биективна и их композиция $h \circ f$, причем:

$$(h \circ f)^{-1}=f^{-1} \circ h^{-1}$$
Доказательство:
Биективность $f$ влечёт существование и биективность $f^{-1}$.
Из условия существования обратного отображения для биективных отображений следует:
$$\left.\begin{aligned} f\circ f^{-1}=e_{Y} \\ f^{-1}\circ f=e_{X}\end{aligned}\right\} \Rightarrow {(f^{-1})}^{-1}=f$$
Далее существуют отображения:
$f^{-1}: Y\to X \quad h^{-1}: Z \to Y$
$f^{-1}\circ h^{-1}:Z\to X$
Из равенств
$(h\circ f)(f^{-1}\circ h^{-1})=\big( (h\circ f)\circ f^{-1}\big)\circ h^{-1}=\big(h \circ (f\circ f^{-1})\big) \circ h^{-1}=$
$$=h \circ h^{-1}=e_{Z}$$
$(f^{-1} \circ h^{-1})\circ(h \circ f)= f^{-1}\circ \big(h^{-1} \circ (h \circ f) \big)=f^{-1}\circ \big((h^{-1}\circ h) \circ f\big)=$
$$=f^{-1} \circ f=e_{X}$$
вытекает, что $f^{-1}\circ h^{-1}$ — обратное отображение к $h \circ f$.

Список литературы:

1. Кострикин А. И. Введение в алгебру. — М.: Наука, 1977. стр. 37-38 стр.
2. Фейс К. Алгебра: кольца, модули и категории. Том 1 — М.: «Мир», 1977. — 40 стр.
3. Н. К. Верещагин, А. Шень. Часть 1. Начала теории множеств. Лекции по математической логике и теории алгоритмов. — 2-е изд., испр. — М.: МЦНМО, 2002. — 128 стр.