Методы Гензеля. Разложение на множители многочлена с целыми коэффициентами

Аннотация

В статье рассматриваются алгоритмы решения полиномиальных уравнений и систем в полях алгебраических чисел, которые основаны на лемме о подъеме решения полиномиального сравнения, впервые предложенной К. Гензелем.

Ключевые слова: многочлен, лемма, алгоритм, полиноминальное уравнение, алгебраические числа.

Abstract

Methods of Hansel. Factorization of a polynomial with integer coefficients

The article deals with algorithms for solving polynomial equations and systems in the fields of algebraic numbers, which are based on the Lemma of lifting the solution of polynomial comparison, first proposed by K. Hansel.

Keywords: polynomial, Lemma, algorithm, polynomial equation, algebraic numbers.

Основная часть

гензель алгебра алгоритм полиномиальный

Решение уравнений и систем в различных кольцах и полях является одной из классических задач алгебры и теории чисел. Среди методов ее решения можно отдельно выделить связанные с подъемом. Идея данных алгоритмов состоит в том, чтобы сначала с помощью подъема решения полиномиального сравнения или системы найти корень по модулю некоторого простого числа, а потом с помощью оценки величины решения получить точный ответ [1].

Впервые идею подъема решения полиномиального сравнения высказал К. Гензель в своей программной статье «Новые основы арифметики» в 1904 г. в следующем виде:

Утверждение 1. Пусть F(x) - многочлен с целыми р адическими коэффициентами, причем р t D(F), где D(F) - дискриминант многочлена F(x). Тогда при условии, что найдено разложение

F(x) = fo(x) go(x) (mod p),

можно найти такие многочлены f(x) и g(x), что

F(x) = f(x) g(x)

в кольце целых p-адических чисел.

При доказательстве данного утверждения Гензель описал алгоритм нахождения многочленов f_k(x) и g_k(x), k 6 N, удовлетворяющих условию

F(x) = fk(x) gk(x) (mod),

с помощью уже известных f_k-i(x) и g_k-i(x).

В 1905 г. в работе «О новом старте теории алгебраических чисел» он сформулировал другой вариант леммы.

Утверждение 2. Пусть F(x) - многочлен с целыми p-адическими коэффициентами, а у - целое p-адическое число, удовлетворяющее условиям: F(y) = 0 (mod p) u

p ^{< 1},

где |-|_p - p-адическая норма числа. Тогда можно найти целое р - адическое число у₁, такое, что у₁ = у (mod p) и

F(yi) = 0

в кольце целых р-адических чисел [2].

В данном виде лемма Гензеля обычно формулируется в современной литературе.

Для того, чтобы разобраться с разложением на множители многочлена с целыми коэффициентами докажем следующую теорему.

Теорема 1. Пусть

f(x) = х^п + diX'¹»¹… + а_п

приведенный многочлен n-й степени, все коэффициенты которого - целые числа. Тогда любой рациональный корень этого многочлена - целое число.

Доказательство. Пусть = - корень многочлена f(x) причем q 2 и - несократимая дробь. Тогда имеет место равенство f() = 0, то есть

Умножим обе части этого равенства на Все члены, кроме первого, окажутся целыми числами, а тогда и должно было бы быть целым числом. Но это не так: поскольку р и q не имеют общих делителей, то их не имеют и и q. Значит, многочлен Ц(х) не может иметь рациональных корней, не являющихся целыми числами.

Перейдем к отысканию целых корней многочлена. Тогда имеет место следующая теорема.

Теорема 2. Пусть

/(*) = х^л + +… 4- X + а_п

приведенный многочлен с целыми коэффициентами. Любой целый корень этого многочлена является делителем его свободного члена.

Доказательство. Пусть целый корень многочлена Ц(х). Тогда имеет место равенство

а'¹ + аіа^ +… а + а_п = 0.

Которое можно записать так:

а_п = - aia, «-¹ - f а&^п~² + … +

Так как и ai,…, a_n-i - целые числа, то выражение в скобках - целое число. Отсюда и следует, что a_n делится на.

Из теоремы 2 вытекает следующий метод нахождения целых корней приведенного многочлена с целыми коэффициентами: надо выписать все делители свободного члена и по очереди подставить их в многочлен. Те делители, подстановка которых обратит многочлен в нуль, и являются его целыми корнями. Других целых корней этот многочлен не имеет. Для каждого найденного корня надо определить его кратность.

Для того, чтобы уменьшить число проверяемых корней, полезно воспользоваться следующим обобщением теоремы 2.

Теорема 3. Пусть

f(x) = хп + а^п~1 4… 4- X + ап