Многочлены над кольцом классов вычетов (стр. 3 из 6)

4. Схема Горнера и теорема Безу.

В кольце многочленов деление в обычном смысле слова, как правило, невозможно. Например, в кольце

многочлен x2 нельзя разделить на x + 1, т.е. не существует такого многочлена g(x), что x2 = g(x)(x + 1) (если бы такой многочлен существовал, то при x = -1 мы получили бы невозможное равенство ).

Если для полиномов f(x) и g(x) из K[x] существует такой полином

, что f(x) = g(x)h(x), то говорят, что полином f(x) делится на полином g(x). Наша ближайшая задача заключается в выяснении вопроса о делимости на линейный двучлен x - c при .

Прежде всего установим, что всегда осуществимо так называемое деление с остатком:

при . Здесь полином h(x) называется неполным частным, а r - остатком.

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

и . Найдутся полином и элемент такие, что . При этом .

Доказательство. Естественно искать h(x) в форме

. Сравнение коэффициентов многочлена в левой части равенства = = с коэффициентами многочлена, полученного после раскрытия скобок и приведения подобных, в правой части этого равенства приводит к цепочке равенств

откуда последовательно определяют коэффициенты h(x) и остаток r:

(8)

Равенство

непосредственно следует из равенства после подстановки в последнее вместо x элемент c.

Теорема доказана. Кроме того, получен очень удобный способ вычисления коэффициентов h(x) и остатка r. Этот способ носит название схемы Горнера. Вычисления удобно располагать в виде таблицы:

	a0	a1	a2	...	an-1	an
c	b0	b1	b2	...	bn-1	c

Элементы нижней строки вычисляются последовательно по формулам (8): b0 = a0, a каждый последующий элемент равен сумме элемента, находящегося над ним, и предыдущего элемента нижней строки, умноженного на x0.

Элемент c кольца K называется корнем полинома f(x), если

.

Следствие (теорема Безу). Многочлен f(x) делится на

в кольце K[x] тогда и только тогда, когда c - его корень.

Доказательство. Пусть f(x) делится на

, т.е. . Тогда .

Пусть

. Тогда в равенстве будет , т.е. . Следствие полностью доказано.

Теорема 3. Число корней ненулевого многочлена не превосходит его степени.

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

, и докажем его для любого многочлена f(x) степени n. Предположим, рассуждая от противного, что x1, x2, ..., xm - корни многочлена f(x), причем . По теореме Безу, f(x) делится на , т.е. , где g(x) - некоторый многочлен степени . Элементы x2, ..., xm кольца K являются корнями многочлена g(x). В самом деле, при имеем: . Так как , а кольцо K не имеет делителей нуля, то . Таким образом, многочлен g(x) имеет не менее чем корней, что противоречит предположению индукции, поскольку . Теорема доказана.

Следствие. Многочлен степени не выше n однозначно определяется своими значениями в

точках.

Иначе говоря, существует не более одного многочлена степени не выше n, принимающего в данных (различных) точках

данные значения y1, y2, ..., yn+1.

Доказательство. Предположим, что f(x), g(x) - два многочлена степени не выше n, принимающие одинаковые значения в точках

. Рассмотрим многочлен . Степень этого многочлена также не выше, чем n. Так как , то при , т.е. - корни многочлена h(x). Согласно теореме 3 h(x) = 0, т.е. f(x) = g(x).

Теорема 4. Если кольцо K бесконечно, то равенство функций, определяемых двумя многочленами из кольца K[x], влечет за собой равенство самих многочленов.

Доказательство. Пусть многочлены

определяют одинаковые функции. Это означает, что для любого . Обозначим через n наивысшую из степеней многочленов f(x), g(x). Так как кольцо K бесконечно, то в нем найдутся различных элементов . Согласно нашему предположению, многочлены f(x) и g(x) принимают одинаковые значения в каждой из точек (как и вообще в любой точке). Следствие теоремы 3 позволяет сделать отсюда вывод, что .

Для конечного кольца K утверждение теоремы 4 неверно. Однако при некоторых дополнительных предположениях и в этом случае оказывается возможным из равенства функций, определяемых двумя многочленами, сделать вывод о равенстве самих многочленов.

6. Вычисление наибольшего общего делителя.

Наибольший общий делитель двух многочленов f и g из кольца R[x] многочленов над полем R может быть найден при помощи алгоритма Евклида. Алгоритм Евклида нахождения наибольшего общего делителя состоит в следующем. Сначала делят с остатком многочлен f на многочлен g, затем многочлен g - на остаток от первого деления, затем остаток от первого деления - на остаток от второго деления и т.д., пока не получится нулевой остаток. Это дает следующую цепочку равенств:

(9)

причем

, поэтому процесс деления конечен. Пусть , т.е. f и g принадлежат одному и тому же главному идеалу . Поэтому их разность , т.е. . Аналогично можно доказать, что , и т.д. Таким образом, . Из последнего равенства (21) следует, что , тогда . Поэтому . Следовательно, по теореме 14 , т.е. . Таким образом, последний ненулевой остаток (т.е. rk) и есть наибольший общий делитель многочленов f и g.