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

в равенство , будем иметь:



Итак, любое любое общее кратное многочленов и ) делится на ). Следовательно, ) есть НОК многочленов и ). Теорема доказана. [1,2,11]

Пример 1. Найти НОК многочленов.



Решение:

1. 
   Найдем НОД
   

А) . Получаем, что ;

Б) . Получаем, что ;

Итак, НОД .

2. 
   
   
3. 
   
   

По схеме Горнера



Ответ: .

---

2.3 Алгоритм Евклида нахождения наибольшего общего делителя двух чисел

Пусть даны целые числа . Для вычисления наибольшего делителя существует хорошо известный алгоритм Евклида.





, ,

Тогда и для его нахождения требуется выполнить делений с остатком. Оценим сначала количество шагов алгоритма Евклида.[4]

Определение 3. Последовательностью чисел Фибоначчи называется рекуррентная последовательность вида



Обозначим также через положительный корень квадратного уравнения

Лемма 1. При любом справедливо неравенство .

Доказательство проведем индукцией по . При неравенство проверяется непосредственно. Далее, используя предположение индукции и определение последовательности Фибоначчи, имеем



Теорема 1.3. Число делений с остатком в алгоритме Евклида для нахождения наибольшего общего делителя чисел не превосходят величины

Доказательство. Индукцией по докажем, что

---

. При данное неравенство выполнено, так как . Для в силу предположения индукции имеем

.

В силу доказанного или

Из последнего неравенства следует оценка числа шагов алгоритма Евклида. Теперь оценим сложность алгоритма Евклида. Пусть , где - число шагов алгоритма. Очевидно, выполняются условия

. Тогда, учитывая сложность деления с остатком, можно оценить сложность алгоритма Евклида величиной

.

Так как оценивается теоремой 1.3 как , то сложность всего алгоритма можно оценивать величиной . Если длина чисел не превосходит , то полученная оценка имеет вид .

Без доказательства приведем еще одну оценку для количества шагов алгоритма Евклида. [7]

Теорема 1.4. Число делений с остатком в алгоритме Евклида для нахождения наибольшего общего делителя не превосходит величины .

Замечание. Оценка теоремы Ламе достижима. Так , и для нахождения наибольшего общего делителя требуется ровно 5 шагов алгоритма Евклида.

Приведем также без доказательства теорему о среднем числе шагов алгоритма Евклида.

---

Теорема 1.5. Если целочисленные случайные величины равномерно и независимо распределены на множестве , и - случайная величина, равная числу шагов алгоритма Евклида нахождения , то

.

При переходе к десятичным логарифмам имеем . Значит, полученные выше оценки числа шагов алгоритма Евклида в среднем завышены примерно в два с половиной раза. [4]

---

2.4 Расширенный алгоритм Евклида

Пусть алгоритм Евклида на каждом шаге, кроме частного и остатка , вычисляет еще два значения по правилу









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

Легко показать, что длина чисел оценивается величиной . Значит, сложность расширенного алгоритма Евклида отличается от сложности обычного алгоритма Евклида не более чем на константный множитель, т.е. для расширенного алгоритма Евклида сохраняется оценка сложности . [6]

2.5 Другие алгоритмы вычисления наибольшего общего делителя

Рассмотрим сначала один из простейших способов ускорения работы алгоритма Евклида. Пусть в ходе выполнения алгоритма вычисляются величины





,



Здесь на

---