Алгебра · объяснение и практика
Как алгоритм Евклида находит общий множитель многочленов
Как находить общий множитель многочленов делением с остатком, зачем нормируют старший коэффициент и почему выбор поля коэффициентов нужно назвать заранее.

В теме Многочлены: деление и корни · Учебная карта
В маршруте Структура многочленов и восстановление · 10 тем
Главная мысль
Над полем коэффициентов алгоритм Евклида сохраняет общие делители при замене пары P,Q на Q и остаток P от деления на Q. Последний ненулевой остаток задаёт НОД с точностью до ненулевого постоянного множителя.
Остаток сохраняет общие делители
Если P=SQ+R, любой общий делитель P и Q делит R=P−SQ. Обратно, общий делитель Q и R делит P. Поэтому пары P,Q и Q,R имеют одинаковые общие делители. Это то же логическое устройство, что в числовом алгоритме Евклида, но мера уменьшения здесь — степень ненулевого остатка, а не величина положительного числа.
Каждое деление выполняют по обычному правилу многочленов, получая остаток степени меньше делителя. Последовательность таких степеней не может бесконечно убывать. Когда остаток стал нулевым, предыдущий ненулевой многочлен делит последнюю пару, а значит и исходную. Одновременно сохранение общих делителей показывает, что он охватывает любой общий множитель.
Пример
Для P=x³−1,Q=x²−1 имеем P=xQ+(x−1), затем Q=(x+1)(x−1). Нормированный НОД равен x−1.
Прямой контроль: P=(x−1)(x²+x+1), Q=(x−1)(x+1). Следующего общего множителя ненулевой степени у оставшихся частей нет.
Почему ответ нормируют
Многочлены x−1 и 2x−2 над рациональными коэффициентами делят друг друга через ненулевую постоянную. Поэтому без договорённости НОД определён не единственным выражением. Удобно выбрать старший коэффициент, равный единице: такой многочлен называют приведённым. При последнем остатке 2x−2 деление на два даст нормированный x−1.
Договорённость о поле существенна. Над рациональными числами любое ненулевое постоянное является обратимым коэффициентом, поэтому константы не создают содержательного общего множителя положительной степени. Если ограничиться целыми коэффициентами и запрещать дроби, появляются дополнительные вопросы о содержании многочлена. Их нельзя молча смешивать с алгоритмом над полем.
Нули и проверка результата
Если один исходный многочлен нулевой, НОД пары с ненулевым многочленом равен нормированному ненулевому. Для пары двух нулевых многочленов обычная договорённость об единственном приведённом НОД не работает; такой случай нужно оговорить отдельно. На нулевой многочлен делить нельзя, поэтому алгоритм завершает деления до этой попытки.
Проверяйте найденный результат делением обоих исходных многочленов без остатка. Это подтверждает, что множитель общий, но само по себе ещё не доказывает его максимальность. Её обеспечивает цепочка сохранения общих делителей или расширенное тождество Евклида. Так отделяются проверка кандидата и доказательство полного результата.
От чтения к действию
А теперь — вы
Частые вопросы
Означает ли «наибольший» самые большие коэффициенты?
Нет. Речь об общем делителе, который делится на любой другой общий делитель, с учётом выбранной нормировки.
Может ли НОД быть равен единице?
Да. Тогда нет общего множителя положительной степени, и многочлены называют взаимно простыми над выбранным полем.
Источники и работа с материалом
Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.
Продолжить разбираться
Как обратная подстановка выражает НОД через два многочлена
Как обратный ход алгоритма Евклида выражает НОД через исходные многочлены, что доказывает такое тождество и почему коэффициенты могут быть дробными.
Открыть темуПочему тождество многочленов определяет все коэффициенты
Как восстановить неизвестные коэффициенты из тождества, проверить все степени и отличить равенство многочленов от совпадения при одном значении переменной.
Открыть тему