Стерлитамакский филиал ФГБОУВПО «Башкирский государственный университет»
Методы Гензеля. Разложение на множители многочлена с целыми коэффициентами
Чернова Елена Алексеевна,
студентка, 2 курс, факультет математики и информационных технологий
Биккулова Г.Г., кандидат физико-математических наук, доцент кафедры «Алгебра, геометрия и методика обучения математике»
г. Стерлитамак
Аннотация
В статье рассматриваются алгоритмы решения полиномиальных уравнений и систем в полях алгебраических чисел, которые основаны на лемме о подъеме решения полиномиального сравнения, впервые предложенной К. Гензелем.
Ключевые слова: многочлен, лемма, алгоритм, полиноминальное уравнение, алгебраические числа.
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-адических чисел.
При доказательстве данного утверждения Гензель описал алгоритм нахождения многочленов fk(x) и gk(x), k 6 N, удовлетворяющих условию
F(x) = fk(x) gk(x) (mod),
с помощью уже известных fk-i(x) и gk-i(x).
В 1905 г. в работе «О новом старте теории алгебраических чисел» он сформулировал другой вариант леммы.
Утверждение 2. Пусть F(x) - многочлен с целыми p-адическими коэффициентами, а у - целое p-адическое число, удовлетворяющее условиям: F(y) = 0 (mod p) u
p < 1,
где |-|p - p-адическая норма числа. Тогда можно найти целое р - адическое число у1, такое, что у1 = у (mod p) и
F(yi) = 0
в кольце целых р-адических чисел [2].
В данном виде лемма Гензеля обычно формулируется в современной литературе.
Для того, чтобы разобраться с разложением на множители многочлена с целыми коэффициентами докажем следующую теорему.
Теорема 1. Пусть
f(x) = хп + diX'1»1… + ап
приведенный многочлен n-й степени, все коэффициенты которого - целые числа. Тогда любой рациональный корень этого многочлена - целое число.
Доказательство. Пусть = - корень многочлена f(x) причем q 2 и - несократимая дробь. Тогда имеет место равенство f() = 0, то есть
Умножим обе части этого равенства на Все члены, кроме первого, окажутся целыми числами, а тогда и должно было бы быть целым числом. Но это не так: поскольку р и q не имеют общих делителей, то их не имеют и и q. Значит, многочлен Ц(х) не может иметь рациональных корней, не являющихся целыми числами.
Перейдем к отысканию целых корней многочлена. Тогда имеет место следующая теорема.
Теорема 2. Пусть
/(*) = хл + +… 4- X + ап
приведенный многочлен с целыми коэффициентами. Любой целый корень этого многочлена является делителем его свободного члена.
Доказательство. Пусть целый корень многочлена Ц(х). Тогда имеет место равенство
а'1 + аіа^ +… а + ап = 0.
Которое можно записать так:
ап = - aia, «-1 - f а&п~2 + … +
Так как и ai,…, an-i - целые числа, то выражение в скобках - целое число. Отсюда и следует, что an делится на.
Из теоремы 2 вытекает следующий метод нахождения целых корней приведенного многочлена с целыми коэффициентами: надо выписать все делители свободного члена и по очереди подставить их в многочлен. Те делители, подстановка которых обратит многочлен в нуль, и являются его целыми корнями. Других целых корней этот многочлен не имеет. Для каждого найденного корня надо определить его кратность.
Для того, чтобы уменьшить число проверяемых корней, полезно воспользоваться следующим обобщением теоремы 2.
Теорема 3. Пусть
f(x) = хп + а^п~1 4… 4- X + ап
приведенный многочлен с целыми коэффициентами и - его целый корень. Тогда для любого целого k число f(k) делится на k.
Для доказательства воспользуемся теоремой Безу. По этой теореме остаток от деления f(x) на (х - k) равен f(k). Поэтому f(x) = q(x) (x - k) + f(k). Подставим в обе части равенства x= Так как - корень многочлена f(x), то f() = 0 и мы получаем: 0 = q() (- k) + f(k). Таким образом,
№ = ~ tfa) (a - k). (1)
Так как q() - целое число, то из равенства (1) следует, что f(k) делится на k.
В силу доказанной теоремы отбор чисел, подлежащих проверке, надо проводить так. Сначала берут все делители свободного члена. Пусть это будут числа і,…, 8. После этого вычисляют ДТ). Если т - корень многочлена Ц(х), то (т - 1) должно быть делителем Ц(1). Поэтому из чисел 1,…, 8 выбирают те, для которых (т - 1) является делителем Д1). После этого вычисляют Ц(-1) и выбирают из оставшихся чисел то, для которых (m + 1) - делитель f(-1). Если и после этого осталось слишком много «претендентов», то вычисляют f(2) и берут те из оставшихся чисел, для которых (m - 1) - делитель f(2) [3].
Список использованной литературы
1. Е.Н. Алексеева. Математический анализ. Учебно-методическое пособие для студентов экономических специальностей. ОГУ, 2015. - 176 с.
2. Галиева Л.И., Галяутдинов И.Г. Класс многочленов со свойствами круговых многочленов // Вестник ТГГПУ. 2015. №15. URL: https://cyberleninka.ru/article/n/klass-mnogochlenov-so-svoystvami-krugovyh-mnogochlenov (дата обращения: 23.12.2018).
3. Виленкин Н.Я., Мордкович А.Г., Куницкая Е.С. Математический анализ. М.: Просвещение, 2016. - с. 27.