!!§!! Вспомогательная страница к разделу ((:polynomial ПОЛИНОМ)) ---- == Приводимость полиномов с целыми коэффициентами == ~~TOC~~ Полином $ \Phi(x) \in \mathbb A[x] $, отличный от константы, называется **неприводимым в** $ \mathbb A_{} $ если у $ \Phi(x) $ нет ((#делимость_полиномов нетривиального делителя)) в $ \mathbb A[x] $. В противном случае $ \Phi(x) $ называется **приводимым в** $ \mathbb A_{} $. Рассмотрим полином с рациональными коэффициентами: $$f(x)=a_0x^n+a_1x^{n-1}+\dots+a_n \in \mathbb Q [x] \ , \ a_0 \ne 0 \ . $$ Если полином $ f(x)_{} $ приводим в $ \mathbb Q_{} $, то будет приводимым и полином $ C\cdot f(x) $ при $ \forall C \in \mathbb Q, C \ne 0 $; верно и обратное. Представив коэффициенты $ a_0,\dots, a_n $ в виде несократимых дробей, возьмем $$ C=\operatorname{HOK}(\mbox{ знаменатель }\ a_0,\dots, \mbox{ знаменатель }\ a_n ) \ , $$ (здесь $ \operatorname{HOK} $ обозначает ((:numtheory#алгоритм_евклида наименьшее общее кратное)) ) тогда приводимость (или неприводимость) полинома $ f_{}(x) $ в $ \mathbb Q_{} $ эквивалентна приводимости (соответственно, неприводимости) в $ \mathbb Q_{} $ полинома $ C\cdot f(x) $ с целыми коэффициентами. Поэтому в дальнейшем будем сразу предполагать $ f(x)\in \mathbb Z[x] $. Можно ли пойти дальше и утверждать, что приводимость такого полинома в $ \mathbb Q_{} $ эквивалентна приводимости его в $ \mathbb Z_{} $, т.е. полином раскладывается на произведение полиномов меньших степеней с рациональными коэффициентами тогда и только тогда, когда он раскладывается на произведение полиномов меньших степеней с целыми коэффициентами? !!Т!! **Теорема.** //Полином// $ f(x)\in \mathbb Z[x] $ //неприводимый в// $ \mathbb Z_{} $ //будет неприводимым и в// $ \mathbb Q_{} $. Приводимость полинома с целыми коэффициентами $ f(x)\in \mathbb Z[x] $ в $ \mathbb Z_{} $ означает, что он раскладывается на два множителя с целыми коэффициентами: $$ a_0x^n+a_1x^{n-1}+ \dots + a_n \equiv (b_0x^k+b_1x^{k-1} + \dots + b_k) (c_0x^{\ell}+c_1x^{\ell-1} + \dots + c_{\ell}) $$ при $ k Итак, для поиска рациональных корней полинома $ f(x)_{} $ надо выписать множество всех натуральных делителей $ \{{\mathfrak p}_1=1,\dots,{\mathfrak p}_{s}\} $ числа $ |a_n| $, и множество всех натуральных делителей $ \{{\mathfrak q}_1=1,\dots,{\mathfrak q}_{t}\} $ числа $ |a_0| $, и после этого организовать вычисление $ f\left(\pm {\mathfrak p}_j/{\mathfrak q}_i \right) $ при всех возможных значениях индексов $ j\in \{1,\dots,s \}, i \in \{1,\dots, t \} $. Если ни одно из полученных чисел не равно нулю, то рациональных корней полином не имеет. !!=>!! Если ((:polynomial#поиск_корней_алгебраических_уравненийрешение_в_радикалах нормализованный полином)) $ f(x) \in \mathbb Z[x] $ имеет рациональные корни, то они --- только целые и находятся среди делителей свободного члена. !!П!! **Пример.** Найти рациональные корни полинома $$f(x)=6\,x^6-55\, x^5+331\, x^3-86\,x^4+289\,x^2-25\,x+350 \ . $$ **Решение.** Выписываем множества делителей \\ для $ 350\ : \quad \{1,\, 2 ,\, 5 ,\, 7,\, 10,\, 14,\, 25 ,\, 35,\, 50,\, 70,\, 175 \} $ и для $ 6\ : \ \{1,\, 2,\, 3,\, 6 \} $. \\ Составляем всевозможные несократимые дроби: $$ \left\{ \begin{array}{ccccccccccc} 1,& 2 ,& 5 ,& 7,& 10,& 14,& 25 ,& 35,& 50,& 70,& 175, \\ {\scriptstyle 1}/{\scriptstyle 2},& & {\scriptstyle 5}/{\scriptstyle 2} ,& {\scriptstyle 7}/{\scriptstyle 2}, & & & {\scriptstyle 25}/{\scriptstyle 2} & {\scriptstyle 35}/{\scriptstyle 2}, & & & {\scriptstyle 175}/{\scriptstyle 2}, \\ {\scriptstyle 1}/{\scriptstyle 3},& {\scriptstyle 2}/{\scriptstyle 3},& {\scriptstyle 5}/{\scriptstyle 3},& {\scriptstyle 7}/{\scriptstyle 3},& {\scriptstyle 10}/{\scriptstyle 3},& {\scriptstyle 14}/{\scriptstyle 3},& {\scriptstyle 25}/{\scriptstyle 3},& {\scriptstyle 35}/{\scriptstyle 3},& {\scriptstyle 50}/{\scriptstyle 3},& {\scriptstyle 70}/{\scriptstyle 3},& {\scriptstyle 175}/{\scriptstyle 3}, \\ {\scriptstyle 1}/{\scriptstyle 6},& & {\scriptstyle 5}/{\scriptstyle 6}, & {\scriptstyle 7}/{\scriptstyle 6}, & & & {\scriptstyle 25}/{\scriptstyle 6},& {\scriptstyle 35}/{\scriptstyle 6},& & & {\scriptstyle 175}/{\scriptstyle 6} \end{array} \right\} $$ Подставляем все эти значения со знаками $ +_{} $ и $ - $ в $ f(x)_{} $ и проверяем (например, с использованием ((#схема_хорнера схемы Хорнера)) ) на равенство нулю. **Ответ.** $ 10,\, {\scriptstyle 5}/{\scriptstyle 2},\, -{\scriptstyle 7}/{\scriptstyle 3} $. !!П!! **Пример [Гаусс]** ((#источники [1])). Доказать, что полином $ f(x) \in \mathbb Z[x] $ не имеет целых корней если оба числа $ f(0) $ и $ f(1) $ --- нечетные. **Решение.** Пусть $ f(k)=0 $ при $ k\in \mathbb Z $. Тогда $ f(x)\equiv (x-k)\varphi(x) $ при $ \varphi(x) \in \mathbb Z[x] $. Подставляем в это тождество $ x=0 $ и $ x=1 $: $$ f(0)=-k\varphi(0),\quad f(1)=(1-k)\varphi(1) \ . $$ Из двух последовательных чисел $ \{ 1-k,-k \} $ одно --- обязательно четное. Но тогда либо число $ f(0) $ --- четное, либо число $ f(1) $ --- четное. ===Нелинейные множители== Из того факта, что полином $ f(x) \in \mathbb Z[x] $ не имеет рациональных корней не следует, что он неприводим в $ \mathbb Z_{} $: в разложении $ f(x)\equiv f_1(x)f_2(x) $ сомножители могут оказаться и нелинейными. Как их определить? Обратим внимание на то обстоятельство, что тождество $ f(x)\equiv f_1(x)f_2(x) $ должно иметь место __при всех__ $ x\in \mathbb C $ и, в частности, при $ x\in \mathbb N $. Таким образом, если мы подставим, например, значение $ x=10 $, то тождество обратится в равенство $$a_0 10^n+a_1 10^{n-1}+ \dots + a_n= (b_0 10^k+b_1 10^{k-1} + \dots + b_k) (c_0 10^{\ell}+c_1 10^{\ell-1} + \dots + c_{\ell}) \ ,$$ которое означает, что число $$A= f(10)= a_0 10^n+a_1 10^{n-1}+ \dots + a_n$$ должно разложиться на два целых сомножителя. Если теперь предположить, что дополнительно известна информация, о том, что все коэффициенты $ b_0,\dots, b_k $ принимают значения из $ \{0,1,2,\dots, 9\} $, то эти коэффициенты обязательно найдутся среди цифр десятичного представления одного из делителей числа $ A_{} $, т.к. $$A=\underline{b_0b_1\dots b_k} \cdot (c_0 10^{\ell}+c_1 10^{\ell-1} + \dots + c_{\ell}) \ .$$ !!П!! **Пример.** Найти нетривиальные делители полинома $$f(x)=x^6+5\,x^5+10\,x^4+31\,x^3+18\,x^2+42\,x+63$$ в $ \mathbb Z[x] $ если известно, что один из них имеет коэффициенты в интервале $ [0,9] $. **Решение.** Число $ A=f(10)=1633283 $ факторизуется по ((:numtheory#факторизация методу Ферма)) за один шаг: $ A=1277\cdot 1279 $. Оба сомножителя --- простые. Используя дополнительную информацию о величине коэффициентов делителя $ f_{}(x) $, можем предсказать возможный вид этого делителя: либо $ \quad x^3+2\, x^2 + 7\, x + 7 $ , либо $ x^3+2\, x^2 + 7\, x + 9 $. Проверка делением подтверждает, что делителем является только первый полином. **Ответ.** $ f(x) \equiv (x^3+2\,x^2+7\,x+7)(x^3+3\,x^2-3\,x+9) $. !!Т!! **Теорема** ((#источники [1])). //Если// $ p_{} $ --- //((:numtheory#простые_числа простое число)), и// $ p=\underline{\mathfrak{b}_0\mathfrak{b}_1\dots \mathfrak{b}_n} $ --- //его десятичное представление// ($ \mathfrak{b}_0\ne 0 $), //то полином// $ f(x)=\mathfrak{b}_0x^n+\mathfrak{b}_1x^{n-1}+\dots+\mathfrak{b}_n $ //неприводим в// $ \mathbb Z_{} $. ====Квадратичные множители== Требуется выяснить существует ли у полинома $ f_{}(x) $ с рациональными коэффициентами множитель второй степени $ f_1(x)=x^2+b_1x+b_2 $ также с рациональными коэффициентами. Воспользуемся результатом из раздела ☞ ((:dets:resultant#поиск_мнимого_корня_полинома РЕЗУЛЬТАНТ)), только с целью стыковки обозначений заменим в полиноме основную переменную на $ z_{} $: $$ f(z)=f(x+ \mathbf i y)=f(x)+{f'(x)\over 1!}\mathbf i \,y+{f''(x)\over 2!}(\mathbf i \, y)^2+ \dots+{f^{(n)}(x)\over n!}(\mathbf i \,y)^n=$$ $$=\left[ f(x)-{f''(x)\over 2!}y^2+{f^{(4)}(x)\over 4!}y^4-\dots\right]+\mathbf i \,y\left[ {f'(x)\over 1!}-{f'''(x)\over3!}y^2+{f^{(5)}(x)\over 5!}y^4-\dots\right]= $$ $$ =F_1(x,Y)+\mathbf i \,yF_2(x,Y) $$ при $$ Y= -y^2 \ , \left\{ \begin{array}{ccc} F_1(x,Y)&= & \displaystyle{f(x)+{f''(x)\over 2!}Y+{f^{(4)}(x)\over 4!}Y^2+\dots,} \\ \\ F_2(x,Y)&=&\displaystyle{{f'(x)\over 1!}+{f'''(x)\over 3!}Y+{f^{(5)}(x)\over 5!}Y^2+\dots} \end{array} \right. $$ Полиномы $ F_{1} $ и $ F_{2} $ имеют рациональные коэффициенты. Составим результант этих полиномов, рассматривая их как полиномы от $ Y_{} $ (элиминанту по переменной $ x_{} $): $$ \mathcal X(x) = {\mathcal R}_Y(F_1,F_2) \ . $$ По ((:dets:resultant#результант_как_полиномиальная_функция_коэффициентов свойствам результанта)), полином $ \mathcal X(x) $ имеет рациональные коэффициенты. !!Т!! **Теорема** ((#источники [2])).//Если// $ f(z)\in \mathbb Q[z] $ //имеет делитель вида// $ z^2+b_1z+b_2 \in \mathbb Q[z] $, //то полином// $ \mathcal X_{}(x) $ //имеет рациональный корень равный// $ (-b_1/2) $. Эта теорема сводит задачу поиска квадратичных множителей полинома $ f_{}(z) $ к задаче поиска рациональных корней полинома $ \mathcal X_{}(x) $; т.е. к задаче, рассмотренной в предыдущем ((#целые_корни ПУНКТЕ)). С использованием результатов ☞ ((:dets:resultant#поиск_мнимого_корня_полинома ПУНКТА)) можно построить и метод нахождения коэффициента $ b_2 $ по найденному значению $ b_{1} $. !!П!! **Пример.** Найти квадратичные множители полинома $$ f(z)=z^6+8\,z^5+17\,z^4+16\,z^3+111\,z^2+186\,z-234 \, .$$ **Решение.** Рассчеты приведены ((:dets:resultant#поиск_мнимого_корня_полинома ЗДЕСЬ)): $$ {\mathcal X}(x) = \left| \begin{array}{ccccc} f^{(6)}(x)/6! & f^{(4)}(x)/4! & f''(x)/ 2! & f(x) & \\ & f^{(6)}(x)/6! & f^{(4)}(x)/4! & f''(x)/ 2! & f(x) \\ & & f^{(5)}(x)/5! & f'''(x)/ 3! & f'(x) \\ & f^{(5)}(x)/5! & f'''(x)/ 3! & f'(x) & \\ f^{(5)}(x)/5! & f'''(x)/ 3! & f'(x) & & \end{array} \right|= $$ $$ =32768\,x^{15}+655360\,x^{14}+5799936\,x^{13}+30015488\,x^{12}+100876288\,x^{11}+230633472\,x^{10}+ $$ $$ +368112640\,x^9+437983232\,x^8+492254208\,x^7+660542464\,x^6+744333056\,x^5+229265856\,x^4- $$ $$ -794443896\,x^3-1341883872\,x^2-916140960\,x-248036040 $$ имеет рациональные корни $ \alpha_{1}=1, \, \alpha_{2}=-7/2, \, \alpha_3=-3/2 $. **Ответ.** $ f(z)\equiv (z^2+3\,z-3)(z^2-2\,z+6)(z^2+7\,z+13) $. ===Критерии неприводимости== !!§!! Результаты этого пункта взяты из ((#источники [1])). !!Т!! **Теорема 1 [Эйзенштейн].** //Если коэффициенты полинома// $$f(x)=a_0x^n+a_1x^{n-1} + \dots + a_n \in \mathbb Z[x] \ , a_0 \ne 0,a_n \ne 0 $$ //удовлетворяют условиям:// 1. $ a_1,\dots,a_n $ //делятся на// $ p_{ } $; 2. $ a_{0} $ не делится на $ p_{ } $; 3. $ a_{n} $ не делится на $ p^{2} $ //для хотя бы одного ((:numtheory#простые_числа простого числа))// $ p_{} $, //то полином// $ f_{}(x) $ //неприводим в// $ \mathbb Z_{} $. **Доказательство.** Если для $ f_{}(x) $ существует разложение в произведение полиномов с целыми коэффициентами $$ a_0x^n+a_1x^{n-1}+ \dots + a_n \equiv (b_0x^k+b_1x^{k-1} + \dots + b_k) (c_0x^{\ell}+c_1x^{\ell-1} + \dots + c_{\ell}) \ , $$ то, сравнивая коэффициенты при $ 1,x,x^2,\dots,x^n $ в левой и правой частях этого тождества, получаем систему равенств $$ \left\{ \begin{array}{lcl} a_n&=&b_k c_{\ell} \ , \\ a_{n-1} &=& b_k c_{\ell-1} + b_{k-1} c_{\ell} \ , \\ a_{n-2} &=& b_k c_{\ell-2} + b_{k-1} c_{\ell-1} + b_{k-2} c_{\ell} \ , \\ \dots & & \dots \\ a_0 &=&b_0c_0 \end{array} \right. $$ Поскольку, по предположению 1 теоремы, $ a_{n} $ делится на простое $ p_{} $ то какой-то из множителей $ b_k $ или $ c_{\ell} $ должен делиться на $ p_{} $. Однако оба они не могут одновременно делиться на $ p_{} $, т.к. тогда число $ a_{n} $ делилось бы на $ p^2 $, что противоречило бы предположению 3 теоремы. Пусть, например, $ b_k $ делится на $ p_{} $, тогда $ c_{\ell} $ не делится на $ p_{} $. Переходим ко второму из равенств системы. Получаем, что, поскольку и $ a_{n-1} $ и $ b_k c_{\ell-1} $ делятся на $ p_{} $, то и их разность, т.е. $ b_{k-1} c_{\ell} $, делится на $ p_{} $. Однако $ c_{\ell} $ на $ p_{} $ не делится, значит $ b_{k-1} $ делится на простое $ p_{} $. Аналогичными рассуждениями над третьим равенством системы докажем, что и $ b_{k-2} $ делится на $ p_{} $ и т.д., наконец, из $ (k+1) $-го равенства получим, что и $ b_{0} $ делится на $ p_{} $, но тогда из последнего равенства следует, что и $ a_{0} $ делится на $ p_{} $, что противоречит предположению 2 теоремы. !!=>!! Существуют неприводимые в $ \mathbb Z_{} $ полиномы произвольной степени $ n_{}>1 $. Такими полиномами являются, например, $ x^n+2 $ или $ x^n+p\, x^{n-1} + p\, x^{n-2} + \dots + p $ при любом ((:numtheory#простые_числа простом)) $ p_{} $. !!Т!! **Теорема 2 [Шур]**. //Полином// $$ (x-a_1)(x-a_2)\times \dots \times (x-a_n)-1 $$ //при различных числах// $ \{a_1,a_2,\dots,a_n\} \subset \mathbb Z $ //неприводим в// $ \mathbb Z_{} $. **Доказательство.** Если $$ (x-a_1)(x-a_2)\times \dots \times (x-a_n)-1 \equiv \varphi(x) \psi(x) \ npu \quad \{ \varphi(x), \psi(x) \}\subset \mathbb Z[x] \ , $$ то $ \varphi(a_j) \psi(a_j) =-1 $, и, следовательно, $ \varphi(a_j)=\pm 1 $, а $ \psi(a_j) =\mp 1 $. Но тогда полином $ \varphi(x)+\psi(x) $ обращается в нуль при $ x\in \{a_j\}_{j=1}^n $. Если оба полинома имеют степень $ \le n-1 $, то, по ((:polynomial#основная_теорема_высшей_алгебры основной теореме высшей алгебры)), $ \varphi(x)\equiv - \psi(x) $. Тогда $$ (x-a_1)(x-a_2)\times \dots \times (x-a_n)-1 \equiv - \left[ \varphi(x) \right]^2 \ , $$ что невозможно поскольку старшие коэффициенты полиномов имеют разные знаки. !!Т!! **Теорема 3 [Шур]**. //Полином// $$ (x-a_1)^2(x-a_2)^2\times \dots \times (x-a_n)^2+1 , $$ //при различных числах// $ \{a_1,a_2,\dots,a_n\} \subset \mathbb Z $ //неприводим в// $ \mathbb Z_{} $ !!Т!! **Теорема 4**. //Если// $ f(x)\in \mathbb Z[x] $ //удовлетворяет условиям//: 1. //Корни полинома// $ f_{}(x) $ //лежат в полуплоскости// $ \mathfrak R\mathbf e (z) 2. $ f(k-1)\ne 0 $; 3. $ f(k) $ --- //((:numtheory#простое_число простое число))// //для некоторого// $ k \in \mathbb Z $, //то// $ f_{}(x) $ //неприводим в// $ \mathbb Z_{} $. ==Задачи== ((:polynomial:irreduc:problems ЗДЕСЬ)) ==Источники== [1]. **Полиа Г.**, **Сеге Г.** //Задачи и теоремы из анализа. Т 2, отдел 8, глава 2.// М.Наука.1978 [2]. **Утешев А.Ю., Калинина Е.А.** //Лекции по высшей алгебре. Часть II.// Учеб. пособие. СПб. «СОЛО». 2007.