2.3. Деление многочленов с остатком. Алгоритм Евклида

Определения и обозначения

Деление многочлена A(x) на ненулевой многочлен B(x) с остатком — это представление A(x) = B(x)Q(x) + R(x), где R(x) = 0 или степень R меньше степени B. Оно показывает, какая часть делимого получается умножением делителя на частное и что остаётся сверх неё. Такое равенство удобно и для проверки вычислений, и для поиска общего делителя.

Частное Q(x) — многочлен, на который умножают делитель B(x), чтобы получить часть делимого без остатка. Его находят по старшим членам многочленов, шаг за шагом сокращая старшую степень. Частное нужно, чтобы записать деление в точной форме, а не только оценить его результат.

Остаток R(x) — многочлен, который остаётся после выделения произведения B(x)Q(x); его степень меньше степени делителя либо он равен нулю. Условие на степень означает, что продолжать сокращение уже нельзя. Остаток помогает понять, делится ли A(x) на B(x) нацело: это происходит ровно тогда, когда R(x) = 0.

Алгоритм Евклида — последовательное деление многочленов с остатком для нахождения их наибольшего общего делителя, или НОД. После каждого деления берут пару из прежнего делителя и полученного остатка. Так задача постепенно сводится к многочленам меньшей степени и завершается, когда остаток становится нулевым.

Как это устроено

Сначала сравнивают старшие члены делимого и делителя: их частное становится первым членом Q(x). Затем делитель умножают на этот член частного и вычитают всё произведение из делимого. Вычитать нужно целиком, поскольку именно так устраняется старший член, а остальные члены произведения изменяют оставшуюся часть выражения.

Если после вычитания текущий остаток всё ещё имеет степень не меньше степени делителя, операцию повторяют: снова делят старшие члены и добавляют новый член к частному. При правильном выборе члена частного старшие члены сокращаются, а степень текущего остатка уменьшается. Степень не может убывать бесконечно: она целая и неотрицательная, поэтому процесс заканчивается, когда остаток станет нулём или окажется ниже делителя по степени.

Равенство A(x) = B(x)Q(x) + R(x) объясняет замену многочленов в алгоритме Евклида. Если многочлен делит A и B, то он делит и разность A − BQ, то есть R; если он делит B и R, то делит BQ + R, то есть A. Значит, пары A, B и B, R имеют одни и те же общие делители, хотя сами многочлены в парах меняются.

Для поиска НОД делят первый многочлен на второй, затем делитель — на первый остаток, а дальше продолжают по тому же правилу. Когда очередной остаток равен нулю, последний ненулевой остаток делит предыдущие многочлены и является НОДом с точностью до ненулевого постоянного множителя. Нулевой остаток не берут за ответ: он лишь показывает, что деление на предыдущем шаге выполнилось нацело.

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

Шаги алгоритма Евклида для многочленов

Начните с исходной пары и записывайте каждое равенство деления: так видно, какой остаток использовать на следующем шаге. Остановитесь только при нулевом остатке, а ответом объявите предыдущий, последний ненулевой остаток.

Разбор задач

Задача 1. Разделить x³ − 2x + 1 на x − 1 с остатком.

1. Запишем делимое как x³ + 0x² − 2x + 1, чтобы видеть пропущенный член. Старшие члены дают первый член частного x²: после вычитания x²(x − 1) остаётся x² − 2x + 1.
2. Старший член остатка x² делим на x и получаем x. Вычитаем x(x − 1) = x² − x, получая −x + 1.
3. Делим −x на x и добавляем к частному −1. После вычитания −1(x − 1) = −x + 1 получаем ноль, значит, деление завершено.

Ответ: Q(x) = x² + x − 1, R(x) = 0. Проверка: (x − 1)(x² + x − 1) = x³ − 2x + 1.

Задача 2. Разделить 2x³ + 3x² − x + 5 на x² + x + 1 с остатком.

1. Старшие члены 2x³ и x² дают 2x, поэтому начинаем с него. Вычитаем 2x(x² + x + 1) = 2x³ + 2x² + 2x; остаётся x² − 3x + 5.
2. Теперь старшие члены x² и x² дают 1. Вычитаем x² + x + 1 и получаем −4x + 4.
3. Степень остатка равна 1, а степень делителя — 2, поэтому дальнейшее сокращение невозможно и деление закончено.

Ответ: Q(x) = 2x + 1, R(x) = −4x + 4. Проверка: (x² + x + 1)(2x + 1) + (−4x + 4) = 2x³ + 3x² − x + 5.

Задача 3. Найти НОД многочленов x³ − 1 и x² − 1 алгоритмом Евклида.

1. Делим x³ − 1 на x² − 1. Получаем равенство x³ − 1 = x(x² − 1) + (x − 1).
2. Теперь делим x² − 1 на x − 1. Получаем x² − 1 = (x + 1)(x − 1) + 0.
3. Остаток стал нулевым, поэтому берём последний ненулевой остаток из предыдущего деления.

Ответ: НОД равен x − 1 с точностью до ненулевого постоянного множителя.

Типичные ошибки

Ошибка: считать допустимым остаток той же степени, что и делитель. Так бывает, если забыть, что на каждом шаге нужно проверить, можно ли ещё сократить старший член. Проверьте степени: ненулевой остаток должен быть строго ниже делителя.

Ошибка: при вычитании произведения делителя на член частного терять знак или менять знак только у части произведения. Это случается, когда вычитают по членам не всё выражение целиком. Раскройте скобки и поменяйте знак у каждого слагаемого произведения, затем проверьте вычитание сложением.

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

Ошибка: назвать НОДом последнее частное или нулевой остаток. Последнее частное появляется на заключительном шаге, а ноль означает лишь, что деление выполнилось нацело. Найдите последний ненулевой остаток; любой его ненулевой постоянный множитель задаёт тот же НОД.

Связь с другими темами

Чтобы делить многочлены, нужно уметь складывать, вычитать и умножать их, а также сравнивать степени. Эти навыки помогают корректно выполнять каждый шаг и проверять равенство A(x) = B(x)Q(x) + R(x). Поэтому перед делением полезно привести подобные слагаемые и записать пропущенные степени с нулевыми коэффициентами.

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

Что запомнить

• При делении многочленов A(x) = B(x)Q(x) + R(x).
• Нулевой остаток допускается; иначе его степень меньше степени делителя.
• Частное строят, последовательно сокращая старшие члены.
• В алгоритме Евклида делитель и остаток становятся новой парой многочленов.
• Процесс заканчивается, когда остаток равен нулю.
• Последний ненулевой остаток является НОД с точностью до ненулевого постоянного множителя.