2. Разложение на множители

Разложение многочлена на множители. Алгоритм Евклида

Неприводимые многочлены.

Неприводимый многочлен

многочлены комплексныечисла множество определение аиг

Неприводимый многочлен

Многочлен $P(x)$ степени выше нулевой называется неприводимым над полем $K$ ¹, если его нельзя представить в виде произведения двух многочленов меньшей степени с коэффициентами из того же поля.
Неприводимые многочлены играют в кольце многочленов ту же роль, что и простые числа в кольце ¹ целых чисел.

Зависимость от поля

Свойство неприводимости зависит от поля, над которым рассматривается многочлен:

1. Над $\mathbb{R}$:² Многочлен $x^2+1$ неприводим, так как не имеет вещественных корней и не раскладывается на линейные множители.
2. Над $\mathbb{C}$: **³ Тот же многочлен $x^2+1$ приводим, так как $x^2+1=(x-i)(x+i)$.
3. Над ${\mathbb{Z}}_2$: ⁴ Многочлен $x^2+1$ приводим, так как в поле вычетов по модулю 2: $x^2+1=x^2+2x+1=(x+1{)}^2$.

Footnotes

1. Тема второго семестра АиГ ↩ ↩²

2. Вещественные числа ↩

3. Комплексные числа ↩

4. Кольцо вычетов ↩

Ссылка на оригинал

Теорема 1. Основная теорема арифметики для многочленов

Теорема. Основная теорема арифметики для многочленов

многочлены теорема аиг дмити

Теорема

Аналог Основной теоремы арифметики
Любой многочлен над полем¹ можно единственным образом (с точностью до перестановки множителей и умножения на константы) разложить в произведение неприводимых многочленов.
Без доказательства

Footnotes

1. Тема второго семестра АиГ ↩

Ссылка на оригинал

---

Теорема 2. Безу

Теорема. Безу

многочлены теорема аиг дмити

Теорема

Остаток от деления многочлена $f(x)$ на двучлен $(x-a)$ равен значению этого многочлена в точке $a$, то есть $f(a)$.

Доказательство

Разделим с остатком: $f(x)=(x-a)q(x)+r(x)$
причём $\mathrm{deg}r(x)<\mathrm{deg}(x-a)=1$, т.е. в остатке константа.
Подставим в равенство $a$ :

$$f(a)=0+r(a),\text{ т.е. }r=f(a)$$

Следствие

Для того, чтобы многочлен $f(x)$ делился на двучлен $(x-a)$, необходимо и достаточно, чтобы $f(a)=0$.

Ссылка на оригинал

---

Многочлен с целыми коэффициентами

Многочлен с целыми коэффициентами

многочлены определение аиг дмити

Многочлен с целыми коэффициентами

Рассматриваем многочлен степени $n$ вида:

$$P(x)=a_n{x}^n+a_{n-1}{x}^{n-1}+\cdots +a_{1}x+a_0,$$

где все коэффициенты $a_i$ являются целыми числами ($a_i\in \mathbb{Z}$), причем $a_n\ne 0$.

Ссылка на оригинал

Теорема 3. О рациональных корнях многочлена с целыми коэффициентами

Теорема. О рациональных корнях многочлена с целыми коэффициентами

многочлены теорема аиг дмити

Теорема о рациональных корнях

Пусть несократимая дробь $p/q$ (где $p\in \mathbb{Z}$ ¹, $q\in \mathbb{N}$², $\text{НОД}(p,q)=1$ ³) является корнем многочлена $P(x)$ с целыми коэффициентами.
Тогда выполняются следующие условия делимости:

1. Старший коэффициент $a_n$ делится на знаменатель дроби $q$ ($a_n⋮q$).

2. Свободный член $a_0$ делится на числитель дроби $p$ ($a_0⋮p$).

Необходимое условие

Данная теорема предоставляет лишь необходимое условие существования рационального корня. Это означает, что если рациональный корень существует, он обязательно имеет такой вид. Однако не каждое число вида $p/q$, удовлетворяющее условиям делимости, является корнем. Требуется проверка подстановкой.

Доказательство

Пусть $x=\frac{p}{q}$ – корень многочлена $P(x)=0$, и дробь $\frac{p}{q}$ несократима ($\text{НОД}(p,q)=1$)³.

1. Подстановка и приведение к общему знаменателю:
   Подставим значение корня в уравнение:

   $$a_n{\left(\frac{p}{q}\right)}^n+a_{n-1}{\left(\frac{p}{q}\right)}^{n-1}+\cdots +a_1\left(\frac{p}{q}\right)+a_0=0$$

   Умножим обе части равенства на $q^n$, чтобы избавиться от знаменателей:

   $$a_n{p}^n+a_{n-1}{p}^{n-1}q+\cdots +a_{1}p{q}^{n-1}+a_0{q}^n=0$$

2. Доказательство делимости свободного члена ($a_0⋮p$):
   Выразим слагаемое, содержащее $a_0$:

   $$a_0{q}^n=-\left(a_n{p}^n+a_{n-1}{p}^{n-1}q+\cdots +a_{1}p{q}^{n-1}\right)$$

   Вынесем общий множитель $p$ в правой части:

   $$a_0{q}^n=-p\left(a_n{p}^{n-1}+a_{n-1}{p}^{n-2}q+\cdots +a_1{q}^{n-1}\right)$$

   Так как выражение в скобках является целым числом, правая часть делится на $p$. Следовательно, левая часть $a_0{q}^n$ также должна делиться на $p$.
   Поскольку числа $p$ и $q$ взаимно просты, то $p$ и $q^n$ не имеют общих множителей. Следовательно, на $p$ должен делиться коэффициент $a_0$.

3. Доказательство делимости старшего коэффициента ($a_n⋮q$):
   Аналогично выразим слагаемое, содержащее $a_n$:

   $$a_n{p}^n=-\left(a_{n-1}{p}^{n-1}q+\cdots +a_{1}p{q}^{n-1}+a_0{q}^n\right)$$

   Вынесем общий множитель $q$ в правой части:

   $$a_n{p}^n=-q\left(a_{n-1}{p}^{n-1}+\cdots +a_{1}p{q}^{n-2}+a_0{q}^{n-1}\right)$$

   Правая часть делится на $q$, значит, и левая часть $a_n{p}^n$ делится на $q$.
   Так как $\text{НОД}(p,q)=1$, а поскольку возведение в степень копирует простые множители нашего числа, не добавляя новых получаем $\text{НОД}(p^n,q)=1$. Следовательно, на $q$ обязан делиться коэффициент $a_n$.

Следствие

Каждый целый корень $p$ многочлена $f(x)=a_n{x}^n+a_{n-1}{x}^{n-1}+\dots +a_{1}x+a_0$ с целыми коэффициентами является делителем свободного члена $a_0$. В этом случае $q=1$

Footnotes

1. Множество целых чисел ↩

2. Множество натуральных чисел ↩

3. Условие взаимной простоты ↩ ↩²

Ссылка на оригинал

---

Наибольший общий делитель двух многочленов

Наибольший общий делитель для многочленов (НОД)

многочлены определение аиг дмити

Определение

Многочлен $d(x)$ называется общим делителем многочленов $f(x)$ и $g(x)$, если

$$f(x)=d(x)\cdot f_1(x),g(x)=d(x)\cdot g_1(x)$$

при некоторых $f_1(x),g_1(x)\in P[x]$. Многочлен называется наибольшим общим делителем (НОД) $f(x)$ и $g(x)$, если он имеет наибольшую степень.

Замечание

Исходя из этого определения, НОД двух многочленов задаётся неоднозначно - их может быть бесконечное множество, но отличаться они будут на постоянный множитель: если $d(x)=$ НОД $(f(x),g(x))$, то $\alpha \cdot d(x)$ также будет являться НОД при любом ненулевом $\alpha$.

Если же зафиксировать старший коэффициент НОД равным 1 , то такой многочлен уже будет единственным.

Ссылка на оригинал

---

Алгоритм Евклида

Алгоритм Евклида для многочленов

Алгоритм

Так как для многочленов определено деление с остатком, к ним применим алгоритм Евклида для поиска НОД, аналогичный числовому.

1. Разделить $f(x)$ на $g(x)$, получить остаток $r(x)$.

2. Если $r(x)=0$, то НОД равен $g(x)$.

3. Иначе заменить пару $(f,g)$ на $(g,r)$ и повторить шаг 1.

Пусть $f,g\in P[x],\mathrm{deg}(g)\ne 0$

$$\begin{array}{l}f=g\cdot q+r,\mathrm{deg}(r)<\mathrm{deg}(g)\\ g=r\cdot q_1+r_1,\mathrm{deg}\left(r_1\right)<\mathrm{deg}(r)\\ r=r_1\cdot q_2+r_2,\\ \dots \\ r_i=r_{i+1}\cdot q_{i+2}+r_{i+2}\\ \dots \\ r_{s-2}=r_{s-1}\cdot q_s+r_s,r_s\ne 0-\text{последний ненулевой остаток равен}\mathrm{НОД}(f,g)\\ r_{s-1}=r_s\cdot q_{s+1}\end{array}$$

Процесс всегда завершается, так как на каждом шаге степень остатка уменьшается

Пример

$$\begin{array}{rl}& f=x^4+x^3-3x^2-4x-1,g=x^3+x^2-x-1\\ & \\ & x^4+x^3-3x^2-4x-1\mid \underline{x^3+x^2-x-1}\\ & \frac{x^4+x^3-x^2-x}{-2x^2-3x-1=r(x)\text{- остаток на шаге 1}}\end{array}$$

Далее по алгоритму

$$\begin{array}{rl}& \begin{array}{lr}{x}^3+x^2-x-1& \frac{-2x^2-3x-1}{-\frac{1}{2}x+\frac{1}{4}}\\ \underline{x^3+\frac{3}{2}{x}^2+\frac{1}{2}x}& \end{array}\\ & -\frac{x^2}{2}-\frac{3}{2}x-1\\ & \underline{-\frac{x^2}{2}-\frac{3}{4}x-\frac{1}{4}}\\ & -\frac{3}{4}x-\frac{3}{4}=r_1(x)\text{ - остаток на шаге }2\text{, равный НОД }(f,g)\text{, }\end{array}$$

поскольку $r=r_1\cdot \left(-\frac{4}{3}\right)\cdot (2x+1)+r_2(x)$ (при этом $r_2(x)=0,r_1(x)-$ последний ненулевой остаток)
В качестве НОД можно взять этот же многочлен с другим множителем, например,

$$x+1=\left(-\frac{3}{4}x-\frac{3}{4}\right)\cdot \left(-\frac{4}{3}\right)$$

Ссылка на оригинал

Теорема 4. Остаток из алгоритма Евклида

Теорема. Остаток из алгоритма Евклида

многочлены теорема аиг дмити

Теорема

$r_s$ из алгоритма Евклида является наибольшим общим делителем многочленов $f(x)$ и $g(x)$

Доказательство

Необходимо доказать два факта: $r_s$ это общий делитель $f$ и $g$ и он имеет наибольшую степень.

Из последнего равенства следует, что $r_{s-1}{r}_s$
Из предпоследнего получаем, что $r_{s-2}=r_s\cdot q_{s+1}\cdot q_s+r_s=r_s\left(q_{s+1}{q}_s+1\right)$, т. е. $r_{s-2}⋮r_s$
Далее, поднимаясь вверх до второго и первого равенств, получим, что $f,g⋮r_s$
Теперь предположим, что существует многочлен $h(x)$ большей степени, являющийся общим делителем $f$ и $g$

Тогда благодаря первому равенству $r⋮h$, благодаря второму $r_1⋮h$; и так далее вплоть до предпоследнего равенства, из которого получим, что $r_s⋮h$, что невозможно. Следовательно, такого многочлена не существует и $r_s$ является НОД( $f,g$ )

Ссылка на оригинал

---

Линейное представление НОД

Взаимно простые многочлены

Def. Два многочлена называются взаимно простыми, если их НОД равен 1.
Обозначается: $(f(x),g(x))=1$

многочлены

Ссылка на оригинал

Теорема 5. О линейном представлении НОД

Теорема. Линейное представление НОД

Теорема

$\forall f(x),g(x)\in \mathbf{R}[x]\backslash \{0\}\mathrm{НОД}(f,g)=d(x)$ может быть представлен в виде

$$d(x)=f(x)a(x)+g(x)b(x)$$

для некоторых $a(x),b(x)\in \mathbf{R}$.

На самом деле теорема верна для любого поля, не только $\mathbf{R}$

Доказательство

Рассмотрим Множество многочленов

$$W=\{m(x)f(x)+n(x)g(x)\mid m(x),n(x)\in \mathbf{R}[x]\}$$

т.е. множество сумм многочленов при всевозможных $m(x),n(x)\in \mathbf{R}[\mathbf{x}]$.
Это бесконечное множество, в нём выберем многочлен $d(x)$ наименьшей степени, отличный от нуля. Покажем, что $d(x)=$ НОД $(f(x),g(x)$.

Сначала докажем, что если $p(x),t(x)\in W$, то их остаток от деления:

$$r(x)\in W(p(x)=q(x)t(x)+r(x))$$

Пусть:

$$p(x)=m_1(x)f(x)+n_1(x)g(x),t(x)=m_2(x)f(x)+n_2(x)g(x)$$

Тогда из $p(x)=q(x)t(x)+r(x)$ следует, что

$$\begin{array}{rl}& r(x)=p(x)-q(x)t(x)=m_1(x)f(x)+n_1(x)g(x)-q(x)\left(m_2(x)f(x)+n_2(x)g(x)\right)\\ & =\left(m_1(x)-q(x)m_2(x)\right)f(x)+\left(n_1(x)-q(x)n_2(x)\right)g(x)\in W\end{array}$$

Пусть степень $d(x)\in W$ минимальна.
Так как сам $f(x)\in W$, при делении его на $d(x)$ остаток также будет содержаться в $W$. Однако, по определению деления с остатком, его степень будет меньше $\mathrm{deg}(d(x))$, а это невозможно по выбору $d(x)$. Следовательно, $f(x)⋮d(x)$.

Аналогично: $g(x)⋮d(x)$.
Таким образом, $d(x)$ - общий делитель $f(x)$ и $g(x)$. Докажем, что наибольший.
Возьмём какой-нибудь другой общий делитель $v(x)$ данных двух многочленов. $d(x)\in W,d(x)=m_0(x)f(x)+n_0(x)g(x)\Rightarrow d(x)⋮v(x)$
Теорема доказана

Следствие 1

Для того чтобы многочлены $f(x)$ и $g(x)$ были взаимно простыми, необходимо и достаточно, чтобы существовали такие многочлены $m(x),n(x)$, чтобы

$$f(x)m(x)+g(x)n(x)=1$$

Непосредственно следует из теоремы.

Следствие 2

Если произведение $f(x)g(x)$ делится на $q(x)$, при этом $(f(x),q(x))=1$, то

$$g(x)⋮q(x)$$

Достаточно расписать условие взаимной простоты и домножить обе части получившегося равенства на $g$

Следствие 3

$$(f(x),q(x))=1,(g(x),q(x))=1⟹(f(x)g(x),q(x))=1$$

Докажите самостоятельно.

многочлены

Ссылка на оригинал

---

Теорема 6. Гаусса

Теорема Гаусса

Теорема

Любой Многочлен $f(x)\in P[x]$ степени не меньше 1 имеет хотя бы 1 комплексный корень.

Без доказательства.

Следствие 1

Пусть $f(x)\in P[x],\mathrm{deg}(f)=n\ge 1$. Тогда $f(x)$ имеет ровно $n$ комплексных корней с учётом их кратности.

Доказательство

По теореме Гаусса $f(x)$ имеет комплексный корень $z_1$. Тогда, по следствию из теоремы Безу

$$f(x)=\left(x-z_1\right)f_1(x)$$

где $\mathrm{deg}\left(f_1(x)\right)=n-1$.

Применим теорему Гаусса к $f_1(x)$, получим:

$$f_1(x)=\left(x-z_2\right)f_2(x)\text{ и }\mathrm{deg}\left(f_2(x)\right)=n-2$$

Повторяя эти рассуждения ещё $n-2$ раза для каждого $f_i(x)$, получим, что

$$f(x)=\left(x-z_1\right)\left(x-z_2\right)\cdot \dots \cdot \left(x-z_{n-1}\right)a_n\left(x-z_n\right)$$

Некоторые корни могут совпадать. Следствие доказано. Более того, мы получили, что каждый Многочлен степени $n$ над полем комплексных чисел раскладывается в произведение $n$ линейных сомножителей.

Следствие 2

Если Комплексное число $z_0=x_0+i{y}_0$ - корень многочлена $f(x)$ с вещественными коэффициентами, то $\overline{z_0}=x_0-i{y}_0$ также является корнем $f(x)$.

Доказательство

По свойствам комплексного сопряжения имеем:

$$\begin{array}{rl}& f\left(z_0\right)=a_n{z}_0^n+a_{n-1}{z}_0^{n-1}+\dots +a_1{z}_0+a_0=0⟹\\ & \overline{0}=\overline{f\left(z_0\right)}=\overline{a_n{z}_0^n+a_{n-1}{z}_0^{n-1}+\dots +a_1{z}_0+a_0}=a_n\overline{z_0^n}+a_{n-1}\overline{z_0^{n-1}}+\dots +a_1\overline{z_0}+a_0=\\ & =f\left(\overline{z_0}\right)\end{array}$$

Следствие 3

Каждый многочлен с вещественными коэффициентами степени $n\ge 1$ раскладывается в произведение неприводимых многочленов не выше второй степени.

Доказательство

По следствию 2 , если $z_0$ - корень $f(x)$, то и $\overline{z_0}$ является корнем данного многочлена.
Это означает, что двучлены $\left(x-z_0\right)=\left(x-x_0-i{y}_0\right)$ и $\left(x-\overline{z_0}\right)=\left(x-x_0+i{y}_0\right)$ являются делителями $f(x)$.
Перемножим их:

$$\left(x-x_0-i{y}_0\right)\left(x-x_0+i{y}_0\right)={\left(x-x_0\right)}^2-{\left(i{y}_0\right)}^2={\left(x-x_0\right)}^2+y_0^2=x^2+2x_0+x_0^2+y_0^2$$

Получили квадратный многочлен с вещественными коэффициентами.

многочлены комплексныечисла

Ссылка на оригинал

---

Наименьшее общее кратное

Наименьшее общее кратное для многочленов (НОК)

многочлены определение

Определение

Наименьшим общим кратным (HOK) многочленов $f(x)$ и $g(x)$ называется многочлен наименьшей степени, который делится на $f(x)$ и $g(x)$.

Ссылка на оригинал

---

Теорема 7. НОК

Теорема. НОК

Теорема

Пусть HOK$(f(x),g(x))=k(x)$, НОД $(f(x),g(x))=d(x)$.
Тогда $d(x)k(x)=f(x)\cdot g(x)$.

Доказательство

Если $d(x)$ это наибольший общий делитель, то $f=f_{1}d,g=g_{1}d$, при этом $\left(f_1,g_1\right)=1$ (иначе нашёлся бы многочлен $d\cdot d_1$, на который делились бы два данных многочлена)

Положим $k=f_1{g}_{1}d$ и докажем, что это $\mathrm{HOK}(f,g)$.

То, что $k$ делится на $f$ и $g$, очевидно (они входят в его разложение).
Пусть некий многочлен $h$ также делится на $f$ и $g$.
Тогда $h=h_{f}f=h_{g}g$, отсюда $h_f{f}_{1}d=h_g{g}_{1}d$ и $h_f{f}_1=h_g{g}_1$.

Из взаимной простоты $f_1$ и $g_1$ следует в частности, что $h_f$ делится на $g_1$, откуда $h_{f}f$ делится на $f{g}_1=k$

многочлены

Ссылка на оригинал

---

По итогам лекции нужно знать:

1. Понятия:
   • НОД и НОK
   • Теорема. Линейное представление НОД
   • Взаимно простые многочлены
2. Теорема Безу и следствие из неё
3. Свойства корней многочленов с целыми коэффициентами
4. Неприводимые многочлены над разными числовыми множествами
5. Алгоритм Евклида для многочленов
6. Разложение многочленов на множители
7. Основные теоретические факты с доказательствами

многочлены комплексныечисла множество