Дипломная работа: Алгоритмы с многочленами

8 . Тогда и только тогда многочлены , одновременно делятся друг на друга, если , .

Из 1. и 8. вытекает свойство:

9 . Всякий делитель одного из двух многочленов , , где , будет делителем и для другого многочлена.

Свойства делимости многочленов могут быть применены для изучения делимости в множестве целых чисел. Выясним, например, для каких целых чисел n числоявляется простым.

Натуральное число, отличное от 1, называется простым, если оно делится только на 1 и на само себя; целое отрицательное число k называется простым, если число –k простое.

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

(2.3)

и поэтому число делится на и на Следовательно, оно может быть простым только в случае, когда один из этих делителей равен 1 или –1, т.е. выполняется хотя бы одно из равенств

Остается проверить следующие значения n : 3, 1, 0, -3, -1 и –2. При этих значениях n рассматриваемое число равно соответственно 19, -5, 3, 4, так что искомое множество чисел есть

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

Из этого примера видно, что уже для решения задач, связанных с делимостью целых чисел, полезно уметь выяснять, делится ли данный многочлен на некоторый другой многочлен (раскладывается ли на множители).Ответ на такой и многие другие вопросы можно найти с помощью деления многочлена с остатком.

2.2. Деление многочленов с остатком

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

Теорема о делении с остатком. Для любых двух многочленов f ( x ) и g ( x ) можно найти такие многочлены q ( x ) и r ( x , что

f ( x )= g ( x ) q ( x )+ r ( x ),

причем степень r ( x ) меньше степени g ( x ) или же r ( x )=0. Многочлены q ( x ) и r ( x ), удовлетворяющие этому условию, определяются однозначно.

Если разности f ( x )- r ( x ) и обе делятся наg ( x ), то их разность также делится наg ( x ). Если бы многочлен s ( x ) был ненулевым, то он имел бы степень меньшую, чем g ( x ), и не мог бы тогда делится наg ( x ). Следовательно, s ( x )=0, так что .

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

Пример. Найти частный и остаток от деления на .

1. и

|

Частным от деления на является многочлен , остатком – .

2. и

│