!!§!! Вспомогательная страница к разделу ((:polynomial#наибольший_общий_делитель ПОЛИНОМ))
----
== Взаимно-простые полиномы ==
~~TOC~~
--- это полиномы, у которых
((:polynomial#решение_в_радикалах нормализованный)) наибольший общий делитель ($ \operatorname{HOD} $) равен $ 1_{} $ (тождественно).
!!П!! **Пример.** Найти условия взаимной простоты полиномов
$$f(x)=a_0x^2+a_1x+a_2,\ g(x)=b_0x^2+b_1x+b_2, \ a_0 \ne 0, b_0 \ne 0
\ .$$
**Решение.** Очевидно, что $ \operatorname{HOD} (f(x),g(x)) $ будет зависеть от коэффициентов обоих полиномов. Ищем его по ((:polynomial#наибольший_общий_делитель алгоритму Евклида)). Поделим $ f_{}(x) $ на $ g_{}(x) $:
$$f(x)=\frac{a_0}{b_0} g(x) + \underbrace{ \left(a_1 - \frac{a_0b_1}{b_0} \right) x +
\left(a_2 - \frac{a_0b_2}{b_0}\right)}_{= r_1(x)}
\ . $$
Предположим сначала, что $ a_1b_0-a_0b_1 \ne 0 $. Тогда, поделив $ g_{}(x) $ на
$ r_1(x) $, получим после длинных выкладок:
$$g(x)=r_1(x)\frac{b_0}{a_1b_0-a_0b_1} \left(b_0x+ \left(b_1-b_0
\frac{a_2b_0-a_0b_2}{a_1b_0-a_0b_1} \right) \right)
+ \underbrace{\frac{b_0\mathcal R(f,g)}{(a_1b_0-a_0b_1)^2}}_{= r_2(x)} \ ,
$$
где
$$
\mathcal R(f,g) =
b_0^2a_2^2-2\,a_0a_2b_0b_2+a_0^2b_2^2-a_1a_2b_0b_1-a_0a_1b_1b_2+
a_0a_2b_1^2+a_1^2b_0b_2
=
$$
$$
=(a_0b_2-a_2b_0)^2 -(a_0b_1-a_1b_0)(a_1b_2-a_2b_1) \ .
$$
Теперь проанализируем $ \operatorname{HOD} (f,g) $ в зависимости от величины $ \mathcal R(f,g) $. Если $ \mathcal R(f,g)\ne 0 $, то, очевидно, что на следующем шаге алгоритм Евклида остановится и $ \mathcal R(f,g)=\operatorname{HOD} (f,g) $. Тогда полиномы $ f_{}(x) $ и $ g_{}(x) $ взаимно просты. Если же $ \mathcal R(f,g)= 0 $, то $ r_1(x)=\operatorname{HOD} (f,g) $, т.е. $ \operatorname{HOD} $ является линейным по $ x $ полиномом.
Если предположить теперь, что $ a_1b_0-a_0b_1 = 0 $, то алгоритм Евклида
остановится уже на втором шаге. Полиномы $ f_{}(x) $ и $ g_{}(x) $ будут взаимно простыми при $ a_2b_0-a_0b_2 \ne 0 $. Одновременное выполнение условий
$$a_1b_0-a_0b_1 = 0 \quad u \quad a_2b_0-a_0b_2 = 0 $$
равносильно тому, что коэффициенты полиномов $ f_{}(x) $ и $ g_{}(x) $ пропорциональны,
т.е. $ f(x)\equiv Cg(x) $ при некоторой константе $ C\in \mathbb A $. Тогда $ \operatorname{HOD}(f,g) $ совпадает с любым из этих полиномов.
Обобщая предшествующие рассуждения можем выписать условие взаимной
простоты $ f_{}(x) $ и $ g_{}(x) $.
**Ответ.** $ \operatorname{HOD}(f,g)=1 $ тогда и только тогда, когда $ \mathcal R (f,g)\ne 0 $.
Предыдущий пример позволяет выявить общую закономерность: наличие у полиномов $ f_{}(x) $ и $ g_{}(x) $ общих корней является ситуацией исключительной, наблюдаемой только тогда, когда коэффициенты этих полиномов связаны некоторым условием типа равенства. Общий способ получения этого условия см. в разделе
☞
((:dets:resultant#результант_в_форме_сильвестра РЕЗУЛЬТАНТ)). В смысле этого результата, полиномы непохожи на целые числа --- вероятность того, что два случайно выбранных целых числа не являются взаимно простыми
((:numtheory#взаимно_простые_числа ненулевая)).
===Разные теоретические результаты==
!!Т!! **Теорема 1.** //Если каждый из полиномов// $ f_1(x),\dots,f_K(x) $ //взаимно прост с//
$ g_{}(x) $, //то и их произведение// $ f_1(x)\times \dots \times f_{K}(x) $
//взаимно просто с// $ g_{}(x) $.
**Доказательство** полностью повторяет доказательство теоремы 2 из пункта
☞
((:numtheory#взаимно_простые_числа ВЗАИМНО ПРОСТЫЕ ЧИСЛА)).
!!=>!! Если каждый из полиномов
$ f_1(x),\dots,f_K(x) $ взаимно прост с каждым из полиномов
$ g_1(x),\dots,g_L(x) $, то и их произведения
$ f_1(x)\times \dots \times f_{K}(x) $ и $ g_1(x)\times \dots \times g_L(x) $
также взаимно просты. В частности,
$$ \operatorname{HOD} (f(x),g(x)) \equiv 1 \quad \Rightarrow \quad \operatorname{HOD}
\left(f(x)^K,g(x)^L \right)=1 \quad npu \ \{K,L\} \subset \mathbb N
\ .
$$
!!Т!! **Теорема 2.** //Если// $ \operatorname{HOD} \left(f_1(x),g(x) \right) \equiv 1 $ //и
произведение// $ f_1(x)f_2(x) $ //делится на// $ g_{}(x) $, то $ f_2(x) $ //делится на// $ g_{}(x) $.
**Доказательство** полностью повторяет доказательство теоремы 3 из пункта
☞
((:numtheory#взаимно_простые_числа ВЗАИМНО ПРОСТЫЕ ЧИСЛА)).
===Тождество Безу==
!!Т!! **Теорема.** //Для того чтобы полиномы// $ f(x)_{} $ //и// $ g(x)_{} $ //из// $ \mathbb A[x]_{} $ //были
взаимно простыми, необходимо и достаточно существование в// $ \mathbb A[x]_{} $
//полиномов// $ u(x) $ //и// $ v(x) $, //удовлетворяющих// **тождеству Безу**:
$$
v(x)f(x)+u(x)g(x)\equiv 1 \ .
$$
**Доказательство.** **Необходимость.** Если $ \operatorname{HOD}(f,g) \equiv 1 $ то справедливость тождества следует из общего результата о линейном представлении наибольшего общего делителя (см.
☞
((:polynomial#наибольший_общий_делитель ЗДЕСЬ)) ).
**Достаточность.** Если $ vf+ug \equiv 1 $ при некоторых
$ u(x),v(x) $ из $ {\mathbb A}[x] $,
и $ d(x)= \operatorname{HOD}(f,g) $, то $ v(x)f(x) $ делится на $ d(x) $ и $ u(x)g(x) $ делится на $ d(x) $. Тогда их сумма, т.е. 1, делится на $ d(x) $. Это возможно тогда и только тогда, когда $ d(x)\equiv const\ne 0 $.
♦
!!=>!! При условии $ \operatorname{HOD} (f,g) \equiv 1 $ существует единственная пара полиномов $ u(x) $ и $ v(x) $, удовлетворяющих тождеству Безу, и таких, что
$$
\deg u(x) < \deg f(x) , \quad \deg v(x) < \deg g(x) \ .
$$
**Доказательство.** Пусть $ u(x) $ и $ v(x) $ --- какая-то пара полиномов из $ \mathbb A[x] $,
удовлетворяющая тождеству Безу. Поделим $ u(x) $ на $ f(x) $:
$ u(x)\equiv Q(x)f(x) + u_1(x) $, здесь степень остатка $ u_1(x) $ должна
быть меньшей $ \deg f(x) $. Но тогда пара полиномов
$ u_1(x) $ и $ v_1(x) = v(x)+Q(x)g(x) $ также будет удовлетворять тождеству Безу: $ v_1(x)f(x)+u_1(x)g(x) \equiv 1 $. Из последнего тождества получим и оценку степени полинома $ v_1(x) $:
$ v_1(x)f(x)\equiv 1 - u_1(x)g(x) \quad \Rightarrow $
$$ \Rightarrow \quad
\deg \left( v_1(x)f(x) \right) = \deg \left( u_1(x)g(x) \right) <
\deg f(x) + \deg g(x) \quad \Rightarrow \quad \deg v_1(x) < \deg g(x) \ . $$
Осталось доказать единственность указанной в теореме пары полиномов.
Предположим, что имеют место два тождества
$$ v_1(x)f(x)+u_1(x)g(x) \equiv 1 \quad u \quad v_2(x)f(x)+u_2(x)g(x) \equiv 1
\quad npu \ \left\{ \begin{array}{c}
\deg u_j < \deg f,\\
\deg v_j < \deg g.
\end{array} \right.
$$
Тогда, вычитая одно тождество из другого, получаем тождество:
$$ \left(v_1(x)-v_2(x) \right)f(x)
\equiv \left(u_2(x)-u_1(x) \right)g(x) \ ,$$
из которого следует, что произведение $ \left(v_1(x)-v_2(x) \right)f(x) $
делится на $ g_{}(x) $. По условию теоремы $ \operatorname{HOD}(f(x),g(x)) \equiv 1 $. Тогда
на основании теоремы 2 предыдущего пункта, полином
$ v_1(x)-v_2(x) $ должен делиться на $ g_{}(x) $. Однако, по предположению
$ \deg \left(v_1(x)-v_2(x) \right)< \deg g(x) $, и делимость возможна только
когда $ v_1(x)-v_2(x)\equiv 0 $. Но тогда и $ u_2(x)-u_1(x) \equiv 0 $.
♦
Для конструктивного построения полиномов $ u_{}(x) $ и $ v_{}(x) $ существует два способа. Один из них
основывается на ((:numtheory#линейное_представление_нод алгоритме Евклида и на континуанте)).
!!П!! **Пример.** Найти полиномы $ u_{}(x) $ и $ v_{}(x) $, удовлетворяющие тождеству Безу
при
$$f(x)=x^5+5\,x^4+9\,x^3+7\,x^2+5\,x+7 \ , \quad
g(x)=x^4+2\,x^3+2\,x^2+x+1 \ .$$
**Решение.** В схеме ((:polynomial#наибольший_общий_делитель алгоритма Евклида)) имеем
$$q_1(x)=x+3,\ q_2(x)=x+2,\ q_3=x+5,\ q_4=1/33\, x-68/363 $$
при $ r_4=37/121 $. Таким образом, действительно $ f_{}(x) $ и $ g_{}(x) $
взаимно простые и существование $ u(x) $ и $ v(x) $ гарантируется предыдущей теоремой.
Вычисляем $ u(x) $ и $ v(x) $ с помощью континуант:
$$
\begin{array}{|c|c|c|c|c|c|}
\hline
j & 0 & 1 & 2 & 3 & 4 \\
\hline
q_j & - & x+3 & x+2 & x+5 & 1/33\, x-68/363 \\
\hline
K_j(q_1,q_2,\dots,q_j) & 1 & x+3 & x^2+5\, x+7 & x^3+10\, x^2+ &
1/33\,x^4 +14/121\,x^3
+ \\
& & & &\quad +33\, x +38 &\
+46/363\,x^2 -1/33\,x - 43/363 \\
\hline
K_{j-1}(q_2,\dots,q_j) & - & 1 & x+2 & x^2+7\, x +11 &
1/33\, x^3+ 3/121 \, x^2 + 8/363\,x- 2/33 \\
\hline
\end{array}
$$
и приписываем этим выражениям знаки в соответствии с правилом, указанном
☞
((:numtheory#линейное_представление_нод ЗДЕСЬ)):
$$
\begin{array}{rcl}
u(x)&=&(-1)^4 \left( {\scriptstyle 1}/{\scriptstyle 33}\,x^4 +
{\scriptstyle 14}/{\scriptstyle 121}\,x^3 +
{\scriptstyle 46}/{\scriptstyle 363}\,x^2 -
{\scriptstyle 1}/{\scriptstyle 33}\,x -
{\scriptstyle 43}/{\scriptstyle 363}\right) \ , \\
v(x)&=&(-1)^3\left(
{\scriptstyle 1}/{\scriptstyle 33}\, x^3+
{\scriptstyle 3}/{\scriptstyle 121} \, x^2 +
{\scriptstyle 8}/{\scriptstyle 363}\,x-
{\scriptstyle 2}/{\scriptstyle 33}
\right) \ .
\end{array}
$$
удовлетворяют тождеству $ v(x)f(x)+u(x)g(x) \equiv r_4 $. Разделив
последнее тождество на $ r_{4} $, приходим к окончательному ответу.
**Ответ.** $ u(x)={\scriptstyle 1}/{\scriptstyle 111} \left(11\, x^4 +42\, x^3 +46\, x^2 -11\,x -43\right) $,
$ v(x)={\scriptstyle 1}/{\scriptstyle 111} \left(-11\, x^3 -9\, x^2 -8\, x +22 \right) $.
**Проверка.**
$$\left(-11\, x^3 -9\, x^2 + \dots \right)
\left(x^5+5\,x^4 + \dots \right) +
\left(11\, x^4 +42\, x^3 + \dots \right) \left( x^4+ 2\, x^3 + \dots \right)=
$$
$$=(-11+11)\,x^8+ (-11\cdot 5 - 9 +42 + 11 \cdot 2)\, x^7 +\dots $$
Еще одним способом нахождения полиномов $ u_{}(x) $ и $ v_{}(x) $ из тождества Безу является **метод неопределенных коэффициентов**. Поскольку из последней теоремы известны ограничения на степени искомых полиномов, то их можно представить в каноническом виде
$$u(x)=U_0x^{n-1} + U_1x^{n-2}+\dots + U_{n-1}, \quad
v(x)=V_0x^{m-1} + V_1x^{m-2}+\dots + V_{m-1}
$$
при $ m = \deg g(x), n = \deg f(x) $ и коэффициентах $ U_0,\dots,U_{n-1}, V_0,\dots,V_{m-1} $, которые и требуется определить. Для их нахождения используется тождество
Безу, в левой части которого после приведения подобных образуется полином $ (n+m-1) $-й степени. Поскольку этот полином должен тождественно равняться $ 1_{} $, то все его коэффициенты должны быть равными нулю, кроме свободного члена, равного $ 1_{} $. Полученная
система из $ n+m $ уравнений будет линейной относительно коэффициентов
$ U_0,\dots, U_{n-1},V_0,\dots, V_{m-1} $. Следствие к теореме гарантирует единственность решения этой системы в случае $ \operatorname{HOD}(f(x),g(x)) \equiv 1 $.
!!П!! **Пример.** Выписать систему линейных уравнений для определения полиномов $ u_{}(x) $ и $ v_{}(x) $, удовлетворяющих тождеству Безу для
$$f(x)=a_0x^2+a_1x+a_2,\ g(x)=b_0x^2+b_1x+b_2, \ a_0 \ne 0, b_0 \ne 0 \ .$$
**Решение.** В этом примере полиномы $ u_{}(x) $ и $ v_{}x) $ следует искать в виде
$$u(x)=U_0x+U_1,\ v(x)=V_0x+V_1 \ . $$
Имеем:
$$v(x)f(x)+u(x)g(x)=(V_0x+V_1)(a_0x^2+a_1x+a_2) +(U_0x+U_1)(b_0x^2+b_1x+b_2)=$$
$$=(V_0a_0+U_0b_0) x^3 + (V_0a_1+V_1a_0+U_0b_1+U_1b_0) x^2 + (V_0a_2+V_1a_1+
U_0b_2+U_1b_1)x+(V_1a_2+U_1b_2)$$
и этот полином должен тождественно равняться $ 1_{} $. Поэтому выписываем систему условий на коэффициенты:
$$
\left\{
\begin{array}{ccccc}
a_0V_0& & +b_0U_0 & &=0,\\
a_1V_0&+a_0V_1 &+b_1U_0& +b_0U_1 & =0,\\
a_2V_0&+a_1V_1 &+b_2U_0& +b_1U_1 & =0,\\
&\ a_2V_1& &+b_2U_1 &=1.
\end{array}
\right.
$$
Эта система и позволит нам определить коэффициенты $ U_0,U_1,V_0,V_1 $ по коэффициентам полиномов $ f_{}(x) $ и $ g_{}(x) $.
Пусть, например, $ a_0=1,a_1=3,a_2=1,b_0=1,b_1=-1,b_2=1 $. Решаем систему:
$$
\left\{
\begin{array}{rrrrl}
V_0& & +U_0 & &=0\\
3V_0&+V_1 &-U_0& +U_1 & =0\\
V_0&+3V_1 &+U_0& -U_1 & =0\\
&V_1& &+U_1 &=1
\end{array}
\right.
\quad
\begin{array}{c}
\Rightarrow \\ \\ \\ \Rightarrow
\end{array}
\quad
\begin{array}{rl}
V_0&=-U_0 \\
\\
\\
V_1&=1-U_1
\end{array}
\quad
\begin{array}{c}
\\ \Rightarrow \\ \Rightarrow \\
\end{array}
\quad
\left\{
\begin{array}{rl}
-3U_0+(1-U_1)-U_0+U_1&=0 \\
-U_0+3(1-U_1)+U_0-U_1&=0
\end{array}
\right.
$$
Последняя система имеет единственное решение
$ U_0= {\scriptstyle 1}/{\scriptstyle 4},\ U_1={\scriptstyle 3}/{\scriptstyle 4} $, тогда
$ V_0=-{\scriptstyle 1}/{\scriptstyle 4},\ V_1={\scriptstyle 1}/{\scriptstyle 4} $.
Окончательно: $ u(x)= {\scriptstyle 1}/{\scriptstyle 4} \, (x+3),\
v(x)={\scriptstyle 1}/{\scriptstyle 4} \, (-x+1) $.
Возьмем теперь $ a_0=1,\, a_1=4,\, a_2=-5,\, b_0=1,\, b_1=-4,\, b_2=3 $:
$$
\left\{
\begin{array}{rrrrl}
V_0& & +U_0 & &=0\\
4V_0&+V_1 &-4U_0& +U_1 & =0\\
-5V_0&+4V_1 &+3U_0& -4U_1 & =0\\
&-5V_1& &+3U_1 &=1
\end{array}
\right.
\quad
\begin{array}{c}
\Rightarrow \\ \\ \\ \Rightarrow
\end{array}
\quad
\begin{array}{rl}
V_0&=-U_0 \\
\\
\\
V_1&={\scriptstyle 3}/{\scriptstyle 5} U_1 - {\scriptstyle 1}/{\scriptstyle 5}
\end{array}
\quad
\begin{array}{c}
\\ \Rightarrow \\ \Rightarrow \\
\end{array}
\quad
\left\{
\begin{array}{rl}
-8\, U_0+{\scriptstyle 8}/{\scriptstyle 5} \,
U_1 &={\scriptstyle 1}/{\scriptstyle 5} \\
8\,U_0-{\scriptstyle 8}/{\scriptstyle 5} \, U_1 &={\scriptstyle 4}/{\scriptstyle 5}
\end{array}
\right.
$$
Последняя система не имеет решений (несовместна). Это факт свидетельствует
о том, что полиномы $ f_{}(x) $ и $ g_{}(x) $ не являются взаимно простыми. Так
оно и есть: $ \operatorname{HOD} (x^2+4\,x-5,\, x^2-4\,x+3) \equiv (x-1) $.
Итак, совместность получившейся системы линейных уравнений напрямую связана с условием
взаимной простоты полиномов $ f_{}(x) $ и $ g_{}(x) $. Это условие было нами
установлено в предыдущем примере: оно заключалось в отличии от нуля
величины $ \mathcal R(f,g) $, определяемой формулой:
$$
\mathcal R(f,g) =
b_0^2a_2^2-2\,a_0a_2b_0b_2+a_0^2b_2^2-a_1a_2b_0b_1-a_0a_1b_1b_2+
a_0a_2b_1^2+a_1^2b_0b_2
=
$$
$$
=(a_0b_2-a_2b_0)^2 -(a_0b_1-a_1b_0)(a_1b_2-a_2b_1) \ .
$$
Следовательно, эта величина должна как-то проявляться и при решении системы в ее общем виде. Так оно и оказывается:
$$
V_0=\frac{b_0(a_0b_1-a_1b_0)}{\mathcal R(f,g)} \ , \
V_1=\frac{-a_0b_0b_2+a_2b_0^2-a_1b_0b_1+a_0b_1^2}{\mathcal R(f,g)} \ , $$
$$
U_0=\frac{a_0(a_1b_0-a_0b_1)}{ \mathcal R(f,g)} \ , \
U_1=\frac{a_0^2b_2-a_0a_2b_0-a_0a_1b_1+a_1^2b_0}{\mathcal R(f,g)} \ .$$
!!?!! Найти полиномы $ u_{}(x) $ и $ v_{}(x) $, удовлетворяющие тождеству Безу при
**а)** $ f(x)=4\,x^3+3\,x^2+2\,x+1\ , \quad g(x)=x^2+2\, x+3 $;
**б)** $ f(x)=5\,x^4+4\,x^3+3\,x^2+2\,x+1\ , \quad g(x)=x^3+2\, x^2+3\,x+4 $;
**в)** $ f(x)=\displaystyle \sum_{j=1}^{n} (n-j+1)x^{n-j} \ , \quad
g(x)=\sum_{j=2}^{n} (j-1)x^{n-j} $.
Метод неопределенных коэффициентов построения полиномов $ u_{}(x) $ и $ v_{}(x) $ из тождества Безу можно развить до получения явного их выражения через коэффициенты полиномов $ f_{}(x) $ и $ g_{}(x) $ --- но для этого придется привлекать аппарат определителей. Подробнее
☞
((:dets:resultant:idea ЗДЕСЬ)).
{{users:au:scriber.jpg |}}
\\
\\
\\
Статья не закончена!
=== Уничтожение иррациональности в знаменателе==
Пусть $ f(x), g(x), g_1(x) $ --- полиномы с рациональными коэффициентами, $ \deg f=n $. Обозначим $ \lambda_1,\dots,\lambda_n $ корни $ f_{}(x) $.
**Задача.** Для ((:fraction#определения рациональной дроби)) $ g_1(x)/g(x) $ найти полином $ G_{}(x) $
c рациональными коэффициентами и такой, чтобы
$$G(\lambda_1)=g_1(\lambda_1)/g(\lambda_1),\ \dots ,\ G(\lambda_n)=g_1(\lambda_n)/g(\lambda_n)
\ .
$$
Понятно, что эта постановка имеет смысл, если $ g(\lambda_j) \ne 0 $ ни при одном $ j_{} $, т.е. полиномы $ f_{}(x) $ и $ g_{}(x) $ взаимно просты.
!!§!! Особый интерес представляет случай, когда $ f_{}(x) $ ((:polynomial#приводимость неприводим)) над множеством рациональных чисел.
!!Т!! **Теорема.** //При условии// $ \operatorname{HOD} (f,g)=1 $ //всегда существует полином// $ G_{}(x) $, //решающий поставленную задачу. При условии// $ \deg{G}{<}{n} $ //такой полином определяется единственным образом.//
**Доказательство.** Легко проверить, что полином $ u(x) $, удовлетворяющий ((#тождество_Безу тождеству Безу)):
$$ v(x)f(x)+u(x)g(x) \equiv 1 \ , $$
фактически определяет решение задачи. На произвольном корне $ \lambda_j $ полинома $ f_{}(x) $ это тождество превращается в равенство $ 1/g(\lambda_j)=u(\lambda_j) $. Таким образом, полином
$$ G(x)=g_1(x)u(x) $$
является искомым. Поскольку коэффициенты $ u_{}(x) $ --- по любому способу их построения из предыдущего пункта --- рационально выражаются через коэффициенты полиномов $ f_{}(x) $ и $ g_{}(x) $, то коэффициенты $ G_{}(x) $ будут рациональными числами. Решением поставленной задачи будет также и произвольный полином вида $ G(x) + q(x) f(x) $ при любом $ q(x) \in \mathbb Q[x] $. В частности, можно в качестве полинома $ G_{}(x) $ взять ((:polynomial#делимость_полиномов остаток)) от деления $ g_1(x)u(x) $ на $ f_{}(x) $. За счет такой возможности получаем решение задачи при указанном в теореме ограничении.
♦
!!?!! Докажите единственность полинома $ G_{}(x) $ при выполнении условия $ \deg G
♦