В данном параграфе мы рассмотрим определение наибольшего общего делителя (НОД) двух элементов и алгоритмы его вычисления.
Пусть R — коммутативное кольцо с единицей, $$a,b\in
R$$. Мы говорим, что a делит b и пишем a|b, если существует элемент $$c\in R$$,
такой, что $$b=a\cdot c$$ ; если такого элемента не существует, то мы говорим, что a не делит b, и пишем $$a\nmid b$$. Заметим, что определение
делимости зависит от рассматриваемого кольца. Так, например, $$2 \mid 3$$
в поле рациональных чисел $$\mathbb Q$$, но $$2 \nmid 3$$ в кольце целых чисел $$\mathbb Z$$.
5.1. ОПРЕДЕЛЕНИЕ. Ненулевой элемент $$a \in R$$ такой, что ab = 0
для некоторого $$b \ne 0$$ называется делителем нуля кольца R, а элемент $$\varepsilon \in R$$, такой, что $$\varepsilon | 1$$ называется обратимым, или делителем
единицы, или единицей кольца R.
5.2. ОПРЕДЕЛЕНИЕ. Коммутативное кольцо с единицей и без де- лителей нуля называется областью целостности или просто областью.
5.3. ОПРЕДЕЛЕНИЕ. Пусть R — коммутативное кольцо с единицей. Элемент $$a \in R$$ называется неприводимым, если из представления a = bc в виде произведения двух элементов кольца R, следует,
что хотя бы один из элементов b и c обратим в R.
5.4. ОПРЕДЕЛЕНИЕ. Пусть R — коммутативное кольцо с едини-
цей. Идеал $$I\subset R$$ называется простым, если из $$bc \in I$$ следует, что
хотя бы один из элементов b и c лежит в I.
5.5. ОПРЕДЕЛЕНИЕ. Мы говорим, что идеал I порожден элементами b1, . . . , bn, и пишем I = (b1, . . . , bn), если $$b_{1}, . . . , b_{n} \in I$$ и любой
элемент $$b \in I$$ может быть записан в виде $$b=\sum\limits_{i=1}^nc_ib_i$$ где $$c_{i} \in R$$.
5.6. ОПРЕДЕЛЕНИЕ. Идеал I называется главным, если I = (b)
для некоторого элемента $$b \in I$$. Кольцо R называется кольцом главных идеалов, если любой идеал кольца R является главным.
5.7. УПРАЖНЕНИЕ. Показать, что Z и k[x] — кольца главных идеалов, а $$\mathbb Z[x]$$ и k[x, y] — нет.
5.8. УПРАЖНЕНИЕ. Показать, что главный идеал (b) является простым тогда и только тогда, когда b — неприводимый элемент.
5.9. ОПРЕДЕЛЕНИЕ. Элементы a и b кольца R называются ассоциированными, если $$a = \varepsilon \cdot b$$, где $$\varepsilon$$ — единица (обратимый элемент)
кольца R.
5.10. ОПРЕДЕЛЕНИЕ. Кольцо R называется факториальным или
кольцом с однозначным разложением на множители, если любой
элемент $$a \in R$$ можно представить в виде $$a = \varepsilon \cdot p_{1} \cdot\cdot\cdot pn$$, где $$\varepsilon$$ —
единица, а pi — неприводимые, причем если $$a = \varepsilon _{1} \cdot q_{1} \cdot\cdot\cdot q_{m}$$ — другое такое разложение, то m = n и для любого индекса i существует
индекс j, такой, что pi ассоциировано с qj.
5.11. ЛЕММА. Пусть R — область главных идеалов. Если элемент $$a \in R$$ допускает разложение на неприводимые множители,
то это разложение однозначно в смысле предыдущего определения.
ДОКАЗАТЕЛЬСТВО оставим читателю в качестве упражнения.
5.12. УПРАЖНЕНИЕ. Показать, что $$\mathbb Z[x]$$ и k[x, y] — факториальные
кольца.
Сформулируем (без доказательства) теорему, которая позволяет получать новые факториальные кольца.
5.13. ТЕОРЕМА. Если R — факториальное кольцо, то кольцо
многочленов R[x] также факториально.
Приведем пример нефакториального кольца.
5.14. ПРИМЕР. Кольцо $$\mathbb Z [\sqrt{-5}]$$ — нефакториально. В частности, $$9=3\cdot3=(2+\sqrt{-5})(2-\sqrt{-5})$$ — два различных разложения числа 9 на неприводимые множители в этом кольце.
5.15. ОПРЕДЕЛЕНИЕ. Пусть R — коммутативное кольцо с единицей, $$a, b \in R$$. Элемент $$d \in R$$ называется наибольшим общим делителем элементов a и b, если d | a, d | b и для любого другого элемента d', такого, что d' | a и d' | b выполняется соотношение d' | d.
5.16. УПРАЖНЕНИЕ. Показать, что в кольце $$\mathbb Z$$ для любых целых
чисел a и b, не равных одновременно нулю, существует наибольшее
целое число, которое делит a и b, и это число является наибольших
общим делителем чисел a и b в смысле определения 5.15. Показать,
что определение 5.15 в кольце $$\mathbb Z$$ определяет НОД( a, b ) неоднозначно.
5.17. УПРАЖНЕНИЕ. Показать, что в кольце k[x] многочленов от
одной переменной x над полем k для любых многочленов a и b,
не равных одновременно нулю, существует многочлен наибольшей
степени, который делит a и b, и этот многочлен является наибольшим общим делителем элементов a и b в смысле определения 5.15.
Показать, что определение 5.15 в кольце k[x] определяет НОД( a, b )
неоднозначно.
НОД(a, a) = {a,-a}НОД(a, 0) = {a,-a}НОД(a, b) = НОД(b, a)НОД(c · a, c · b) = c · НОД(a, b)НОД(a, c) = {1,-1} (в частности, если c = -1 ), то НОД(a, c · b) = НОД(a, b)НОД(a, b) = НОД(a - b, b)НОД(a, b) = НОД(b, r), где r — остаток от деления a на bИспользуя различные комбинации этих свойств, можно получить
различные алгоритмы вычисления НОД(a, b) в кольце $$\mathbb Z$$. Пользуясь
свойствами 3 и 5, можно свести задачу вычисления НОД в $$\mathbb Z$$ к
той же задаче для множества неотрицательных целых чисел и ограничиться представителем только положительного числа в качестве
результата. Например, используя свойства 1, 3, 6, можно получить
один из простейших алгоритмов вычисления НОД; используя свойства 1, 4, 5 с c = 2, получаем бинарный алгоритм вычисления НОД ; а используя свойства 2 и 7, получаем алгоритм Евклида нахождения наибольшего общего делителя натуральных чисел.
5.18. УПРАЖНЕНИЕ. Сформулировать перечисленные алгоритмы.
Свойство 7 использует понятие "остаток от деления одного числа на другое" . На этом свойстве основан алгоритм Евклида, и распространение действия этого алгоритма на другие кольца достигается введением следующего определения.
5.19. ОПРЕДЕЛЕНИЕ. Область целостности R называется евклидовым кольцом, если каждому ненулевому элементу $$a \in R$$ сопоставлено целое неотрицательное число g(a) со следующими свойствами:
УПРАЖНЕНИЕ. Доказать, что следующие кольца являются евклидовыми:
k[x] от одной переменной над любым
полем k ;k.В качестве упражнения читателю предлагается доказать следующую теорему.
5.21. ТЕОРЕМА. Любое евклидово кольцо является кольцом главных идеалов, а следовательно, факториальным кольцом.
Сформулируем
алгоритмы, предложенные ранее в качестве упражнения. Во всех
предложенных ниже алгоритмах считаем, что a и b — натуральные
числа, следовательно, ненулевые.
А1. АЛГОРИТМ (НОД1).
$$Дано: \quad $a,b\in \mathbb N$ \\ Надо: \quad $d\in \mathbb \mathbb N$, \\ Переменные:\quad $x,y\in \mathbb N$ \\ начало \\ $x:=a$ \\ $y:=b$ \\ цикл пока $x \ne y$\\ \quad если $x>y$, то \\ \quad\quad $x:=x-y$\\ \quad иначе\\ \quad\quad $y:=y-x$\\ \quad конец если\\ конец цикла\\ $d:=x$ \\ конец$$Данный алгоритм использует операции сравнения натуральных
чисел, вычитания натуральных чисел и присваивания переменной
значения натурального числа. Оценивая сложность предложенного
алгоритма, можно рассматривать эти операции как элементарные.
В теле цикла "пока" выполняется две операции сравнения, одна
операция вычитания и одна операция присваивания. Цикл выполняется не более max(a, b) раз. Таким образом, сложность алгоритма
равна O(max(a, b)).
Однако, более естественно рассматривать в качестве элементарных
5.22. УПРАЖНЕНИЕ. Показать, что если max(a, b) = n, то сложность вычисления НОД(a, b) по предложенному алгоритму равна O(n log2 n) битовых операций.
А2. АЛГОРИТМ (Евклида).
$$\begin{align*} \text{Дано: \quad $a, b \in\mathbb N$}\\ \text{Надо: \quad $d \in\mathbb N$,}\\ \text{Переменные: \quad $r, x, y \in\mathbb Z_+$}\\ \text{начало}\\ \text{$x := a$}\\ \text{$y := b$}\\ \text{цикл пока \quad $y \ne 0$}\\ \text{\quad\quad $r := x (mod \;y)$}\\ \text{\quad\quad $x := y$}\\ \text{\quad\quad $y := r$}\\ \text{конец цикла}\\ \text{$d := x$}\\ \text{конец} \end{align*}$$В алгоритме Евклида использовано стандартное обозначение x (mod y) для остатка от деления x на y. Легко показать, что после
двух делений делимое уменьшается, как минимум, в два раза. Значит, количество повторений цикла равно O(log2 n), где n=max(a, b).
Определяя битовую сложность алгоритма Евклида, мы должны учитывать, что сложность операции деления зависит от количества
цифр квадратично. Таким образом, мы получаем оценку $$O(\log_2^3n)$$
для битовой сложности алгоритма Евклида. Более тщательный анализ позволяет доказать оценку $$O(\log_2^2n)$$.
Можно показать, что, в определенном смысле, наихудший вариант для алгоритма Евклида представляют последовательные числа Фиббоначчи.
5.23. УПРАЖНЕНИЕ. Показать, что если a = Fn+1, b = Fn — со-
ответствующие числа Фиббоначчи, то остатки в алгоритме Евклида
принимают последовательно значения Fn-1, . . . , F2 = 1.
5.24. УПРАЖНЕНИЕ. Показать, что если a > b и $$r_{1}, . . . , r_{n} \ne 0$$ —
последовательные остатки, получаемые в алгоритме Евклида, то a >
Fn+1, где Fk — k -ое число Фиббоначчи.
Легко видеть, что алгоритм Евклида применим в любом евкли-
довом кольце, т. е. условия $$a, b \in \mathbb N,$$ $$d \in \mathbb N$$ и $$r, x, y \in \mathbb Z_+ $$ можно
заменить на $$a, b, d, r, x, y \in R$$, где R — любое евклидово кольцо.
5.25. УПРАЖНЕНИЕ. Что произойдет, если в алгоритме Евклида a
и b — отрицательные или нулевые целые числа?
Следующий алгоритм использует специфику машинной арифметики, основанной на системе счисления по основанию 2, в которой операции умножения и деления на 2 сводятся к сдвигу, следовательно, выполняются очень быстро.
А3. АЛГОРИТМ (бинарный НОД).
$$\begin{align*} \text{Дано: \quad$a, b \in \mathbbN$}\\ \text{Надо: \quad$d \in \mathbbN$,}\\ \text{Переменные: \quad$x, y \in \mathbbN$}\\ \text{начало}\\ \text{$x := a$}\\ \text{$y := b$}\\ \text{$d := 1$}\\ \text{цикл пока $x (mod \; 2) = y (mod \;2) = 0$}\\ \quad\text{$d := 2d, x := x/2, y := y/2$}\\ \text{конец цикла}\\ \text{цикл пока $x \ne y$}\\ \quad\text{выбор}\\ \quad\quad\text{при $x (mod 2) = 0$ делать $x := x/2$}\\ \quad\quad\quad\text{при $y (mod 2) = 0$ делать $y := y/2$}\\ \quad\quad\quad\text{при $x > y$ делать $x := x - y$}\\ \quad\quad\quad\text{при $x < y$ делать $y := y - x$}\\ \quad\quad\text{конец выбора}\\ \text{конец цикла}\\ \text{$d := d \cdot x$}\\ \text{конец}\\ \end{align*}$$5.26. ЗАМЕЧАНИЕ. В конструкции выбор выполняются только
действия для первого истинного условия в операторах при. Таким
образом, на первые два условия мы можем попасть, когда один из
аргументов четный, а другой — нечетный. На последние два условия
можно попасть, только когда оба аргумента нечетны. Учитывая, что
при вычитании нечетного числа из нечетного получается четное,
можно результат сразу разделить на 2, т. е. строки
при x > y делать x := x - y при x < y делать y := y - x
заменить строками
при x > y делать x := (x - y)/2 при x < y делать y := (y - x)/2
Очевидно, что при каждом повторении тела цикла последнего
алгоритма хотя бы один аргумент уменьшается в два раза. Значит,
количество повторений цикла равно 2 n), где n = max(a, b).
Определяя битовую сложность бинарного алгоритма, мы должны
учитывать, что сложность операций, выполняемых в теле цикла,
зависит от количества цифр линейно, т. е. битовая сложность бинарного алгоритма равна $$O(\log_2^2n)$$.
Приведем еще алгоритм вычисления НОД, основанный на свойстве факториальности кольца $$\mathbb Z$$.
А4. АЛГОРИТМ ( НОД через примарное разложение).
Наибольший общий делитель двух целых чисел обладает следую-
щим важным свойством: если d = НОД(a, b), то существуют целые числа u и v, такие, что d = u · a + v · b.
5.27. УПРАЖНЕНИЕ. Доказать это свойство, пользуясь тем, что $$\mathbb Z$$ — кольцо главных идеалов.
Для нахождения целых чисел u и v используется метод, называемый расширенным алгоритмом Евклида.
А 5. АЛГОРИТМ (Евклида расширенный).
$$\begin{align*} \text{Дано: $a, \; b \in \mathbb N$}\\ \text{Надо: $d \in \mathbb N, u, \; v \in \mathbb Z$}\\ \text{Переменные: $R,X,\; Y$ — векторы элементов типа $Z$ с индексом $0..2$}\\ \quad \quad \quad \quad \text{$q \in \mathbb Z_+$}\\ \text{Обозначения: \quad $r \;== \;R[0], x\; == \;X[0], y \;== \;Y \;[0]$}\\ \text{начало}\\ \text{$X := (a,\; 1,\; 0)$}\\ \text{$Y := (b,\; 0,\; 1)$}\\ \text{цикл пока $y \ne 0$}\\ \quad \text{$q := [x/y]$ \quad \quad \quad // целая часть дроби $\frac{x}{y}$}\\ \quad \text{$R := X - q \cdot Y$}\\ \quad \text{$X := Y$}\\ \quad \text{$Y := R$}\\ \text{конец цикла}\\ \text{$(d, \;u,\; v) := X$}\\ \text{конец}\\ \end{align*}$$Три компонента вектора X связаны соотношением:
X[0] = X[1] · a + X[2] · b.
Такое же соотношение справедливо для Y и R.
Чтобы распространить этот алгоритм на отрицательные и нулевые целые числа, достаточно заменить первые две строки следующими:
если a > 0, то X := (a, 1, 0) иначе X := (-a,-1, 0) если b > 0, то Y := (b, 0, 1) иначе Y := (-b, 0,-1)
5.28. УПРАЖНЕНИЕ. Доказать, что битовая сложность расширенного алгоритма Евклида равна $$O(\log^2_2n)$$, где n = max(|a|, |b|).
5.29. УПРАЖНЕНИЕ. Сформулировать расширенную версию алгоритма А 1 и оценить его сложность.
До недавнего времени считалось, что расширенной версии бинарного алгоритма не существует. С.А. Абрамов и С.И. Рыбин
построили ее, допустив в рассмотрение вектор (0, b/2k,-a/2k), где 2k — степень 2 в НОД, который можно прибавлять к другим векторам или вычитать из них.
5.30. УПРАЖНЕНИЕ. Написать расширенный бинарный алгоритм.
Алгоритм
Евклида и бинарный алгоритм вычисления НОД являются достаточно эффективными для большинства приложений. При проектировании высокопроизводительных систем используются различные
методы повышения быстродействия алгоритма вычисления НОД, в
частности, алгоритм Лемера .
Алгоритмы А 2 и А 5 дословно переносятся на любое евклидово кольцо,
в частности, на кольцо многочленов k[x] от одной переменной над
произвольным полем k.
Последовательность остатков полиномов, полученная при выполнении алгоритма Евклида, называется последовательностью полиномиальных остатков ( PRS ).
Рассмотрим пример, сконцентрировав наше внимание на росте коэффициентов членов последовательности полиномиальных остатков.
6.1. ПРИМЕР. Рассмотрим полиномы p1(x) = x3-7x+7 и p2(x) =
= 3x2 - 7 как элементы евклидова кольца $$\mathbb Q[x]$$. Применяя алгоритм Евклида, получаем такие последовательности:
Поскольку p4(x) = -1/4, получаем НОД[p1(x), p2(x)] = 1.
Рост коэффициентов последовательности полиномиальных остатков может быть минимизирован, если каждый член, как только он получен, нормируется. В этом случае мы получаем
$$\begin{align*} p_1(x)=x^3-7x+7,\\ p_2(x)=x^2-7/3,\quadq_1(x)=x,\\ p_3(x)=x-3/2,q_2(x)=x+3/2,\\ p_4(x)=1,q_3(x)=x-3/2,\\ p_5(x)=0. \end{align*}$$Действительно, мы видим, что коэффициенты растут медленнее,
но расплачиваемся за это вычислением НОД целых чисел на каждом
шаге, чтобы максимально редуцировать дроби.
Из этого примера видно, что использовать арифметику рациональных чисел для вычисления последовательности полиномиальных остатков нецелесообразно; с одной стороны, число требуемых
для максимального редуцирования коэффициентов вычислений НОД
целых чисел слишком велико, и с другой стороны, отказ от редукции ведет в стремительному росту выражения.
Коэффициенты многочленов в приведенных выше примерах являются целыми числами, т. е. мы можем рассматривать эти многочлены как элементы кольца $$\mathbb Z[x]$$. Поскольку это кольцо факториально (с однозначным разложением на неприводимые множители),
для любых двух элементов этого кольца, не равных одновременно
нулю, определен их наибольший общий делитель. С другой сторо-
ны, из вложения $$\mathbb Z[x] \subset \mathbb Q[x]$$ следует, что мы можем рассматривать
наибольший общий делитель этих же многочленов в кольце $$\mathbb Q[x]$$.
Как связаны между собой эти наибольшие общие делители? Одно
отличие мы уже знаем: НОД в кольце $$\mathbb Z[x]$$ определен с точностью
до знака, а в кольце $$\mathbb Q[x]$$ — с точностью до умножения на любое
ненулевое рациональное число. Покажем, что, по существу, этим
отличие и ограничивается.
6.2. ЛЕММА (Гаусса). Если коэффициенты многочлена $$f \in \mathbb Z[x]$$ взаимно просты в совокупности и f = g · h, где $$g, h \in \mathbb Q[x]$$ и НОД числителей коэффициентов каждого из многочленов g и h равен 1, то $$g, h \in \mathbb Z[x]$$.
ДОКАЗАТЕЛЬСТВО. Проведем доказательство методом "от противного". Пусть $$g=\sum\limits_{i=0}^na_ix^i\notin \Z[x]$$ и $$p$$ — простое число, которое делит
знаменатель какого-либо коэффициента ai. Выберем максимальную
степень числа p, которая делит знаменатель какого-либо коэффициента ai, обозначим ее k. Без потери общности можем обозначить i0 такой индекс, что знаменатели коэффициентов ai при i > i0 не
делятся на pk, а знаменатель коэффициента $$a_{i_0}$$ делится на pk. Рассмотрим теперь многочлен $$h(x)=\sum\limits_{j=0}^mb_jx^j.$$ Пусть l — минимальная
степень p, на которую делится хотя бы один коэффициент bj (l < 0, если p делит знаменатель какого-либо коэффициента). По условию, l <= 0. Пусть j0 — наибольшее значение индекса, на котором этот
минимум достигается. Вычислим коэффициент $$c_{i_0+j_0}$$ при $$x^{i_0+j_0}$$ в
произведении gh. Имеем
Знаменатель первого слагаемого делится на pk-l, знаменатель ни
одного из коэффициентов под знаком суммы на это число не делится. Таким образом, знаменатель коэффициента $$c_{i_0+j_0}$$ делится на $$p^{k-l}>1$$, что противоречит
условию леммы.
Пользуясь леммой Гаусса 6.2, мы можем разбить вычисление НОД(f(x), g(x)) в кольце $$\mathbb Z[x]$$ на следующие этапы:
f(x) и g(x) ;dq(x) = НОД(f(x), g(x)) в кольце $$\mathbb Q[x]$$, нормированный таким образом, что $$dq(x)\in \mathbb Z[x]$$ и коэффициенты многочлена dq(x) взаимно просты;НОД(f(x), g(x)) = dc · dq(x) в кольце $$\mathbb Z[x]$$.Введем следующие определения.
6.3. ОПРЕДЕЛЕНИЕ. Наибольший общий делитель коэффициен-
тов многочлена $$f(x) \in \mathbb Z[x]$$ называется содержанием этого многочлена и обозначается cont(f). Многочлен f(x)/ cont(f) называется примитивной частью многочлена f(x) и обозначается p. p.(f(x)).
Обратимся теперь к задаче нахождения наибольшего общего делителя двух полиномов p1(x), p2(x) в кольце $$\mathbb Z[x]$$, при условии, что
все арифметические операции над коэффициентами выполняются не
в поле $$\mathbb Q$$, а в кольце $$\mathbb Z$$, являющимся не полем, а только областью
с однозначным разложением на множители. Из приведенных выше
рассуждений ясно, что мы можем вывести следующие важные соотношения:
cont{НОД[p1(x), p2(x)]} = НОД{cont[p1(x)], cont[p2(x)]},
p. p.{НОД[p1(x), p2(x)]} = НОД{p. p.[p1(x)], p. p.[p2(x)]}.
Поэтому задача нахождения наибольшего общего делителя произвольных полиномов сводится к задаче нахождения наибольшего общего делителя примитивных полиномов.
Рассмотрим два примитивных ненулевых полинома p1(x) и p2(x)
в $$\mathbb Z[x]$$, у которых deg[p1(x)] = m и deg[p2(x)] = n, m > n. Поскольку
алгоритм деления полиномов с остатком требует точной делимости
p1(x) и p2(x) над целыми числами, не ослабляя требования делимости. Поэтому мы вводим процесс псевдоделения, который всегда
дает нам псевдочастное и псевдоостаток (prem), коэффициенты
которых являются целыми числами.
Псевдоделение означает предварительное умножение полинома p1(x) на {lc[p2(x)]}m-n+1, а затем применение алгоритма деления
многочленов, когда известно, что все частные существуют, т. е.
где q(x) и r(x) — псевдочастное и псевдоостаток соответственно.
6.4. ПРИМЕР. Пользуясь псевдоделением в $$\mathbb Z[x]$$, разделим p1(x) == x4 - 7x + 7 на p2(x) = 3x2 - 7. Для того, чтобы вычислить q(x)
и r(x), предварительно умножим p1(x) на 34-2+1 = 27, а затем,
применяя алгоритм деления многочленов, получаем q(x) = 9x2 + 21
и r(x) = -189x + 336. Читатель может убедиться, что алгоритм
деления многочленов не будет работать, если мы предварительно
домножим p1(x ) только на 3.
Поэтому, пытаясь вычислить наибольший общий делитель полиномов p1(x) и p2(x), мы должны убедиться, что выполнимы все деления полиномов, встречающиеся в этом процессе, т. е. мы должны,
используя псевдоделения, сформировать последовательность полиномиальных остатков. Таким образом, мы приходим к следующему
обобщенному алгоритму Евклида для полиномов.
А 6. АЛГОРИТМ (GEA-P). Обобщенный алгоритм Евклида для многочленов над целыми числами G eneralized E uclidean A lgorithm for P olynomials over the Integers.
$$\begin{align*} \text{Дано:\quad $p_1(x), p_2(x)$ - ненулевые полиномы в $ \mathbb Z[x]$;}\\ \text{\quad \quad \quad$\deg[p_1(x)]=n_1$, $\deg[p_2(x)] = n_2$,$n_1\ge n_2$.}\\ \text{Надо:\quad $НОД[p_1(x), p_2(x)]$, НОД многочленов $p_1(x)$ и $p_2(x)$.}\\ \text{начало}\\ \text{ \quad\quad\quad 1 [Вычисление НОД содержаний]}\\ \text{\quad\quad\quad\quad $c:=НОД\{\cont[p_1(x)],\cont[p_2(x)]\}$.(Здесь мы используем }\\ \text{\quad\quad\quad алгоритм Евклида для вычисления наибольшего общего де-}\\ \text{\quad\quad\quad лителя двух целых чисел.)}\\ \text{ \quad\quad 2 [Вычисление примитивных частей]}\\ \text{\quad\quad\quad $p'_1(x):=p_1(x)/\cont[p_1(x)]; p'_2(x):=p_2(x)/\cont[p_2(x)]$.}\\ \text{ \quad\quad3 [Построение PRS]}\\ \text{\quad\quad\quad Вычислить $p'_1(x),p'_2(x),p_3(x),\dots,p_h(x)$.}\\ \text{\quad\quad 4 [Выход]}\\ \text{ \quad\quad\quad Если $\deg[p_h(x)] = 0$, то вернуть $НОД[p_1(x), p_2(x)]:=c$,}\\ \text{ \quad\quad\quad иначе вернуть $НОД[p_1(x), p_2(x)]:=c\cdot \pp[p_h(x)]$.}\\ \end{align*}$$Ясно, что время работы этого алгоритма зависит от того, насколько эффективно мы можем вычислять последовательность полиномиальных остатков $$p'_1(x), p'_2(x), p_3(x), \dots, p_h(x)$$. Заметим, что если $$n_i=\deg[p_i(x)]$$, то в общем случае мы можем утверждать, что члены этой последовательности удовлетворяют соотношениям
$$\{lc[p_{i+1}(x)]\}^{n_i-n_{i+1}+1}p_i(x)=p_{i+1}(x)q_i(x)+\beta_ip_{i+2}(x),\\ \deg[p_{i+2}(x)] < \deg[p_{i+1}(x)], \end{gathered}\label{beta}$$где i = 1, 2, . . . , h - 1 для некоторого h. [Разумеется, $$p_i(x):=p'_i(x)$$, i = 1, 2,где $$p'_i(x)$$, $$i=1,2$$ определены на шаге 2 алгоритма GEA-P ].
Если дан метод выбора коэффициентов $$\beta _{i}$$, то выписанное соотношение дает алгоритм построения PRS; очевидно, что условие завершения этого семейства алгоритмов — равенство нулю псевдоостатка.
Ниже мы рассматриваем различные алгоритмы, полученные для разных значений $$\beta _{i}$$.
Здесь $$\beta_i=1$$ для всех $$i=1, 2,\dots, h-1$$, т.е. каждый псевдоостаток используется в том виде, в котором он получен. Это один из худших методов построения PRS, приводящий к экспоненциальному росту коэффициентов.
6.5. ПРИМЕР. Рассмотрим полиномы $$p_1(x)=x^3-7x+7$$, $$p_2(x)= 3x^2-7$$ в $$\mathbb Z[x].$$ Очевидно, что $$\cont[p_1(x)]=\cont[p_2(x)]=1$$ и $$p_i(x)=p'_i(x)$$, $$i=1,2$$. Мы имеем такую последовательность:
$$\begin{align*} {}p_1(x)=x^3-7x+7, \\ {}p_2(x)=3x^2-7, q_1(x)=3x, \\ {}p_3(x)=-42x+63,\quad q_2(x)=-126x-189,\\ {}p_4(x)=-441, q_3(x)=18522x-27783, \end{align*}$$полученную при выполнении следующих псевдоделений:
$$\begin{align*} (3)^2 p_1(x)=p_2(x)\cdot(3x)+(-42x+63),\\ (-42)^2p_2(x)=p_3(x)\cdot(-126x-189)+(-441),\\ (-441)^2 p_3(x)=p_4(x)\cdot(18522x-27783)+0. \end{align*}$$Из шага 4 алгоритма GEA-P следует, что НОД[p1(x), p2(x)]=1. Отметим также, что в последнем псевдоделении коэффициенты имеют
8 десятичных цифр, поскольку (-441)2p3(x)=-8168202x+12252303.
Последовательность полиномиальных остатков этого примера называется полной, потому что степень каждого ее члена на единицу
меньше степени предыдущего; два первых члена могут, конечно,
иметь одинаковые степени. В противном случае последовательность
называется неполной. Заметим, что не существует способа сказать
a priori, будет ли PRS полной или неполной.
Экспоненциальный рост коэффициентов членов PRS в приведенном примере обусловлен тем, что полиномы этой последовательности не являются примитивными, т. е. то, что мы не избавляемся от их содержания, дает вредный эффект. Эта ситуация исправляется ниже.
В этом случае
$$\beta_i=\cont\{\prem[p_i(x),p_{i+1}(x)]\},\quad i=1, 2,\dots , h-1,$$где prem обозначает псевдоостаток, т. е. теперь мы удаляем содержание (i + 2) -го члена PRS до того, как мы используем его.
[Напомним, что для данного p(x) удобно определять p. p.[p(x)] так,
чтобы
6.6. ПРИМЕР. Рассмотрим те же полиномы, что и в предыдущем
примере: p1(x) = x3 - 7x + 7, p2(x) = 3x2 - 7 в $$\mathbb Z[x]$$, где снова $$p_i(x)=p'_i(x) , \; i=1,2$$ Теперь мы получаем
что достигается выполнением следующих псевдоделений:
$$\begin{align*} (3)^2p_1(x)=p_2(x)\cdot(3x)+(-21)(2x-3),\\ (2)^2p_2(x)=p_3(x)\cdot(6x+9)+(-1),\\ (1)^2p_3(x)=p_4(x)\cdot(2x-3)+0. \end{align*}$$Этот алгоритм дает наилучшие возможные результаты в отношении роста коэффициентов, однако, они достигаются достаточно сложными вычислениями НОД коэффициентов на каждом этапе. В монографии , 2.3.3] утверждается, что лучшим из известных методов вычисления НОД многочленов, основанных на применении к многочленам с целыми коэффициентами алгоритма Евклида, является метод, в котором множители $$\beta _{i}$$ выбираются следующим образом.
Предположим, что даны два многочлена $$p_1(x), p_2(x) \in \mathbb Z[x]$$. Для
вычисления их НОД построим последовательность полиномиальных
остатков (x) и $$\delta i$$ для разности степеней
многочленов pi(x) и pi+1(x). Последовательность полиномиальных
остатков строим по формуле (6.1), в которой полагаем
где
$$\begin{aligned} \psi_1=-1 \\ \psi_i=(-c_i)^{\delta_{i-1}}i\psi_{i-1}^{1-\delta_{i-1}},\quad i>1.\quad \quad \quad \ecno(6.3) \end{aligned}$$Теорема о субрезультантах (см., например, ) утверждает, что
все pi являются многочленами с целыми коэффициентами.
6.7. ПРИМЕР. Анализ вычисления НОД следующих многочленов выполнен Брауном . Этот пример разобран также в монографии , § 2.3.3].
$$\begin{align*} p_1(x)=x^8+x^6-3x^4-3x^3+8x^2+2x-5,\\ p_2(x)=3x^6+5x^4-4x^2-9x+21. \end{align*}$$Рассматривая эти многочлены как элементы кольца $$\mathbb Q[x]$$ и применяя алгоритм Евклида, мы получаем следующую последовательность:
$$\begin{align*} p_3=\frac{-5}9x^4+\frac19x^2-\frac13,\\ p_4=\frac{-117}{25}x^2-9x+\frac{441}{25},\\ p_5=\frac{233150}{19773}x-\frac{102500}{6591},\\ p_6=\frac{1288744821}{543589225}. \end{align*}$$Все выписанные дроби являются несократимыми.
Выписанная последовательность достаточно трудоемка для вычислений вручную. Рекомендуется воспользоваться системой rem, вычисляющей остатки. По умолчанию система Maple не упорядочивает слагаемые в многочленах, для этой цели используется функция sort.
Последовательность команд может выглядеть следующим образом:
Применение нормализации делителя позволяет уменьшить коэффициенты, но не слишком сильно.
Для данного примера евклидова последовательность полиномиальных остатков имеет вид
$$\begin{align*} p_3=-15x^4+3x^2-9,\\ p_4=15795x^2+30375x-59535,\\ p_5=1254542875143750x-1654608338437500,\\ p_6=12593338795500743100931151992187500. \end{align*}$$Для вычисления этой последовательности с помощью системы Maple нужно в приведенной выше программе заменить функцию rem на prem.
Наконец, применяя формулы (6.2) и (6.3), мы получаем последовательность
$$\begin{align*} p_3=15x^4-3x^2+9,\\ p_4=65x^2+125x-245,\\ p_5=9326x-12300,\\ p_6=260708, \end{align*}$$которая возрастает значительно медленнее, чем предыдущие последовательности.
Пусть p — простое число. Любое целое число m можно рассматривать как представитель соответствующего класса вычетов по модулю p, т. е. числу m можно однозначно поставить в соответствие некоторый элемент из поля $$\EuScript{F}_p = \mathbb Z/p\mathbb Z$$. В частности, любому многочлену $$f(x) \in \mathbb Z[x]$$ можно однозначно поставить в соответствие многочлен $$f_p(x) \in F_p[x]$$.
Вернемся к примеру 6.7. Многочлены
$$\begin{align*} a(x)=x^8+x^6-3x^4-3x^3+8x^2+2x-5,\\ b(x)=3x^6+5x^4-4x^2-9x+21. \end{align*}$$можно рассматривать как элементы кольца $$\EuScript F_p[x]$$ для любого простого p. Можно вычислить их наибольший общий делитель в $$\EuScript F_p[x]$$. При
этом у нас не возникнет проблем с ростом коэффициентов, поскольку мы можем пользоваться системой представителей из множества {0, 1, . . . .p - 1}. Полагая p = 5, мы без особого труда убеждаемся,
что многочлены a(x) и b(x) взаимно просты в кольце $$\EuScript Fp[x]$$. Можно ли из этого сделать вывод, что многочлены a(x) и b(x) взаимно
просты в кольце $$\mathbb Z[x]$$? Оказывается, можно. Доказательство этого
факта основано на следующих утверждениях.
6.8. ПРЕДЛОЖЕНИЕ. Описанное выше отображение $$\mathbb Z[x] \rightarrow$$ $$\EuScript F[x]$$, такое, что $$f(x)7 \mapstofp (x)$$ является гомоморфизмом колец, т. е. сумма переходит в сумму, а произведение—в произведение. В частности, если g(x) | f(x) в $$\mathbb Z[x]$$, то gp(x) | fp(x) в $$\EuScript F[x]$$.
6.9. ПРЕДЛОЖЕНИЕ. Предположим, что $$a(x), \; b(x) \in \mathbb Z[x]$$ —примитивные многочлены и простое число p не делит старшие коэффициенты многочленов a(x) и b(x). Если НОД(ap(x), bp(x)) = 1
в $$\EuScript Fp[x]$$, то НОД(a(x), b(x)) = 1 в $$\mathbb Z[x]$$.
6.10. УПРАЖНЕНИЕ. Показать, что оба условия в предложении 6.9
являются существенными, т. е. если многочлены $$a(x), \; b(x) \in \mathbb Z[x]$$ не
являются примитивными или p делит их НОД(ap(x), bp(x)) = 1 в $$\EuScript Fp[x]$$ не следует, что НОД(a(x), b(x)) = 1
в $$\mathbb Z[x]$$.
6.11. ПРЕДЛОЖЕНИЕ. Предположим, что $$a(x), b(x) \in \mathbb Z[x]$$ — примитивные многочлены, такие, что НОД(a(x), b(x))=1 в $$\mathbb Z[x]$$. Тогда НОД(ap(x), bp(x))=1 в $$\EuScript Fp[x]$$ для почти всех простых чисел p.
ДОКАЗАТЕЛЬСТВО. Без потери общности мы можем считать, что
рассматриваются только простые числа, которые не делят ни a(x), ни b(x). Условие НОД(ap(x), bp(x)) = 1 означает, что результант Resp(ap, bp) этих многочленов, рассматриваемых как элементы кольца $$\EuScript F_p[x]$$, не обращается в нуль. Чтобы вычислить Resp(ap, bp), нам
достаточно вычислить результант Res(a, b) многочленов a(x), b(x) в
кольце $$\mathbb Z[x]$$ и взять образ этого результанта по модулю p. Результант Res(a, b) является ненулевым целым числом (так как исходные многочлены по условию взаимно просты) и делится только на конечное
число простых чисел.
6.12. ОПРЕДЕЛЕНИЕ. Пусть $$a(x), \; b(x) \in \mathbb Z[x]$$ —примитивные многочлены, такие, что НОД(a(x), b(x))=1 в $$\mathbb Z[x]$$. Простое число p назовем плохой редукцией, если либо p делит a(x), b(x), либо $$НОД(a_{p}(x), b_{p}(x)) \ne -1$$.
6.13. ЗАДАЧА. Для примитивных многочленов $$a(x), \; b(x) \in \mathbb Z[x]$$ найти ограничение сверху для числа плохих редукций (или ограничение сверху для их произведения).
Для решения этой задачи могут пригодиться результаты, приведенные в параграфе 7 .
Итак, мы можем сформулировать следующий алгоритм проверки взаимной простоты примитивных многочленов $$a(x), \; b(x) \in \mathbb Z[x]$$.
А 7. АЛГОРИТМ (Проверки взаимной простоты многочленов).
$$\begin{align*}\text{Дано: \quad $a(x),\; b(x) \in \mathbb Z[x]$ —примитивные многочлены}\\ \text{Надо: \quad являются ли $a(x)$ и $b(x)$ взаимно простыми}\\ \text{начало}\\ \text{Найти ограничение сверху для числа плохих редукций}\\ \text{цикл пока ограничение сверху не превышено}\\ \text{\quad \quad выбрать следующее простое $p$}\\ \text{\quad \quad если $НОД(ap(x), \; bp(x)) = 1$ то вернуть(взаимно просты)}\\ \text{\quad \quad конец если}\\ \text{конец цикла}\\ \text{вернуть(не взаимно просты)}\\ \text{конец}\\ \end{align*} $$В действительности, модулярный метод может быть применен
не только для проверки взаимной простоты многочленов, но и для
нахождения их НОД.
Следующее предложение обобщает предложение 6.11.
6.14. ПРЕДЛОЖЕНИЕ. Предположим, что $$a(x), \; b(x) \in \mathbb Z[x]$$ —примитивные многочлены и d(x) = НОД(a(x), b(x)) в $$\mathbb Z[x]$$. Предположим, что p — простое число, которое не делит ни a(x), ни b(x ). Пусть $$\tilde
d(x)=НОД(a_p(x),b_p(x))$$ в $$\EuScript F_p[x]$$. Тогда
deg $$\deg \tilde d(x)\ge \deg d(x)$$ и $$\deg \tilde d(x)= \deg d(x)$$ для почти всех p.
ДОКАЗАТЕЛЬСТВО. Из предложения 6.8 следует, что dp(x) является общим делителем многочленов ap(x) и bp(x)) в $$\EuScript Fp[x]$$, т. е. $$d_p(x)\mid\tilde d(x)$$. Следовательно, $$\deg \tilde d(x)\ge \deg d(x)$$. Применяя предложение 6.11 к многочленам a(x)/d(x ) и b(x)/d(x), получим, что $$\deg \tilde d(x)= \deg d(x)$$ для почти всех p.
Обобщим определение 6.12 следующим образом.
6.15. ОПРЕДЕЛЕНИЕ. Пусть $$a(x), \; b(x) \in \mathbb Z[x]$$ —примитивные многочлены. Простое число p назовем плохой редукцией, если либо p
делит a(x),
b(x), либо $$\deg НОД(a_p(x),b_p(x) > \deg \; НОД(a(x),b(x))$$.
Можно ли утверждать, что $$\tilde d(x)=d_p(x)$$? Для ответа на этот вопрос вспомним, что НОД определен с точностью до умножения на обратимые элементы кольца, т. е. $$d(x)=НОД(a(x),b(x))$$, следовательно, и $$d_p(x)$$ определены с точностью до умножения на $$\pm1$$, а $$\tilde d(x)$$ определен с точностью до умножения на ненулевые элементы поля $$\cF_p$$. Таким образом, среди возможных значений $$\tilde d(x)$$ будут $$d_p(x)$$, но, в общем случае, ими значения $$\tilde d(x)$$ не исчерпываются.
Наша ближайшая цель — разработать алгоритм вычисления
наибольшего общего делителя примитивных многочленов с
целочисленными коэффициентами, основываясь на следующих
соображениях. Выбираем несколько простых чисел $$p$$, которые должны
быть достаточно маленькими (чтобы вычисления в
Что касается необходимого количества редукций (количества простых чисел, по модулю которых выполняются вычисления), то можно поступить одним из следующих способов:
Отметим, что в этой задаче, применяя КТО, мы должны находить числа с данными вычетами не из множества неотрицательных чисел $$\smu{1}\{0,1,\dots,m-1\}$$, а из симметричной системы $$\smu{1}\{-(m-1)/2,\dots,-1,0,1,\dots,(m-1)/2\}$$ (при четном $$m$$, т. е. когда в качестве одного из модулей используется 2, система получается немного несимметричной: от $$-k+1$$ до $$k$$, где $$k=m/2$$ ).
Основная же проблема состоит в том, как согласовать вычисления для различных значений $$p$$. Здесь можно предложить два подхода.
Во-первых, можно свести задачу к случаю, когда искомый НОД
является нормированным многочленом. Для этого заметим, что старший
коэффициент искомого НОД делит
Недостаток этого метода в том, что при достаточно высоких степенях исходных многочленов коэффициенты промежуточных многочленов (от $$y$$ ) становятся очень большими, что требует большего количества чисел $$p$$, используемых для редукций, и более громоздких вычислений при применении КТО.
А 8. АЛГОРИТМ (Модулярный НОД).
$$\begin{align*} \text{Дано: \quad $a(x), b(x) \in Z[x]$}\\ \text{Надо: \quad $d(x) = НОД(a(x), b(x))$}\\ \text{начало}\\ \text{$c := НОД(lc(a(x)), lc(b(x)))$}\\ \text{выбрать нечетное простое $p$}\\ \text{$m := p$}\\ \text{$dm(x) := c * НОД(a_p(x), b_p(x))$ (в симметричной системе вычетов}\\ \text{\quad \quad \quad по модулю $m$);}\\ \text{цикл пока $p.p.(d_m(x))$ не делит $a(x) и b(x) в Z[x]$}\\ \text{\quad выбрать следующее простое $p$}\\ \text{\quad $d_p(x) := НОД(a_p(x), b_p(x))$}\\ \text{\quad если $deg d_p(x) < deg d_m(x)$ то}\\ \text{\quad \quad $m := p$}\\ \text{\quad \quad $d_m(x) := c * d_p(x)$ (в симметричной системе вычетов}\\ \text{\quad \quad \quad по модулю $m$);}\\ \text{\quad иначе если $deg d_p(x) = deg d_m(x)$ то}\\ \text{\quad \quad Применить КТО к $(m, p, d_m(x), c * d_p(x))$}\\ \text{\quad конец если}\\ \text{конец цикла}\\ \text{вернуть$(d_m(x)$)} \end{align*}$$Предписание "Применить КТО к $$(m,p,d_m(x),c*d_p(x))$$ " означает следующее. На входе: $$p$$ — простое число, $$m$$ — натуральное число, не делящееся на $$p$$, коэффициенты многочленов $$d_m(x)=\sum\limits_{i=0}^na_ix^i$$ и $$c*d_p(x)=\smash[t]{\sum\limits_{i=0}^n}b_ix^i$$ рассматриваются как представители смежных классов по модулю $$m$$ и $$p$$ соответственно. Вычисляются числа $$a'_i$$, такие что $$a'_i\equiv a_i\pmod m$$ и $$a'_i\equiv b_i\pmod p$$, $$-mp/2 < a'_i\le mp/2$$, $$i=0,1,\dots,n$$. На выходе $$m:=m*p$$ и $$d_m(x)=\sum\limits_{i=0}^na'_ix^i$$.
6.16. ЗАДАЧА. Доказать корректность представленного алгоритма.
6.17. ПРИМЕР. Пользуясь модулярным алгоритмом, вычислим НОД многочленов $$f(x)=28x^3+216x^2-193x-51$$ и $$g(x)=8x^3+ 78x^2+33x-442$$.
Наибольший общий делитель
В качестве следующего простого числа берем $$p=5$$. Вычисляя $$НОД(f(x),g(x))\pmod5$$, получим $$d_5(x)=x^2+3x+2$$. Поскольку $$\smu{1} \deg(d_5)>\deg(d_3)$$, заключаем, что $$\smu{1} p=5$$ является "плохой редукцией".
Переходим к $$p=7$$. Получаем $$\smu{1} d_7(x)=НОД(f(x),g(x))\pmod7= x+5$$. Домножая на 4, получим $$4x+20\equiv 4x+6\pmod7$$. Пользуясь китайской теоремой об остатках, решаем систему сравнений$$\begin{cases} a\equiv 1\pmod3,\\a\equiv6\pmod7.\end{cases}$$ Получаем $$a\equiv13\pmod{21}$$. Переходя к симметричной системе вычетов, получаем $$d_{21}(x)=4x-8$$. Убеждаемся, что $$d_{21}(x)$$ не делит исходные многочлены в $$\mathbb Q[x]$$.
Берем $$p=11$$. Получаем $$d_{11}(x)=НОД(f(x),g(x))\pmod{11} = x+3$$. Домножая на 4, получим $$4x+12\equiv 4x+1\pmod7$$. Пользуясь китайской теоремой об остатках, решаем систему сравнений$$\begin{cases} a\equiv 13\pmod{21},\\a\equiv1\pmod{11}.\end{cases}$$ Получаем $$a\equiv34\pmod{231}$$. Переход к симметричной системе вычетов ничего не меняет, и в итоге мы получаем $$d_{231}(x)=4x+34$$. Убеждаемся, что $$d_{231}(x)$$ делит исходные многочлены в $$\mathbb \Q[x]$$ и $$p.p.(d_{231}(x))=2x+17$$ является наибольшим общим делителем исходных многочленов.
Вычисляя евклидову последовательность полиномиальных остатков, мы видели, что коэффициенты промежуточных многочленов могут расти достаточно быстро. При этом коэффициенты наибольшего общего делителя, как правило, оказываются небольшими. В этом параграфе мы постараемся найти оценки для коэффициентов многочленов, делящих заданный многочлен с целыми коэффициентами. Первая гипотеза, приходящая на ум, состоит в том, что если $$\smu{1} f(x),g(x)\in \mathbb Z[x]$$ и $$\smu{1} g(x)\mid f(x)$$, то коэффициенты делителя не превосходят по абсолютной величине коэффициентов делимого. К сожалению,
7.1. ПРИМЕР. Рассмотрим многочлены$$\begin{align*} f(x)=x^3+x^2-x-1=(x+1)^2(x-1),\\ g(x)=x^4+x^3-x-1=(x+1)^2(x^2-x+1). \end{align*}$$ Легко видеть, что НОД $$(f(x),g(x))=x^2+2x+1=(x+1)^2$$.
Этот пример легко обобщается, например, путем умножения обоих исходных многочленов на $$(x+1)^2$$.
Оценку для коэффициентов делителей полинома будем выводить из известного неравенства Коши, которое дает оценку абсолютной величины корня полинома.
ТЕОРЕМА. Пусть $$d \geq 1$$,$$\begin{equation} P(x) = a_0 x^d + a_1 x^{d-1}+\dots + a_d,\qquad a_0 \ne 0\end{equation}$$ - полином с комплексными коэффициентами. Тогда любой корень $$z$$ полинома $$P(x)$$ удовлетворяет неравенству$$\begin{equation} | z| lt; 1 + \frac{\max \{ | a_1 |, \dots, | a_d | \}}{| a_0 |}. \end{equation}$$
ДОКАЗАТЕЛЬСТВО. Пусть $$P(z)=0$$. Если $$|z|\le1$$, то утверждение теоремы тривиально. Предположим, что $$|z|>1$$ и положим $$H= \max(|a_1|,\dots,|a_d|)$$. По предположению$$a_0z^d=-a_1z^{d-1}-\dots-a_d,$$ следовательно,$$|a_0|\;|z|^d\le H\left(|z|^{d-1}+\dots+1\right)<\frac{H\,|z|^d}{|z|-1},$$ то есть $$|a_0|(|z|-1)<H$$.
Разумеется, эта оценка не является единственно возможной. Ниже приведены еще две оценки, первая из которых также принадлежит Коши, а вторая — Кнуту:$$\begin{align*} |z|\leq \max \left(\genfrac||{}{} {da_1}{a_0}, \genfrac||{}{}{da_2}{a_0}^{1/2}, \genfrac||{}{}{da_3}{a_0}^{1/3}, \dots , \genfrac||{}{}{da_d}{a_0}^{1/d} \right), \\ |z|\leq2\max \left(\genfrac||{}{}{a_1}{a_0}, \genfrac||{}{}{a_2}{a_0}^{1/2}, \genfrac||{}{}{a_3}{a_0}^{1/3}, \dots , \genfrac||{}{}{a_d}{a_0}^{1/d} \right). \end{align*}$$
Каждая из этих оценок дает также границу и для минимального модуля корня полинома (в предположении, что свободный член полинома ненулевой) — заменяем в исходном полиноме $$x$$ на $$1/x$$, другими словами, ищем наибольший корень полинома $$a_dx^d+a_{d-1}x^{d-1}+\dots+a_1x+a_0$$, обратный к которому будет наименьшим корнем исходного полинома.
Воспользуемся неравенством Коши для получения оценки коэффициентов делителя полинома, которая известна как неравенство Ландау. Ландау
Пусть $$F = \sum^m_{k=0} c_k x^k$$. Положим$$\begin{equation} \|F\| = \left(\sum^m_{k=0} | c_k | ^2 \right)^{1/2}. \end{equation}$$ Рассматриваем формулу (7.3) как некоторое удобное обозначение. Можно доказать, что эта формула задает на пространстве полиномов метрику, но мы не пользуемся этим фактом, необходимые нам свойства этой метрики будут доказаны.
ТЕОРЕМА. Предположим, что полином $$P(x)$$ задан формулой (7.1). Пусть $$z_1, \dots, z_d$$ — корни полинома $$P(x)$$. Положим$$M(P)=|a_0|\prod^d_{j=1}\max\{1,|z_j|\} .$$ Тогда $$M(P) \leq \|P\|$$.
Для доказательства теоремы нам понадобится
ЛЕММА. Если $$Q$$ — полином и $$z$$ — комплексное число, то$$\begin{equation} \| (x + z) Q(x)\| = \|(\bar zx + 1) Q(x)\|. \end{equation}$$
ДОКАЗАТЕЛЬСТВО. Пусть $$Q(x) = \sum^m_{k=0} c_k x^k$$. Тогда квадрат выражения в левой части равенства (7.4) равен$$\sum^{m+1}_{k=0} (c_{k-1} + zc_k ) (\bar c_{k-1} + \bar z\bar c_k ) = (1 + | z| ^2) \|Q\|^2 +\sum^{m+1}_{k=0} (zc_k \bar c_{k-1} + \bar z\bar c_k c_{k-1})$$ (полагаем $$c_{-1} = c_{m+1} = 0$$ ). Этому же выражению равен и квадрат правой части.
ДОКАЗАТЕЛЬСТВО ТЕОРЕМЫ. Пусть $$z_1, \dots, z_k$$ — корни полинома $$P(x)$$, лежащие вне единичного круга. Тогда $$M(P)=|a_0|\cdot|z_1\cdot\dots\cdot z_k|$$. Положим$$\begin{equation*} R(x) = a_0 \prod^k_{j=1} (\bar z_j x - 1) \prod^d_{j=k+1} (x - z_j) = b_0 x^d +\dots+b_d. \end{equation*}$$ k-кратное применение леммы дает $$\smu{1} \|P\| = \|R\|$$. Однако $$\smu{1} \|R\|^2\geq\|b_0\|^2 = [M(P)]^2$$.
7.5. ТЕОРЕМА. Пусть $$Q = b_0 x^q + b_1 x^{q-1} + \dots + b_q$$, $$b_0 \ne0$$ — делитель полинома $$P(x)$$, задаваемого формулой (7.1). Тогда$$| b_0 | + | b_1 | + \dots + | b_q | \leq \genfrac||{}{}{b_0}{a_0}\cdot 2^q \|P\|.$$
ДОКАЗАТЕЛЬСТВО. Легко проверяется, что$$| b_0 | + | b_1 | + \dots + | b_q | \leq 2^q M(Q),$$ но $$M(Q) \leq | b_0 /a_0 | M(P)$$, и из неравенства Ландау следует, что $$M(P)\le \|P\|$$.
7.6. УПРАЖНЕНИЕ. Пусть $$f(x) \in \Z[x]$$ и $$h(x)$$ — делитель полинома $$f(x)$$. Предположим, что $$\deg (h) \leq m$$. Тогда$$\|h\| \leq \binom {2m}m ^{1/2}\|f\| .$$ (Символ $$\binom{n}{k}$$ используется здесь и неоднократно в дальнейшем для обозначения биномиальных коэффициентов, т. е. числа сочетаний из $$n$$ по $$k$$.)
Другие полезные границы можно найти, например, в работе .
В данном параграфе мы рассмотрим определение наибольшего общего делителя (НОД) двух элементов и алгоритмы его вычисления.
Пусть R — коммутативное кольцо с единицей, $$a,b\in
R$$. Мы говорим, что a делит b и пишем a|b, если существует элемент $$c\in R$$,
такой, что $$b=a\cdot c$$ ; если такого элемента не существует, то мы говорим, что a не делит b, и пишем $$a\nmid b$$. Заметим, что определение
делимости зависит от рассматриваемого кольца. Так, например, $$2 \mid 3$$
в поле рациональных чисел $$\mathbb Q$$, но $$2 \nmid 3$$ в кольце целых чисел $$\mathbb Z$$.
5.1. ОПРЕДЕЛЕНИЕ. Ненулевой элемент $$a \in R$$ такой, что ab = 0
для некоторого $$b \ne 0$$ называется делителем нуля кольца R, а элемент $$\varepsilon \in R$$, такой, что $$\varepsilon | 1$$ называется обратимым, или делителем
единицы, или единицей кольца R.
5.2. ОПРЕДЕЛЕНИЕ. Коммутативное кольцо с единицей и без де- лителей нуля называется областью целостности или просто областью.
5.3. ОПРЕДЕЛЕНИЕ. Пусть R — коммутативное кольцо с единицей. Элемент $$a \in R$$ называется неприводимым, если из представления a = bc в виде произведения двух элементов кольца R, следует,
что хотя бы один из элементов b и c обратим в R.
5.4. ОПРЕДЕЛЕНИЕ. Пусть R — коммутативное кольцо с едини-
цей. Идеал $$I\subset R$$ называется простым, если из $$bc \in I$$ следует, что
хотя бы один из элементов b и c лежит в I.
5.5. ОПРЕДЕЛЕНИЕ. Мы говорим, что идеал I порожден элементами b1, . . . , bn, и пишем I = (b1, . . . , bn), если $$b_{1}, . . . , b_{n} \in I$$ и любой
элемент $$b \in I$$ может быть записан в виде $$b=\sum\limits_{i=1}^nc_ib_i$$ где $$c_{i} \in R$$.
5.6. ОПРЕДЕЛЕНИЕ. Идеал I называется главным, если I = (b)
для некоторого элемента $$b \in I$$. Кольцо R называется кольцом главных идеалов, если любой идеал кольца R является главным.
5.7. УПРАЖНЕНИЕ. Показать, что Z и k[x] — кольца главных идеалов, а $$\mathbb Z[x]$$ и k[x, y] — нет.
5.8. УПРАЖНЕНИЕ. Показать, что главный идеал (b) является простым тогда и только тогда, когда b — неприводимый элемент.
5.9. ОПРЕДЕЛЕНИЕ. Элементы a и b кольца R называются ассоциированными, если $$a = \varepsilon \cdot b$$, где $$\varepsilon$$ — единица (обратимый элемент)
кольца R.
5.10. ОПРЕДЕЛЕНИЕ. Кольцо R называется факториальным или
кольцом с однозначным разложением на множители, если любой
элемент $$a \in R$$ можно представить в виде $$a = \varepsilon \cdot p_{1} \cdot\cdot\cdot pn$$, где $$\varepsilon$$ —
единица, а pi — неприводимые, причем если $$a = \varepsilon _{1} \cdot q_{1} \cdot\cdot\cdot q_{m}$$ — другое такое разложение, то m = n и для любого индекса i существует
индекс j, такой, что pi ассоциировано с qj.
5.11. ЛЕММА. Пусть R — область главных идеалов. Если элемент $$a \in R$$ допускает разложение на неприводимые множители,
то это разложение однозначно в смысле предыдущего определения.
ДОКАЗАТЕЛЬСТВО оставим читателю в качестве упражнения.
5.12. УПРАЖНЕНИЕ. Показать, что $$\mathbb Z[x]$$ и k[x, y] — факториальные
кольца.
Сформулируем (без доказательства) теорему, которая позволяет получать новые факториальные кольца.
5.13. ТЕОРЕМА. Если R — факториальное кольцо, то кольцо
многочленов R[x] также факториально.
Приведем пример нефакториального кольца.
5.14. ПРИМЕР. Кольцо $$\mathbb Z [\sqrt{-5}]$$ — нефакториально. В частности, $$9=3\cdot3=(2+\sqrt{-5})(2-\sqrt{-5})$$ — два различных разложения числа 9 на неприводимые множители в этом кольце.
5.15. ОПРЕДЕЛЕНИЕ. Пусть R — коммутативное кольцо с единицей, $$a, b \in R$$. Элемент $$d \in R$$ называется наибольшим общим делителем элементов a и b, если d | a, d | b и для любого другого элемента d', такого, что d' | a и d' | b выполняется соотношение d' | d.
5.16. УПРАЖНЕНИЕ. Показать, что в кольце $$\mathbb Z$$ для любых целых
чисел a и b, не равных одновременно нулю, существует наибольшее
целое число, которое делит a и b, и это число является наибольших
общим делителем чисел a и b в смысле определения 5.15. Показать,
что определение 5.15 в кольце $$\mathbb Z$$ определяет НОД( a, b ) неоднозначно.
5.17. УПРАЖНЕНИЕ. Показать, что в кольце k[x] многочленов от
одной переменной x над полем k для любых многочленов a и b,
не равных одновременно нулю, существует многочлен наибольшей
степени, который делит a и b, и этот многочлен является наибольшим общим делителем элементов a и b в смысле определения 5.15.
Показать, что определение 5.15 в кольце k[x] определяет НОД( a, b )
неоднозначно.
НОД(a, a) = {a,-a}НОД(a, 0) = {a,-a}НОД(a, b) = НОД(b, a)НОД(c · a, c · b) = c · НОД(a, b)НОД(a, c) = {1,-1} (в частности, если c = -1 ), то НОД(a, c · b) = НОД(a, b)НОД(a, b) = НОД(a - b, b)НОД(a, b) = НОД(b, r), где r — остаток от деления a на bИспользуя различные комбинации этих свойств, можно получить
различные алгоритмы вычисления НОД(a, b) в кольце $$\mathbb Z$$. Пользуясь
свойствами 3 и 5, можно свести задачу вычисления НОД в $$\mathbb Z$$ к
той же задаче для множества неотрицательных целых чисел и ограничиться представителем только положительного числа в качестве
результата. Например, используя свойства 1, 3, 6, можно получить
один из простейших алгоритмов вычисления НОД; используя свойства 1, 4, 5 с c = 2, получаем бинарный алгоритм вычисления НОД ; а используя свойства 2 и 7, получаем алгоритм Евклида нахождения наибольшего общего делителя натуральных чисел.
5.18. УПРАЖНЕНИЕ. Сформулировать перечисленные алгоритмы.
Свойство 7 использует понятие "остаток от деления одного числа на другое" . На этом свойстве основан алгоритм Евклида, и распространение действия этого алгоритма на другие кольца достигается введением следующего определения.
5.19. ОПРЕДЕЛЕНИЕ. Область целостности R называется евклидовым кольцом, если каждому ненулевому элементу $$a \in R$$ сопоставлено целое неотрицательное число g(a) со следующими свойствами:
УПРАЖНЕНИЕ. Доказать, что следующие кольца являются евклидовыми:
k[x] от одной переменной над любым
полем k ;k.В качестве упражнения читателю предлагается доказать следующую теорему.
5.21. ТЕОРЕМА. Любое евклидово кольцо является кольцом главных идеалов, а следовательно, факториальным кольцом.
Сформулируем
алгоритмы, предложенные ранее в качестве упражнения. Во всех
предложенных ниже алгоритмах считаем, что a и b — натуральные
числа, следовательно, ненулевые.
А1. АЛГОРИТМ (НОД1).
$$Дано: \quad $a,b\in \mathbb N$ \\ Надо: \quad $d\in \mathbb \mathbb N$, \\ Переменные:\quad $x,y\in \mathbb N$ \\ начало \\ $x:=a$ \\ $y:=b$ \\ цикл пока $x \ne y$\\ \quad если $x>y$, то \\ \quad\quad $x:=x-y$\\ \quad иначе\\ \quad\quad $y:=y-x$\\ \quad конец если\\ конец цикла\\ $d:=x$ \\ конец$$Данный алгоритм использует операции сравнения натуральных
чисел, вычитания натуральных чисел и присваивания переменной
значения натурального числа. Оценивая сложность предложенного
алгоритма, можно рассматривать эти операции как элементарные.
В теле цикла "пока" выполняется две операции сравнения, одна
операция вычитания и одна операция присваивания. Цикл выполняется не более max(a, b) раз. Таким образом, сложность алгоритма
равна O(max(a, b)).
Однако, более естественно рассматривать в качестве элементарных
5.22. УПРАЖНЕНИЕ. Показать, что если max(a, b) = n, то сложность вычисления НОД(a, b) по предложенному алгоритму равна O(n log2 n) битовых операций.
А2. АЛГОРИТМ (Евклида).
$$\begin{align*} \text{Дано: \quad $a, b \in\mathbb N$}\\ \text{Надо: \quad $d \in\mathbb N$,}\\ \text{Переменные: \quad $r, x, y \in\mathbb Z_+$}\\ \text{начало}\\ \text{$x := a$}\\ \text{$y := b$}\\ \text{цикл пока \quad $y \ne 0$}\\ \text{\quad\quad $r := x (mod \;y)$}\\ \text{\quad\quad $x := y$}\\ \text{\quad\quad $y := r$}\\ \text{конец цикла}\\ \text{$d := x$}\\ \text{конец} \end{align*}$$В алгоритме Евклида использовано стандартное обозначение x (mod y) для остатка от деления x на y. Легко показать, что после
двух делений делимое уменьшается, как минимум, в два раза. Значит, количество повторений цикла равно O(log2 n), где n=max(a, b).
Определяя битовую сложность алгоритма Евклида, мы должны учитывать, что сложность операции деления зависит от количества
цифр квадратично. Таким образом, мы получаем оценку $$O(\log_2^3n)$$
для битовой сложности алгоритма Евклида. Более тщательный анализ позволяет доказать оценку $$O(\log_2^2n)$$.
Можно показать, что, в определенном смысле, наихудший вариант для алгоритма Евклида представляют последовательные числа Фиббоначчи.
5.23. УПРАЖНЕНИЕ. Показать, что если a = Fn+1, b = Fn — со-
ответствующие числа Фиббоначчи, то остатки в алгоритме Евклида
принимают последовательно значения Fn-1, . . . , F2 = 1.
5.24. УПРАЖНЕНИЕ. Показать, что если a > b и $$r_{1}, . . . , r_{n} \ne 0$$ —
последовательные остатки, получаемые в алгоритме Евклида, то a >
Fn+1, где Fk — k -ое число Фиббоначчи.
Легко видеть, что алгоритм Евклида применим в любом евкли-
довом кольце, т. е. условия $$a, b \in \mathbb N,$$ $$d \in \mathbb N$$ и $$r, x, y \in \mathbb Z_+ $$ можно
заменить на $$a, b, d, r, x, y \in R$$, где R — любое евклидово кольцо.
5.25. УПРАЖНЕНИЕ. Что произойдет, если в алгоритме Евклида a
и b — отрицательные или нулевые целые числа?
Следующий алгоритм использует специфику машинной арифметики, основанной на системе счисления по основанию 2, в которой операции умножения и деления на 2 сводятся к сдвигу, следовательно, выполняются очень быстро.
А3. АЛГОРИТМ (бинарный НОД).
$$\begin{align*} \text{Дано: \quad$a, b \in \mathbbN$}\\ \text{Надо: \quad$d \in \mathbbN$,}\\ \text{Переменные: \quad$x, y \in \mathbbN$}\\ \text{начало}\\ \text{$x := a$}\\ \text{$y := b$}\\ \text{$d := 1$}\\ \text{цикл пока $x (mod \; 2) = y (mod \;2) = 0$}\\ \quad\text{$d := 2d, x := x/2, y := y/2$}\\ \text{конец цикла}\\ \text{цикл пока $x \ne y$}\\ \quad\text{выбор}\\ \quad\quad\text{при $x (mod 2) = 0$ делать $x := x/2$}\\ \quad\quad\quad\text{при $y (mod 2) = 0$ делать $y := y/2$}\\ \quad\quad\quad\text{при $x > y$ делать $x := x - y$}\\ \quad\quad\quad\text{при $x < y$ делать $y := y - x$}\\ \quad\quad\text{конец выбора}\\ \text{конец цикла}\\ \text{$d := d \cdot x$}\\ \text{конец}\\ \end{align*}$$5.26. ЗАМЕЧАНИЕ. В конструкции выбор выполняются только
действия для первого истинного условия в операторах при. Таким
образом, на первые два условия мы можем попасть, когда один из
аргументов четный, а другой — нечетный. На последние два условия
можно попасть, только когда оба аргумента нечетны. Учитывая, что
при вычитании нечетного числа из нечетного получается четное,
можно результат сразу разделить на 2, т. е. строки
при x > y делать x := x - y при x < y делать y := y - x
заменить строками
при x > y делать x := (x - y)/2 при x < y делать y := (y - x)/2
Очевидно, что при каждом повторении тела цикла последнего
алгоритма хотя бы один аргумент уменьшается в два раза. Значит,
количество повторений цикла равно 2 n), где n = max(a, b).
Определяя битовую сложность бинарного алгоритма, мы должны
учитывать, что сложность операций, выполняемых в теле цикла,
зависит от количества цифр линейно, т. е. битовая сложность бинарного алгоритма равна $$O(\log_2^2n)$$.
Приведем еще алгоритм вычисления НОД, основанный на свойстве факториальности кольца $$\mathbb Z$$.
А4. АЛГОРИТМ ( НОД через примарное разложение).
Наибольший общий делитель двух целых чисел обладает следую-
щим важным свойством: если d = НОД(a, b), то существуют целые числа u и v, такие, что d = u · a + v · b.
5.27. УПРАЖНЕНИЕ. Доказать это свойство, пользуясь тем, что $$\mathbb Z$$ — кольцо главных идеалов.
Для нахождения целых чисел u и v используется метод, называемый расширенным алгоритмом Евклида.
А 5. АЛГОРИТМ (Евклида расширенный).
$$\begin{align*} \text{Дано: $a, \; b \in \mathbb N$}\\ \text{Надо: $d \in \mathbb N, u, \; v \in \mathbb Z$}\\ \text{Переменные: $R,X,\; Y$ — векторы элементов типа $Z$ с индексом $0..2$}\\ \quad \quad \quad \quad \text{$q \in \mathbb Z_+$}\\ \text{Обозначения: \quad $r \;== \;R[0], x\; == \;X[0], y \;== \;Y \;[0]$}\\ \text{начало}\\ \text{$X := (a,\; 1,\; 0)$}\\ \text{$Y := (b,\; 0,\; 1)$}\\ \text{цикл пока $y \ne 0$}\\ \quad \text{$q := [x/y]$ \quad \quad \quad // целая часть дроби $\frac{x}{y}$}\\ \quad \text{$R := X - q \cdot Y$}\\ \quad \text{$X := Y$}\\ \quad \text{$Y := R$}\\ \text{конец цикла}\\ \text{$(d, \;u,\; v) := X$}\\ \text{конец}\\ \end{align*}$$Три компонента вектора X связаны соотношением:
X[0] = X[1] · a + X[2] · b.
Такое же соотношение справедливо для Y и R.
Чтобы распространить этот алгоритм на отрицательные и нулевые целые числа, достаточно заменить первые две строки следующими:
если a > 0, то X := (a, 1, 0) иначе X := (-a,-1, 0) если b > 0, то Y := (b, 0, 1) иначе Y := (-b, 0,-1)
5.28. УПРАЖНЕНИЕ. Доказать, что битовая сложность расширенного алгоритма Евклида равна $$O(\log^2_2n)$$, где n = max(|a|, |b|).
5.29. УПРАЖНЕНИЕ. Сформулировать расширенную версию алгоритма А 1 и оценить его сложность.
До недавнего времени считалось, что расширенной версии бинарного алгоритма не существует. С.А. Абрамов и С.И. Рыбин
построили ее, допустив в рассмотрение вектор (0, b/2k,-a/2k), где 2k — степень 2 в НОД, который можно прибавлять к другим векторам или вычитать из них.
5.30. УПРАЖНЕНИЕ. Написать расширенный бинарный алгоритм.
Алгоритм
Евклида и бинарный алгоритм вычисления НОД являются достаточно эффективными для большинства приложений. При проектировании высокопроизводительных систем используются различные
методы повышения быстродействия алгоритма вычисления НОД, в
частности, алгоритм Лемера .
Алгоритмы А 2 и А 5 дословно переносятся на любое евклидово кольцо,
в частности, на кольцо многочленов k[x] от одной переменной над
произвольным полем k.
Последовательность остатков полиномов, полученная при выполнении алгоритма Евклида, называется последовательностью полиномиальных остатков ( PRS ).
Рассмотрим пример, сконцентрировав наше внимание на росте коэффициентов членов последовательности полиномиальных остатков.
6.1. ПРИМЕР. Рассмотрим полиномы p1(x) = x3-7x+7 и p2(x) =
= 3x2 - 7 как элементы евклидова кольца $$\mathbb Q[x]$$. Применяя алгоритм Евклида, получаем такие последовательности:
Поскольку p4(x) = -1/4, получаем НОД[p1(x), p2(x)] = 1.
Рост коэффициентов последовательности полиномиальных остатков может быть минимизирован, если каждый член, как только он получен, нормируется. В этом случае мы получаем
$$\begin{align*} p_1(x)=x^3-7x+7,\\ p_2(x)=x^2-7/3,\quadq_1(x)=x,\\ p_3(x)=x-3/2,q_2(x)=x+3/2,\\ p_4(x)=1,q_3(x)=x-3/2,\\ p_5(x)=0. \end{align*}$$Действительно, мы видим, что коэффициенты растут медленнее,
но расплачиваемся за это вычислением НОД целых чисел на каждом
шаге, чтобы максимально редуцировать дроби.
Из этого примера видно, что использовать арифметику рациональных чисел для вычисления последовательности полиномиальных остатков нецелесообразно; с одной стороны, число требуемых
для максимального редуцирования коэффициентов вычислений НОД
целых чисел слишком велико, и с другой стороны, отказ от редукции ведет в стремительному росту выражения.
Коэффициенты многочленов в приведенных выше примерах являются целыми числами, т. е. мы можем рассматривать эти многочлены как элементы кольца $$\mathbb Z[x]$$. Поскольку это кольцо факториально (с однозначным разложением на неприводимые множители),
для любых двух элементов этого кольца, не равных одновременно
нулю, определен их наибольший общий делитель. С другой сторо-
ны, из вложения $$\mathbb Z[x] \subset \mathbb Q[x]$$ следует, что мы можем рассматривать
наибольший общий делитель этих же многочленов в кольце $$\mathbb Q[x]$$.
Как связаны между собой эти наибольшие общие делители? Одно
отличие мы уже знаем: НОД в кольце $$\mathbb Z[x]$$ определен с точностью
до знака, а в кольце $$\mathbb Q[x]$$ — с точностью до умножения на любое
ненулевое рациональное число. Покажем, что, по существу, этим
отличие и ограничивается.
6.2. ЛЕММА (Гаусса). Если коэффициенты многочлена $$f \in \mathbb Z[x]$$ взаимно просты в совокупности и f = g · h, где $$g, h \in \mathbb Q[x]$$ и НОД числителей коэффициентов каждого из многочленов g и h равен 1, то $$g, h \in \mathbb Z[x]$$.
ДОКАЗАТЕЛЬСТВО. Проведем доказательство методом "от противного". Пусть $$g=\sum\limits_{i=0}^na_ix^i\notin \Z[x]$$ и $$p$$ — простое число, которое делит
знаменатель какого-либо коэффициента ai. Выберем максимальную
степень числа p, которая делит знаменатель какого-либо коэффициента ai, обозначим ее k. Без потери общности можем обозначить i0 такой индекс, что знаменатели коэффициентов ai при i > i0 не
делятся на pk, а знаменатель коэффициента $$a_{i_0}$$ делится на pk. Рассмотрим теперь многочлен $$h(x)=\sum\limits_{j=0}^mb_jx^j.$$ Пусть l — минимальная
степень p, на которую делится хотя бы один коэффициент bj (l < 0, если p делит знаменатель какого-либо коэффициента). По условию, l <= 0. Пусть j0 — наибольшее значение индекса, на котором этот
минимум достигается. Вычислим коэффициент $$c_{i_0+j_0}$$ при $$x^{i_0+j_0}$$ в
произведении gh. Имеем
Знаменатель первого слагаемого делится на pk-l, знаменатель ни
одного из коэффициентов под знаком суммы на это число не делится. Таким образом, знаменатель коэффициента $$c_{i_0+j_0}$$ делится на $$p^{k-l}>1$$, что противоречит
условию леммы.
Пользуясь леммой Гаусса 6.2, мы можем разбить вычисление НОД(f(x), g(x)) в кольце $$\mathbb Z[x]$$ на следующие этапы:
f(x) и g(x) ;dq(x) = НОД(f(x), g(x)) в кольце $$\mathbb Q[x]$$, нормированный таким образом, что $$dq(x)\in \mathbb Z[x]$$ и коэффициенты многочлена dq(x) взаимно просты;НОД(f(x), g(x)) = dc · dq(x) в кольце $$\mathbb Z[x]$$.Введем следующие определения.
6.3. ОПРЕДЕЛЕНИЕ. Наибольший общий делитель коэффициен-
тов многочлена $$f(x) \in \mathbb Z[x]$$ называется содержанием этого многочлена и обозначается cont(f). Многочлен f(x)/ cont(f) называется примитивной частью многочлена f(x) и обозначается p. p.(f(x)).
Обратимся теперь к задаче нахождения наибольшего общего делителя двух полиномов p1(x), p2(x) в кольце $$\mathbb Z[x]$$, при условии, что
все арифметические операции над коэффициентами выполняются не
в поле $$\mathbb Q$$, а в кольце $$\mathbb Z$$, являющимся не полем, а только областью
с однозначным разложением на множители. Из приведенных выше
рассуждений ясно, что мы можем вывести следующие важные соотношения:
cont{НОД[p1(x), p2(x)]} = НОД{cont[p1(x)], cont[p2(x)]},
p. p.{НОД[p1(x), p2(x)]} = НОД{p. p.[p1(x)], p. p.[p2(x)]}.
Поэтому задача нахождения наибольшего общего делителя произвольных полиномов сводится к задаче нахождения наибольшего общего делителя примитивных полиномов.
Рассмотрим два примитивных ненулевых полинома p1(x) и p2(x)
в $$\mathbb Z[x]$$, у которых deg[p1(x)] = m и deg[p2(x)] = n, m > n. Поскольку
алгоритм деления полиномов с остатком требует точной делимости
p1(x) и p2(x) над целыми числами, не ослабляя требования делимости. Поэтому мы вводим процесс псевдоделения, который всегда
дает нам псевдочастное и псевдоостаток (prem), коэффициенты
которых являются целыми числами.
Псевдоделение означает предварительное умножение полинома p1(x) на {lc[p2(x)]}m-n+1, а затем применение алгоритма деления
многочленов, когда известно, что все частные существуют, т. е.
где q(x) и r(x) — псевдочастное и псевдоостаток соответственно.
6.4. ПРИМЕР. Пользуясь псевдоделением в $$\mathbb Z[x]$$, разделим p1(x) == x4 - 7x + 7 на p2(x) = 3x2 - 7. Для того, чтобы вычислить q(x)
и r(x), предварительно умножим p1(x) на 34-2+1 = 27, а затем,
применяя алгоритм деления многочленов, получаем q(x) = 9x2 + 21
и r(x) = -189x + 336. Читатель может убедиться, что алгоритм
деления многочленов не будет работать, если мы предварительно
домножим p1(x ) только на 3.
Поэтому, пытаясь вычислить наибольший общий делитель полиномов p1(x) и p2(x), мы должны убедиться, что выполнимы все деления полиномов, встречающиеся в этом процессе, т. е. мы должны,
используя псевдоделения, сформировать последовательность полиномиальных остатков. Таким образом, мы приходим к следующему
обобщенному алгоритму Евклида для полиномов.
А 6. АЛГОРИТМ (GEA-P). Обобщенный алгоритм Евклида для многочленов над целыми числами G eneralized E uclidean A lgorithm for P olynomials over the Integers.
$$\begin{align*} \text{Дано:\quad $p_1(x), p_2(x)$ - ненулевые полиномы в $ \mathbb Z[x]$;}\\ \text{\quad \quad \quad$\deg[p_1(x)]=n_1$, $\deg[p_2(x)] = n_2$,$n_1\ge n_2$.}\\ \text{Надо:\quad $НОД[p_1(x), p_2(x)]$, НОД многочленов $p_1(x)$ и $p_2(x)$.}\\ \text{начало}\\ \text{ \quad\quad\quad 1 [Вычисление НОД содержаний]}\\ \text{\quad\quad\quad\quad $c:=НОД\{\cont[p_1(x)],\cont[p_2(x)]\}$.(Здесь мы используем }\\ \text{\quad\quad\quad алгоритм Евклида для вычисления наибольшего общего де-}\\ \text{\quad\quad\quad лителя двух целых чисел.)}\\ \text{ \quad\quad 2 [Вычисление примитивных частей]}\\ \text{\quad\quad\quad $p'_1(x):=p_1(x)/\cont[p_1(x)]; p'_2(x):=p_2(x)/\cont[p_2(x)]$.}\\ \text{ \quad\quad3 [Построение PRS]}\\ \text{\quad\quad\quad Вычислить $p'_1(x),p'_2(x),p_3(x),\dots,p_h(x)$.}\\ \text{\quad\quad 4 [Выход]}\\ \text{ \quad\quad\quad Если $\deg[p_h(x)] = 0$, то вернуть $НОД[p_1(x), p_2(x)]:=c$,}\\ \text{ \quad\quad\quad иначе вернуть $НОД[p_1(x), p_2(x)]:=c\cdot \pp[p_h(x)]$.}\\ \end{align*}$$Ясно, что время работы этого алгоритма зависит от того, насколько эффективно мы можем вычислять последовательность полиномиальных остатков $$p'_1(x), p'_2(x), p_3(x), \dots, p_h(x)$$. Заметим, что если $$n_i=\deg[p_i(x)]$$, то в общем случае мы можем утверждать, что члены этой последовательности удовлетворяют соотношениям
$$\{lc[p_{i+1}(x)]\}^{n_i-n_{i+1}+1}p_i(x)=p_{i+1}(x)q_i(x)+\beta_ip_{i+2}(x),\\ \deg[p_{i+2}(x)] < \deg[p_{i+1}(x)], \end{gathered}\label{beta}$$где i = 1, 2, . . . , h - 1 для некоторого h. [Разумеется, $$p_i(x):=p'_i(x)$$, i = 1, 2,где $$p'_i(x)$$, $$i=1,2$$ определены на шаге 2 алгоритма GEA-P ].
Если дан метод выбора коэффициентов $$\beta _{i}$$, то выписанное соотношение дает алгоритм построения PRS; очевидно, что условие завершения этого семейства алгоритмов — равенство нулю псевдоостатка.
Ниже мы рассматриваем различные алгоритмы, полученные для разных значений $$\beta _{i}$$.
Здесь $$\beta_i=1$$ для всех $$i=1, 2,\dots, h-1$$, т.е. каждый псевдоостаток используется в том виде, в котором он получен. Это один из худших методов построения PRS, приводящий к экспоненциальному росту коэффициентов.
6.5. ПРИМЕР. Рассмотрим полиномы $$p_1(x)=x^3-7x+7$$, $$p_2(x)= 3x^2-7$$ в $$\mathbb Z[x].$$ Очевидно, что $$\cont[p_1(x)]=\cont[p_2(x)]=1$$ и $$p_i(x)=p'_i(x)$$, $$i=1,2$$. Мы имеем такую последовательность:
$$\begin{align*} {}p_1(x)=x^3-7x+7, \\ {}p_2(x)=3x^2-7, q_1(x)=3x, \\ {}p_3(x)=-42x+63,\quad q_2(x)=-126x-189,\\ {}p_4(x)=-441, q_3(x)=18522x-27783, \end{align*}$$полученную при выполнении следующих псевдоделений:
$$\begin{align*} (3)^2 p_1(x)=p_2(x)\cdot(3x)+(-42x+63),\\ (-42)^2p_2(x)=p_3(x)\cdot(-126x-189)+(-441),\\ (-441)^2 p_3(x)=p_4(x)\cdot(18522x-27783)+0. \end{align*}$$Из шага 4 алгоритма GEA-P следует, что НОД[p1(x), p2(x)]=1. Отметим также, что в последнем псевдоделении коэффициенты имеют
8 десятичных цифр, поскольку (-441)2p3(x)=-8168202x+12252303.
Последовательность полиномиальных остатков этого примера называется полной, потому что степень каждого ее члена на единицу
меньше степени предыдущего; два первых члена могут, конечно,
иметь одинаковые степени. В противном случае последовательность
называется неполной. Заметим, что не существует способа сказать
a priori, будет ли PRS полной или неполной.
Экспоненциальный рост коэффициентов членов PRS в приведенном примере обусловлен тем, что полиномы этой последовательности не являются примитивными, т. е. то, что мы не избавляемся от их содержания, дает вредный эффект. Эта ситуация исправляется ниже.
В этом случае
$$\beta_i=\cont\{\prem[p_i(x),p_{i+1}(x)]\},\quad i=1, 2,\dots , h-1,$$где prem обозначает псевдоостаток, т. е. теперь мы удаляем содержание (i + 2) -го члена PRS до того, как мы используем его.
[Напомним, что для данного p(x) удобно определять p. p.[p(x)] так,
чтобы
6.6. ПРИМЕР. Рассмотрим те же полиномы, что и в предыдущем
примере: p1(x) = x3 - 7x + 7, p2(x) = 3x2 - 7 в $$\mathbb Z[x]$$, где снова $$p_i(x)=p'_i(x) , \; i=1,2$$ Теперь мы получаем
что достигается выполнением следующих псевдоделений:
$$\begin{align*} (3)^2p_1(x)=p_2(x)\cdot(3x)+(-21)(2x-3),\\ (2)^2p_2(x)=p_3(x)\cdot(6x+9)+(-1),\\ (1)^2p_3(x)=p_4(x)\cdot(2x-3)+0. \end{align*}$$Этот алгоритм дает наилучшие возможные результаты в отношении роста коэффициентов, однако, они достигаются достаточно сложными вычислениями НОД коэффициентов на каждом этапе. В монографии , 2.3.3] утверждается, что лучшим из известных методов вычисления НОД многочленов, основанных на применении к многочленам с целыми коэффициентами алгоритма Евклида, является метод, в котором множители $$\beta _{i}$$ выбираются следующим образом.
Предположим, что даны два многочлена $$p_1(x), p_2(x) \in \mathbb Z[x]$$. Для
вычисления их НОД построим последовательность полиномиальных
остатков (x) и $$\delta i$$ для разности степеней
многочленов pi(x) и pi+1(x). Последовательность полиномиальных
остатков строим по формуле (6.1), в которой полагаем
где
$$\begin{aligned} \psi_1=-1 \\ \psi_i=(-c_i)^{\delta_{i-1}}i\psi_{i-1}^{1-\delta_{i-1}},\quad i>1.\quad \quad \quad \ecno(6.3) \end{aligned}$$Теорема о субрезультантах (см., например, ) утверждает, что
все pi являются многочленами с целыми коэффициентами.
6.7. ПРИМЕР. Анализ вычисления НОД следующих многочленов выполнен Брауном . Этот пример разобран также в монографии , § 2.3.3].
$$\begin{align*} p_1(x)=x^8+x^6-3x^4-3x^3+8x^2+2x-5,\\ p_2(x)=3x^6+5x^4-4x^2-9x+21. \end{align*}$$Рассматривая эти многочлены как элементы кольца $$\mathbb Q[x]$$ и применяя алгоритм Евклида, мы получаем следующую последовательность:
$$\begin{align*} p_3=\frac{-5}9x^4+\frac19x^2-\frac13,\\ p_4=\frac{-117}{25}x^2-9x+\frac{441}{25},\\ p_5=\frac{233150}{19773}x-\frac{102500}{6591},\\ p_6=\frac{1288744821}{543589225}. \end{align*}$$Все выписанные дроби являются несократимыми.
Выписанная последовательность достаточно трудоемка для вычислений вручную. Рекомендуется воспользоваться системой rem, вычисляющей остатки. По умолчанию система Maple не упорядочивает слагаемые в многочленах, для этой цели используется функция sort.
Последовательность команд может выглядеть следующим образом:
Применение нормализации делителя позволяет уменьшить коэффициенты, но не слишком сильно.
Для данного примера евклидова последовательность полиномиальных остатков имеет вид
$$\begin{align*} p_3=-15x^4+3x^2-9,\\ p_4=15795x^2+30375x-59535,\\ p_5=1254542875143750x-1654608338437500,\\ p_6=12593338795500743100931151992187500. \end{align*}$$Для вычисления этой последовательности с помощью системы Maple нужно в приведенной выше программе заменить функцию rem на prem.
Наконец, применяя формулы (6.2) и (6.3), мы получаем последовательность
$$\begin{align*} p_3=15x^4-3x^2+9,\\ p_4=65x^2+125x-245,\\ p_5=9326x-12300,\\ p_6=260708, \end{align*}$$которая возрастает значительно медленнее, чем предыдущие последовательности.
Пусть p — простое число. Любое целое число m можно рассматривать как представитель соответствующего класса вычетов по модулю p, т. е. числу m можно однозначно поставить в соответствие некоторый элемент из поля $$\EuScript{F}_p = \mathbb Z/p\mathbb Z$$. В частности, любому многочлену $$f(x) \in \mathbb Z[x]$$ можно однозначно поставить в соответствие многочлен $$f_p(x) \in F_p[x]$$.
Вернемся к примеру 6.7. Многочлены
$$\begin{align*} a(x)=x^8+x^6-3x^4-3x^3+8x^2+2x-5,\\ b(x)=3x^6+5x^4-4x^2-9x+21. \end{align*}$$можно рассматривать как элементы кольца $$\EuScript F_p[x]$$ для любого простого p. Можно вычислить их наибольший общий делитель в $$\EuScript F_p[x]$$. При
этом у нас не возникнет проблем с ростом коэффициентов, поскольку мы можем пользоваться системой представителей из множества {0, 1, . . . .p - 1}. Полагая p = 5, мы без особого труда убеждаемся,
что многочлены a(x) и b(x) взаимно просты в кольце $$\EuScript Fp[x]$$. Можно ли из этого сделать вывод, что многочлены a(x) и b(x) взаимно
просты в кольце $$\mathbb Z[x]$$? Оказывается, можно. Доказательство этого
факта основано на следующих утверждениях.
6.8. ПРЕДЛОЖЕНИЕ. Описанное выше отображение $$\mathbb Z[x] \rightarrow$$ $$\EuScript F[x]$$, такое, что $$f(x)7 \mapstofp (x)$$ является гомоморфизмом колец, т. е. сумма переходит в сумму, а произведение—в произведение. В частности, если g(x) | f(x) в $$\mathbb Z[x]$$, то gp(x) | fp(x) в $$\EuScript F[x]$$.
6.9. ПРЕДЛОЖЕНИЕ. Предположим, что $$a(x), \; b(x) \in \mathbb Z[x]$$ —примитивные многочлены и простое число p не делит старшие коэффициенты многочленов a(x) и b(x). Если НОД(ap(x), bp(x)) = 1
в $$\EuScript Fp[x]$$, то НОД(a(x), b(x)) = 1 в $$\mathbb Z[x]$$.
6.10. УПРАЖНЕНИЕ. Показать, что оба условия в предложении 6.9
являются существенными, т. е. если многочлены $$a(x), \; b(x) \in \mathbb Z[x]$$ не
являются примитивными или p делит их НОД(ap(x), bp(x)) = 1 в $$\EuScript Fp[x]$$ не следует, что НОД(a(x), b(x)) = 1
в $$\mathbb Z[x]$$.
6.11. ПРЕДЛОЖЕНИЕ. Предположим, что $$a(x), b(x) \in \mathbb Z[x]$$ — примитивные многочлены, такие, что НОД(a(x), b(x))=1 в $$\mathbb Z[x]$$. Тогда НОД(ap(x), bp(x))=1 в $$\EuScript Fp[x]$$ для почти всех простых чисел p.
ДОКАЗАТЕЛЬСТВО. Без потери общности мы можем считать, что
рассматриваются только простые числа, которые не делят ни a(x), ни b(x). Условие НОД(ap(x), bp(x)) = 1 означает, что результант Resp(ap, bp) этих многочленов, рассматриваемых как элементы кольца $$\EuScript F_p[x]$$, не обращается в нуль. Чтобы вычислить Resp(ap, bp), нам
достаточно вычислить результант Res(a, b) многочленов a(x), b(x) в
кольце $$\mathbb Z[x]$$ и взять образ этого результанта по модулю p. Результант Res(a, b) является ненулевым целым числом (так как исходные многочлены по условию взаимно просты) и делится только на конечное
число простых чисел.
6.12. ОПРЕДЕЛЕНИЕ. Пусть $$a(x), \; b(x) \in \mathbb Z[x]$$ —примитивные многочлены, такие, что НОД(a(x), b(x))=1 в $$\mathbb Z[x]$$. Простое число p назовем плохой редукцией, если либо p делит a(x), b(x), либо $$НОД(a_{p}(x), b_{p}(x)) \ne -1$$.
6.13. ЗАДАЧА. Для примитивных многочленов $$a(x), \; b(x) \in \mathbb Z[x]$$ найти ограничение сверху для числа плохих редукций (или ограничение сверху для их произведения).
Для решения этой задачи могут пригодиться результаты, приведенные в параграфе 7 .
Итак, мы можем сформулировать следующий алгоритм проверки взаимной простоты примитивных многочленов $$a(x), \; b(x) \in \mathbb Z[x]$$.
А 7. АЛГОРИТМ (Проверки взаимной простоты многочленов).
$$\begin{align*}\text{Дано: \quad $a(x),\; b(x) \in \mathbb Z[x]$ —примитивные многочлены}\\ \text{Надо: \quad являются ли $a(x)$ и $b(x)$ взаимно простыми}\\ \text{начало}\\ \text{Найти ограничение сверху для числа плохих редукций}\\ \text{цикл пока ограничение сверху не превышено}\\ \text{\quad \quad выбрать следующее простое $p$}\\ \text{\quad \quad если $НОД(ap(x), \; bp(x)) = 1$ то вернуть(взаимно просты)}\\ \text{\quad \quad конец если}\\ \text{конец цикла}\\ \text{вернуть(не взаимно просты)}\\ \text{конец}\\ \end{align*} $$В действительности, модулярный метод может быть применен
не только для проверки взаимной простоты многочленов, но и для
нахождения их НОД.
Следующее предложение обобщает предложение 6.11.
6.14. ПРЕДЛОЖЕНИЕ. Предположим, что $$a(x), \; b(x) \in \mathbb Z[x]$$ —примитивные многочлены и d(x) = НОД(a(x), b(x)) в $$\mathbb Z[x]$$. Предположим, что p — простое число, которое не делит ни a(x), ни b(x ). Пусть $$\tilde
d(x)=НОД(a_p(x),b_p(x))$$ в $$\EuScript F_p[x]$$. Тогда
deg $$\deg \tilde d(x)\ge \deg d(x)$$ и $$\deg \tilde d(x)= \deg d(x)$$ для почти всех p.
ДОКАЗАТЕЛЬСТВО. Из предложения 6.8 следует, что dp(x) является общим делителем многочленов ap(x) и bp(x)) в $$\EuScript Fp[x]$$, т. е. $$d_p(x)\mid\tilde d(x)$$. Следовательно, $$\deg \tilde d(x)\ge \deg d(x)$$. Применяя предложение 6.11 к многочленам a(x)/d(x ) и b(x)/d(x), получим, что $$\deg \tilde d(x)= \deg d(x)$$ для почти всех p.
Обобщим определение 6.12 следующим образом.
6.15. ОПРЕДЕЛЕНИЕ. Пусть $$a(x), \; b(x) \in \mathbb Z[x]$$ —примитивные многочлены. Простое число p назовем плохой редукцией, если либо p
делит a(x),
b(x), либо $$\deg НОД(a_p(x),b_p(x) > \deg \; НОД(a(x),b(x))$$.
Можно ли утверждать, что $$\tilde d(x)=d_p(x)$$? Для ответа на этот вопрос вспомним, что НОД определен с точностью до умножения на обратимые элементы кольца, т. е. $$d(x)=НОД(a(x),b(x))$$, следовательно, и $$d_p(x)$$ определены с точностью до умножения на $$\pm1$$, а $$\tilde d(x)$$ определен с точностью до умножения на ненулевые элементы поля $$\cF_p$$. Таким образом, среди возможных значений $$\tilde d(x)$$ будут $$d_p(x)$$, но, в общем случае, ими значения $$\tilde d(x)$$ не исчерпываются.
Наша ближайшая цель — разработать алгоритм вычисления
наибольшего общего делителя примитивных многочленов с
целочисленными коэффициентами, основываясь на следующих
соображениях. Выбираем несколько простых чисел $$p$$, которые должны
быть достаточно маленькими (чтобы вычисления в
Что касается необходимого количества редукций (количества простых чисел, по модулю которых выполняются вычисления), то можно поступить одним из следующих способов:
Отметим, что в этой задаче, применяя КТО, мы должны находить числа с данными вычетами не из множества неотрицательных чисел $$\smu{1}\{0,1,\dots,m-1\}$$, а из симметричной системы $$\smu{1}\{-(m-1)/2,\dots,-1,0,1,\dots,(m-1)/2\}$$ (при четном $$m$$, т. е. когда в качестве одного из модулей используется 2, система получается немного несимметричной: от $$-k+1$$ до $$k$$, где $$k=m/2$$ ).
Основная же проблема состоит в том, как согласовать вычисления для различных значений $$p$$. Здесь можно предложить два подхода.
Во-первых, можно свести задачу к случаю, когда искомый НОД
является нормированным многочленом. Для этого заметим, что старший
коэффициент искомого НОД делит
Недостаток этого метода в том, что при достаточно высоких степенях исходных многочленов коэффициенты промежуточных многочленов (от $$y$$ ) становятся очень большими, что требует большего количества чисел $$p$$, используемых для редукций, и более громоздких вычислений при применении КТО.
А 8. АЛГОРИТМ (Модулярный НОД).
$$\begin{align*} \text{Дано: \quad $a(x), b(x) \in Z[x]$}\\ \text{Надо: \quad $d(x) = НОД(a(x), b(x))$}\\ \text{начало}\\ \text{$c := НОД(lc(a(x)), lc(b(x)))$}\\ \text{выбрать нечетное простое $p$}\\ \text{$m := p$}\\ \text{$dm(x) := c * НОД(a_p(x), b_p(x))$ (в симметричной системе вычетов}\\ \text{\quad \quad \quad по модулю $m$);}\\ \text{цикл пока $p.p.(d_m(x))$ не делит $a(x) и b(x) в Z[x]$}\\ \text{\quad выбрать следующее простое $p$}\\ \text{\quad $d_p(x) := НОД(a_p(x), b_p(x))$}\\ \text{\quad если $deg d_p(x) < deg d_m(x)$ то}\\ \text{\quad \quad $m := p$}\\ \text{\quad \quad $d_m(x) := c * d_p(x)$ (в симметричной системе вычетов}\\ \text{\quad \quad \quad по модулю $m$);}\\ \text{\quad иначе если $deg d_p(x) = deg d_m(x)$ то}\\ \text{\quad \quad Применить КТО к $(m, p, d_m(x), c * d_p(x))$}\\ \text{\quad конец если}\\ \text{конец цикла}\\ \text{вернуть$(d_m(x)$)} \end{align*}$$Предписание "Применить КТО к $$(m,p,d_m(x),c*d_p(x))$$ " означает следующее. На входе: $$p$$ — простое число, $$m$$ — натуральное число, не делящееся на $$p$$, коэффициенты многочленов $$d_m(x)=\sum\limits_{i=0}^na_ix^i$$ и $$c*d_p(x)=\smash[t]{\sum\limits_{i=0}^n}b_ix^i$$ рассматриваются как представители смежных классов по модулю $$m$$ и $$p$$ соответственно. Вычисляются числа $$a'_i$$, такие что $$a'_i\equiv a_i\pmod m$$ и $$a'_i\equiv b_i\pmod p$$, $$-mp/2 < a'_i\le mp/2$$, $$i=0,1,\dots,n$$. На выходе $$m:=m*p$$ и $$d_m(x)=\sum\limits_{i=0}^na'_ix^i$$.
6.16. ЗАДАЧА. Доказать корректность представленного алгоритма.
6.17. ПРИМЕР. Пользуясь модулярным алгоритмом, вычислим НОД многочленов $$f(x)=28x^3+216x^2-193x-51$$ и $$g(x)=8x^3+ 78x^2+33x-442$$.
Наибольший общий делитель
В качестве следующего простого числа берем $$p=5$$. Вычисляя $$НОД(f(x),g(x))\pmod5$$, получим $$d_5(x)=x^2+3x+2$$. Поскольку $$\smu{1} \deg(d_5)>\deg(d_3)$$, заключаем, что $$\smu{1} p=5$$ является "плохой редукцией".
Переходим к $$p=7$$. Получаем $$\smu{1} d_7(x)=НОД(f(x),g(x))\pmod7= x+5$$. Домножая на 4, получим $$4x+20\equiv 4x+6\pmod7$$. Пользуясь китайской теоремой об остатках, решаем систему сравнений$$\begin{cases} a\equiv 1\pmod3,\\a\equiv6\pmod7.\end{cases}$$ Получаем $$a\equiv13\pmod{21}$$. Переходя к симметричной системе вычетов, получаем $$d_{21}(x)=4x-8$$. Убеждаемся, что $$d_{21}(x)$$ не делит исходные многочлены в $$\mathbb Q[x]$$.
Берем $$p=11$$. Получаем $$d_{11}(x)=НОД(f(x),g(x))\pmod{11} = x+3$$. Домножая на 4, получим $$4x+12\equiv 4x+1\pmod7$$. Пользуясь китайской теоремой об остатках, решаем систему сравнений$$\begin{cases} a\equiv 13\pmod{21},\\a\equiv1\pmod{11}.\end{cases}$$ Получаем $$a\equiv34\pmod{231}$$. Переход к симметричной системе вычетов ничего не меняет, и в итоге мы получаем $$d_{231}(x)=4x+34$$. Убеждаемся, что $$d_{231}(x)$$ делит исходные многочлены в $$\mathbb \Q[x]$$ и $$p.p.(d_{231}(x))=2x+17$$ является наибольшим общим делителем исходных многочленов.
Вычисляя евклидову последовательность полиномиальных остатков, мы видели, что коэффициенты промежуточных многочленов могут расти достаточно быстро. При этом коэффициенты наибольшего общего делителя, как правило, оказываются небольшими. В этом параграфе мы постараемся найти оценки для коэффициентов многочленов, делящих заданный многочлен с целыми коэффициентами. Первая гипотеза, приходящая на ум, состоит в том, что если $$\smu{1} f(x),g(x)\in \mathbb Z[x]$$ и $$\smu{1} g(x)\mid f(x)$$, то коэффициенты делителя не превосходят по абсолютной величине коэффициентов делимого. К сожалению,
7.1. ПРИМЕР. Рассмотрим многочлены$$\begin{align*} f(x)=x^3+x^2-x-1=(x+1)^2(x-1),\\ g(x)=x^4+x^3-x-1=(x+1)^2(x^2-x+1). \end{align*}$$ Легко видеть, что НОД $$(f(x),g(x))=x^2+2x+1=(x+1)^2$$.
Этот пример легко обобщается, например, путем умножения обоих исходных многочленов на $$(x+1)^2$$.
Оценку для коэффициентов делителей полинома будем выводить из известного неравенства Коши, которое дает оценку абсолютной величины корня полинома.
ТЕОРЕМА. Пусть $$d \geq 1$$,$$\begin{equation} P(x) = a_0 x^d + a_1 x^{d-1}+\dots + a_d,\qquad a_0 \ne 0\end{equation}$$ - полином с комплексными коэффициентами. Тогда любой корень $$z$$ полинома $$P(x)$$ удовлетворяет неравенству$$\begin{equation} | z| lt; 1 + \frac{\max \{ | a_1 |, \dots, | a_d | \}}{| a_0 |}. \end{equation}$$
ДОКАЗАТЕЛЬСТВО. Пусть $$P(z)=0$$. Если $$|z|\le1$$, то утверждение теоремы тривиально. Предположим, что $$|z|>1$$ и положим $$H= \max(|a_1|,\dots,|a_d|)$$. По предположению$$a_0z^d=-a_1z^{d-1}-\dots-a_d,$$ следовательно,$$|a_0|\;|z|^d\le H\left(|z|^{d-1}+\dots+1\right)<\frac{H\,|z|^d}{|z|-1},$$ то есть $$|a_0|(|z|-1)<H$$.
Разумеется, эта оценка не является единственно возможной. Ниже приведены еще две оценки, первая из которых также принадлежит Коши, а вторая — Кнуту:$$\begin{align*} |z|\leq \max \left(\genfrac||{}{} {da_1}{a_0}, \genfrac||{}{}{da_2}{a_0}^{1/2}, \genfrac||{}{}{da_3}{a_0}^{1/3}, \dots , \genfrac||{}{}{da_d}{a_0}^{1/d} \right), \\ |z|\leq2\max \left(\genfrac||{}{}{a_1}{a_0}, \genfrac||{}{}{a_2}{a_0}^{1/2}, \genfrac||{}{}{a_3}{a_0}^{1/3}, \dots , \genfrac||{}{}{a_d}{a_0}^{1/d} \right). \end{align*}$$
Каждая из этих оценок дает также границу и для минимального модуля корня полинома (в предположении, что свободный член полинома ненулевой) — заменяем в исходном полиноме $$x$$ на $$1/x$$, другими словами, ищем наибольший корень полинома $$a_dx^d+a_{d-1}x^{d-1}+\dots+a_1x+a_0$$, обратный к которому будет наименьшим корнем исходного полинома.
Воспользуемся неравенством Коши для получения оценки коэффициентов делителя полинома, которая известна как неравенство Ландау. Ландау
Пусть $$F = \sum^m_{k=0} c_k x^k$$. Положим$$\begin{equation} \|F\| = \left(\sum^m_{k=0} | c_k | ^2 \right)^{1/2}. \end{equation}$$ Рассматриваем формулу (7.3) как некоторое удобное обозначение. Можно доказать, что эта формула задает на пространстве полиномов метрику, но мы не пользуемся этим фактом, необходимые нам свойства этой метрики будут доказаны.
ТЕОРЕМА. Предположим, что полином $$P(x)$$ задан формулой (7.1). Пусть $$z_1, \dots, z_d$$ — корни полинома $$P(x)$$. Положим$$M(P)=|a_0|\prod^d_{j=1}\max\{1,|z_j|\} .$$ Тогда $$M(P) \leq \|P\|$$.
Для доказательства теоремы нам понадобится
ЛЕММА. Если $$Q$$ — полином и $$z$$ — комплексное число, то$$\begin{equation} \| (x + z) Q(x)\| = \|(\bar zx + 1) Q(x)\|. \end{equation}$$
ДОКАЗАТЕЛЬСТВО. Пусть $$Q(x) = \sum^m_{k=0} c_k x^k$$. Тогда квадрат выражения в левой части равенства (7.4) равен$$\sum^{m+1}_{k=0} (c_{k-1} + zc_k ) (\bar c_{k-1} + \bar z\bar c_k ) = (1 + | z| ^2) \|Q\|^2 +\sum^{m+1}_{k=0} (zc_k \bar c_{k-1} + \bar z\bar c_k c_{k-1})$$ (полагаем $$c_{-1} = c_{m+1} = 0$$ ). Этому же выражению равен и квадрат правой части.
ДОКАЗАТЕЛЬСТВО ТЕОРЕМЫ. Пусть $$z_1, \dots, z_k$$ — корни полинома $$P(x)$$, лежащие вне единичного круга. Тогда $$M(P)=|a_0|\cdot|z_1\cdot\dots\cdot z_k|$$. Положим$$\begin{equation*} R(x) = a_0 \prod^k_{j=1} (\bar z_j x - 1) \prod^d_{j=k+1} (x - z_j) = b_0 x^d +\dots+b_d. \end{equation*}$$ k-кратное применение леммы дает $$\smu{1} \|P\| = \|R\|$$. Однако $$\smu{1} \|R\|^2\geq\|b_0\|^2 = [M(P)]^2$$.
7.5. ТЕОРЕМА. Пусть $$Q = b_0 x^q + b_1 x^{q-1} + \dots + b_q$$, $$b_0 \ne0$$ — делитель полинома $$P(x)$$, задаваемого формулой (7.1). Тогда$$| b_0 | + | b_1 | + \dots + | b_q | \leq \genfrac||{}{}{b_0}{a_0}\cdot 2^q \|P\|.$$
ДОКАЗАТЕЛЬСТВО. Легко проверяется, что$$| b_0 | + | b_1 | + \dots + | b_q | \leq 2^q M(Q),$$ но $$M(Q) \leq | b_0 /a_0 | M(P)$$, и из неравенства Ландау следует, что $$M(P)\le \|P\|$$.
7.6. УПРАЖНЕНИЕ. Пусть $$f(x) \in \Z[x]$$ и $$h(x)$$ — делитель полинома $$f(x)$$. Предположим, что $$\deg (h) \leq m$$. Тогда$$\|h\| \leq \binom {2m}m ^{1/2}\|f\| .$$ (Символ $$\binom{n}{k}$$ используется здесь и неоднократно в дальнейшем для обозначения биномиальных коэффициентов, т. е. числа сочетаний из $$n$$ по $$k$$.)
Другие полезные границы можно найти, например, в работе .
Для получения официальных документов о завершении программы дополнительного профессионального образования (удостоверения о повышении квалификации, дипломов о профессиональной переподготовке и MBA) необходимо предоставить:
Внимание! Вы можете не заказывать доставку бумажной версии официального документы, а скачать его в электронном виде и распечатать самостоятельно. Информация о выданном документе в течение 1 месяца загружается в Федеральную информационную систему «Федеральный реестр сведений о документах об образовании и (или) о квалификации, документах об обучении» - ФИС ФРДО.
Доступ на новый сайт осуществляется с использованием адреса электронной почты, который был указан вами при регистрации на "старом". Мы постарались перенести все ваши данные с прежнего ресурса, однако не исключена вероятность потери части информации.
При возникновении проблемы со входом, воспользуйтесь функцией сброса пароля
Если вы обнаружите несоответствия, пожалуйста, сообщите нам.