П. 3. Делимость многочленов

Пусть - кольцо многочленов одной переменной х над полем Р.

Опр.3. Пусть . Говорят, что делится на (и пишут ), если .

Свойства делимости многочленов:

1) .

2) .

Так как .

3) .

Теорема 2 (о делении многочленов с остатком). Для любых многочленов существуют единственные многочлены такие, что , при этом или .

(Знать определение степени многочлена, высшего (старшего) члена многочлена).

Доказательство: 1. Возможность деления с остатком. Пусть , .

1 случай. Если или , то и существование представления доказано.

2 случай. Пусть теперь , , .

Рассмотрим многочлен . , так как

многочлены и имеют одинаковые высшие члены , которые при вычитании взаимно уничтожаются.

Если или , то процесс закончен и искомое представление .

Пусть теперь и старший коэффициент многочлена равен , то строим многочлен . Аналогично устанавливаем, что .

Если или , то процесс закончен.

Пусть теперь , старший коэффициент равен . Строим многочлен . .

И так далее…

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

Сложив почленно равенства , , ,…, , получим

. То есть , возможность деления с остатком доказана.

2. Единственность деления с остатком.

Допустим, что

, где или

, где или

Отсюда имеем:

Если , то есть , то так как , то из равенства имеем, что и единственность деления с остатком доказана.

Пусть теперь . Тогда из равенств . Если при этом , то . Значит и . Единственность деления с остатком доказана. ▲.

Пример: Разделить многочлен на .

Значит .

 

 

ВОПРОС № 12 Алгоритм Евклида для целых чисел и для многочленов. НОД и НОК.

 

Опр.1. Пусть - целые числа, из которых хотя бы одно отлично от нуля. Наибольшим общим делителем чисел а₁,…,а_k называется такое целое число , что:

1) ;

2) - общий делитель этих чисел (то есть ).

3) делится на любой общий делитель чисел .

Обозначается НОД чисел так: .

Теорема 1. Если НОД целых чисел существует, то он определяется однозначно.

Доказательство: Пусть и .

Так как - общий делитель , а - их НОД, то .

Так как - общий делитель , а - их НОД, то .

А так как , , то из и . ▲.

Теорема 2. НОД целых чисел равен НОД их модулей, то есть .

Поэтому в дальнейшем можно рассматривать НОД натуральных чисел.

 

Алгоритм Евклида

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

Пусть . Делим на с остатком: , .

Если , то процесс закончен и .

Если , то делим на с остатком: , .

Если , то процесс закончен, если , делим на : , .

Поскольку остатки, являясь неотрицательными целыми числами, убывают, то процесс деления оборвётся и на каком-то шаге мы получим остаток, равный нулю.

Пусть ,

.

Теорема 3. Последний, отличный от нуля, остаток в алгоритме Евклида, составленном для чисел , является наибольшим общим делителем чисел .

Доказательство: Пусть - последний отличный от нуля остаток, тогда:

1) .

2) Покажем, что - общий делитель чисел . Для этого рассмотрим последовательно равенства алгоритма Евклида, начиная с последнего. Из этого равенства следует, что

, кроме того, . Тогда , то есть ; затем получим, что и т.д. И, наконец, из второго и первого равенств имеем, что и .

3) Покажем, что делится на любой общий делитель чисел . Для этого рассмотрим равенства алгоритма, начиная с первого. Пусть - произвольный общий делитель чисел , то есть и , то есть

то есть и т.д. И, наконец, .

Число удовлетворяет всем условиям определения НОД чисел . ▲.

Следующая теорема даёт способ отыскания НОД нескольких целых чисел.

Теорема 4. Если , , …, , то .

 

НОК целых чисел

Опр.2. Общим кратным целых, отличных от нуля чисел называется целое число с, которое делится на каждое из чисел , то есть .

Опр.3. Целое число т называется наименьшим общим кратным целых, отличных от нуля чисел , если: 1) ;

2) т есть общее кратное чисел ;

3) любое общее кратное чисел делится на число т.

Обозначается НОК чисел так: .

Теорема 5. Если НОК целых чисел существует, то оно единственно.

Теорема 6. НОК целых чисел равно НОК их модулей.

Доказательства теорем 5 и 6 аналогичны доказательствам теорем 1 и 2.

Теорема 6 позволяет рассматривать НОК только натуральных чисел. Следующая теорема даёт способ отыскания НОК двух натуральных чисел:

Теорема 7. .

Доказательство: покажем, что число удовлетворяет всем трём условиям определения НОК целых чисел.

1) Во-первых, , так как .

2) Покажем, что число есть общее кратное чисел .

Обозначим , причем числа взаимно просты, то есть .

Теперь имеем: .

3) Покажем, что любое общее кратное чисел делится на число .

Пусть т – произвольное общее кратное чисел , то есть .

. Но , тогда

 

. Теперь имеем:

.

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

Следующая теорема позволяет находить НОК нескольких чисел:

Теорема 8. Если , , , …, , то .