УказательРазделыОбозначенияАвторО проекте


§

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


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

Полином \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}( знаменатель \ a_0,\dots, знаменатель \ 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 [Эйзенштейн]. Если коэффициенты полинома

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].

Задачи

Источники

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

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


2014/10/24 00:55 редактировал au