Инструменты сайта


§

Вспомогательная страница к разделу ПОЛИНОМ


Приводимость полиномов с целыми коэффициентами

Полином $ \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} $ обозначает наименьшее общее кратное ) тогда приводимость (или неприводимость) полинома $ 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<n, \ell < n, k+\ell = n $. Для практического решения вопроса о существовании такого разложения, сначала установим условия его существования для случая, когда один из сомножителей — линейный полином.

Целые корни

Т

Теорема. Если полином $$f(x)=a_0x^n+a_1x^{n-1} + \dots + a_n \in \mathbb Z[x] \ , a_0 \ne 0,a_n \ne 0 $$ имеет рациональный корень, представленный в виде несократимой дроби $ \lambda=\mathfrak p/\mathfrak q,\, \{{\mathfrak p}, {\mathfrak q}\}\subset \mathbb Z $, то ее числитель $ {\mathfrak p} $ является делителем свободного члена $ a_{n} $, а знаменатель $ {\mathfrak q} $ — делителем старшего коэффициента $ a_{0} $.

Доказательство. Условие $ f\left(\mathfrak p/\mathfrak q \right)=0 $ эквивалентно $$a_0{\mathfrak p}^n+a_1{\mathfrak p}^{n-1}{\mathfrak q} + \dots+ a_j{\mathfrak p}^{n-j}{\mathfrak q}^j + \dots + a_n{\mathfrak q}^n=0 \ .$$ Это равенство можно переписать либо в виде $$a_0{\mathfrak p}^n=-{\mathfrak q} \left(a_1{\mathfrak p}^{n-1} + \dots + a_j{\mathfrak p}^{n-j}{\mathfrak q}^{j-1} + \dots + a_n{\mathfrak q}^{n-1} \right)$$ либо в виде $$a_n{\mathfrak q}^n=-{\mathfrak p} \left(a_0{\mathfrak p}^{n-1}+a_1{\mathfrak p}^{n-2}{\mathfrak q} + \dots + a_{n-1}{\mathfrak q}^{n-1} \right) \ . $$ Из первого равенства следует, что $ a_0{\mathfrak p}^n $ делится на $ {\mathfrak q} $, а из второго — что $ a_n{\mathfrak q}^n $ делится на $ {\mathfrak p} $. Поскольку, по предположению теоремы, дробь $ \mathfrak p/\mathfrak q $ несократима, то $ \operatorname{HOD} (\mathfrak p,\mathfrak q )=1 $. Следовательно, число $ a_{0} $ делится на $ {\mathfrak q} $, a $ a_{n} $ — на $ {\mathfrak p} $.

Итак, для поиска рациональных корней полинома $ 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 \} $. Если ни одно из полученных чисел не равно нулю, то рациональных корней полином не имеет.

=>

Если нормализованный полином $ 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 $ факторизуется по методу Ферма за один шаг: $ 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_{} $ — простое число, и $ 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 $ также с рациональными коэффициентами. Воспользуемся результатом из раздела ☞ РЕЗУЛЬТАНТ, только с целью стыковки обозначений заменим в полиноме основную переменную на $ 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) \ . $$ По свойствам результанта, полином $ \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) $; т.е. к задаче, рассмотренной в предыдущем ПУНКТЕ. С использованием результатов ☞ ПУНКТА можно построить и метод нахождения коэффициента $ b_2 $ по найденному значению $ b_{1} $.

П

Пример. Найти квадратичные множители полинома $ f(z)=z^6+8\,z^5+17\,z^4+16\,z^3+111\,z^2+186\,z-234 $.

Решение. Рассчеты приведены ЗДЕСЬ: $$ {\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} $

для хотя бы одного простого числа $ 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 $ при любом простом $ 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 $, то, по основной теореме высшей алгебры, $ \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)<k-1/2 $ комплексной плоскости;

2. $ f(k-1)\ne 0 $;

3. $ f(k) $ — простое число

для некоторого $ k \in \mathbb Z $, то $ f_{}(x) $ неприводим в $ \mathbb Z_{} $.

Задачи

Источники

[1]. Полиа Г., Сеге Г. Задачи и теоремы из анализа. Т 2, отдел 8, глава 2. М.Наука.1978

[2]. Утешев А.Ю., Калинина Е.А. Лекции по высшей алгебре. Часть II. Учеб. пособие. СПб. «СОЛО». 2007.

polynomial/irreduc.txt · Последние изменения: 2020/05/19 10:12 — au