Признак Дюма. 
Приводимые и неприводимые многочлены

Пусть pфиксированное простое число, — многочлен с целыми коэффициентами, причем A₀A_n? 0. Запишем ненулевые коэффициенты многочлена f в виде, где a_i— целое число, не делящееся на p. Каждому ненулевому коэффициенту сопоставим точку на плоскости с координатами (i, a_i). По этим точкам можно построить диаграмму Ньютона многочлена f (соответствующую простому числу p). Делается это следующим образом. Пусть P₀ = (0,a₀) и P₁ = (i₁,), где i₁— наибольшее целое число, для которого ниже прямой P₀P₁ нет данных точек. Пусть, далее, P₂ = (i₂,), где i₂— наибольшее целое число, для которого ниже прямой P₁P₂ нет данных точек. Самый последний отрезок имеет вид P_r-1P_r, где P_r = (n, a_n). Если звенья ломаной P₀ … P_r проходят через точки с целочисленными координатами, то все эти точки мы тоже считаем вершинами ломаной. Полученную в результате ломаную Q₀ … Q_r+s называют диаграммой Ньютона (здесь Q₀ = P₀ и Q_r+s = P_r). Отрезки P_lP_l+1 и Q_iQ_i+1 будем называть, соответственно, сторонами и звеньями диаграммы Ньютона, а векторы будем называть векторами звеньев диаграммы Ньютона.

Рассмотрим систему векторов звеньев диаграммы Ньютона, взяв каждый вектор с учетом его кратности, т. е. столько раз, сколько он входит в число векторов звеньев.

Теорема (Дюма). Пусть f = gh, где f, g и hмногочлены с целыми коэффициентами. Тогда система векторов звеньев для многочлена f представляет собой объединение систем векторов звеньев для g и h. (Простое число p для всех многочленов берется одно и то же.).

Доказательство. Пусть, и (числа a_i, b_j, c_k не делятся на p). Возьмем некоторую сторону P_lP_l+1 диаграммы Ньютона многочлена f (сторона P_lP_l+1 может состоять из нескольких звеньев диаграммы Ньютона). Пусть точки P_l и P_l+1 имеют соответственно координаты (i_{_}, a_{i_}) и (i₊, a_i+). Наклоны P_lP_l+1 равен.

.

Пусть и, где t > 0- наибольший общий делитель чисел и. Тогда M= A/I, причем (A, I) = 1.

Рассматриваемая сторона P_lP_l+1 диаграммы Ньютона лежит на прямой, где. По условию все точки (i, a_i), i = = 0,1, …, n, лежат не ниже этой прямой, т. е., причем это неравенство строгое при i i₊. Будем называть число Ia_i — Ai весом монома ap^axⁱ, где (a, p) = 1. Числа i_ и i₊ однозначно определяются как наименьший и наибольший показатели степени x мономов многочлена f с минимальным весом.

Для многочлена g рассмотрим величину.

И определим j_ и j₊ как наименьший и наибольший индексы, для которых .

Аналогично для многочлена h рассмотрим величину.

И определим k_ и k₊ как наименьший и наибольший индексы, для которых .

Ясно, что.

Вес произведения двух членов равен сумме их весов, поэтому вес слагаемого с j = j_ и k = k_ равен G + H. Веса всех остальных слагаемых строго больше G + H, так как для них j < j_ или k < k_. В самом деле, пусть, например, j < j_. Тогда вес члена строго больше G, а вес члена не меньше H.

Вес члена ()() при j + k = const монотонно возрастает с возрастанием, поскольку I > 0. В рассматриваемом случае j + k = j_ + + k_, поэтому сумма строго минимальна при j = j_ и k = k_. Следовательно, вес члена равен G + H. Ясно также, что при i < j_ + k_ вес члена строго больше G + H, а при i? j_ + k_ вес члена не меньше G + H. Следовательно, G + H = F и j_ + k_ = i_.

Таким образом,. (1).

В частности, одно из чисел и отлично от нуля.

Если оба числа и отличны от нуля, то отрезок с концами и является стороной диаграммы Ньютона многочлена g, а отрезок с концами () и () является стороной диаграммы Ньютона многочлена h. Наклон сторон в обоих случаях равен M = =A/I, так как.

Соотношение (1) показывает, что сумма длин сторон с наклоном M диаграмм Ньютона многочленов g и h равна длине стороны (с тем же самым наклоном M) диаграммы Ньютона многочлена f.

Если же одно из чисел и равно нулю, то у диаграммы Ньютона одного из многочленов g и h есть сторона с наклоном M, причем ее длина равна длине стороны диаграммы Ньютона многочлена f, а у диаграммы Ньютона другого многочлена сторон с наклоном M нет.

Итак, вектор стороны с наклоном M диаграммы Ньютона многочлена f равен сумме векторов сторон с тем же наклоном M диаграмм Ньютона многочленов g и h. Соотношение (1) показывает, что если у одной из диаграмм Ньютона многочленов g и h есть сторона с некоторым наклоном M, то у диаграммы Ньютона многочлена f тоже должна быть сторона с таким наклоном. многочлен неприводимый временной экономический.