Файл: Нод и нок многочленов.docx

Глава 2. Наименьшее общее кратное, наибольший общий делитель. Алгоритм Евклида

2.1 Наибольший общий делитель

Пусть   и   - многочлены с коэффициентами в целочисленной области  , обычно поле или целые числа. Наибольший общий делитель   и    - это многочлен  , который делит   и  , и такой, что каждый общий делитель   и    также делит   . Каждая пара многочленов (не оба равны нулю) имеет GCD тогда и только тогда, когда   является уникальной областью факторизации.

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

---

, что в данном случае он не определен.

Наибольший общий делитель   и    обычно обозначается как

Наибольший общий делитель не является уникальным: если d является НОД из   и   , то многочлен  является другим НОД тогда и только тогда, когда существует обратимый элемент   из   такой, что



и

{\displaystyle d=u^{-1}f}

Другими словами, GCD уникален с точностью до умножения на обратимую константу.

В случае целых чисел эта неопределенность была решена путем выбора в качестве GCD единственного положительного (есть еще один, который является его противоположностью). Согласно этому соглашению, НОД двух целых чисел также является наибольшим (для обычного порядка) общим делителем. Однако, поскольку для многочленов над целочисленной областью не существует естественного общего порядка, здесь нельзя действовать таким же образом. Для одномерных многочленов над полем можно дополнительно потребовать, чтобы GCD был одномерным (то есть иметь 1 в качестве коэффициента наивысшей степени), но в более общих случаях общего соглашения нет. 

Следовательно, равенства типа   или   являются распространенными злоупотреблениями обозначениями, которые следует читать как "  -это GCD из  " и "  и   имеют тот же набор GCD, что и 

---

 и  ". В частности,   означает, что обратимые константы являются единственными общими делителями. В этом случае, по аналогии с целочисленным случаем, говорят, что   и   равны взаимно простые многочлены. [9]

---

2.2 Наименьшее общее кратное

Пусть даны многочлены и над полем .

Определение 1. Многочлен называется общим кратным многочленов и , если и .

Определение 2. Наибольшим общим кратным (НОК) многочленов и называется такое их общее кратное, на которое делится любое общее кратное этих многочленов.

Замечание. Наибольшим общим кратным (НОК) многочленов и обозначается НОК ( , ) или НОК или .

Теорема 1. НОК многочленов и вычисляется по формуле:

(1.6)

Таким образом, НОК двух многочленов есть частное от деления произведения этих многочленов на их НОД.

Доказательство. Пусть НОД многочленов , тогда и . Поставим в формулу 1.6 вместо его значение, получим:

---

Следовательно, .

В равенстве 1.6 подставим вместо его значение, получим:



Следовательно, .

Итак, многочлен является общим кратным многочленов и . Пусть есть наименьшее общее кратное многочленов и . Требуется доказать, что . Так как – общее кратное и , то и . Пусть и . Будем иметь, что . Делим обе части последнего равенства на и получаем:



Многочлены и делятся на свой НОД , в частном получим взаимно простые многочлены и . Многочлен будет делиться на . Подставляя значение

---