Алгоритмы с многочленами — страница 3

  • Просмотров 6145
  • Скачиваний 84
  • Размер файла 811
    Кб

изучения делимости в множестве целых чисел. Выясним, например, для каких целых чисел 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. и │ Частным от деления на является многочлен ,

остатком – . Это правило в общем виде можно сформулировать так: 1) разделить старший член многочлена f(x) на старший член g(x) и записать результат «под длинной стороной угла»; 2)умножить g(x) на результат действия 1) и записать произведение под многочленом f(x); 3) вычесть из f(x) записанный под ним многочлен; 4) проверить имеет ли результат действия 3) степень меньшую, чем степень g(x); если да (или результат нулевой), то он является остатком, а