Деление с остатком в . Схема Горнера

Определение. Разделить с остатком многочлен на ненулевой многочлен - значит найти многочлены такие, что

1) и 2) .

При этом многочлен называется остатком, а - неполным частным.

Теорема 8.2. (О делении многочленов с остатком в ). Для любых многочленов существуют, причём единственные многочлены такие, что 1) и 2) .

Таким образом, деление с остатком любого многочлена на ненулевой многочлен с коэффициентами из одного и того же поля всегда возможно, причём единственным образом.

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

Схема Горнера – это алгоритм деления с остатком многочлена на .

Если , то по теореме Безу существует единственный многочлен такой, что . Тогда

получаем следующую систему соотношений:

Замечаем следующую зависимость: получается как сумма и . Заготовкой для вычислений является таблица:

				….

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

Все дальнейшие вычисления производим в таблице:

				….
				….

Пример 17. Разделить с остатком на .

В данном случае . Заполняем заготовку:

		-3			-5
-2

Далее производим вычисления:

		-3			-5
-2		-17		-66		-253

Значит, .

В частности, .

Схема Горнера применяется во многих случаях. В частности, при определении кратности корня многочлена.

Определение. Пусть , где . Тогда называется корнем кратности многочлена . Если , то называется простым корнем.

Пример 18. Найти кратность корня многочлена .

По теореме Безу кратность корня равна количеству делений на с нулевым остатком. Все вычисления выполняем в одной таблице:

		-2		-13		-5
		-1		-9
				-5
			7 0

Значит, ⋮ , но не делится на . Поэтому кратность корня многочлена равна 3.

Заметим, что при вычислении значений в третьей и т.д. строках таблицы, требуемые по схеме Горнера числа брали из стоящей выше строки.