Лекции.Орг


Поиск:




Категории:

Астрономия
Биология
География
Другие языки
Интернет
Информатика
История
Культура
Литература
Логика
Математика
Медицина
Механика
Охрана труда
Педагогика
Политика
Право
Психология
Религия
Риторика
Социология
Спорт
Строительство
Технология
Транспорт
Физика
Философия
Финансы
Химия
Экология
Экономика
Электроника

 

 

 

 


Алгоритм Евкліда для знаходження НСД двох ненульових поліномів та.




Розглядаємо два ненульових полінома та степенів та відповідно, нехай .

1. Ділимо на .

Якщо , то

- НСД знайдено,

інакше

.

В останньому випадку з властивості 4 подільності поліномів спільний дільник поліномів та є також дільником остачі . Тобто НСД між та співпадає з НСД між та . Можна зробити перехід до розшуку НСД між та . При цьому степінь поліномів зменшується.

2. Ділимо на .

Якщо , то

- НСД знайдено,

інакше

.

Переходимо до розшуку НСД між та . При цьому степінь поліномів знову зменшується.

3. .

………………….

k-1. .

k. .

k+1. .

Оскільки степінь поліномів на кожному кроці зменшується, то процес поетапного ділення завжди буде скінченим, граничним значення остач буде поліном 0-го степеня.

З останнього кроку видно, що .

Простежуючи поступово вгору ланцюжок ділень, можна зробити висновок, що

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

Якщо НСД між поліномами та є поліном 0-го степеня - число , то з урахуванням властивості 5 подільності поліномів можна стверджувати, що в такому випадку НСД між та дорівнює 1.

Застосувавши властивість 5 подільності поліномів, до - полінома степеня, більшого за 0, можна подати таким чином:

Скоротивши НСД на згідно властивості подільності поліномів 5, отримаємо, що

Висновки:

1. Алгоритм Евкліда є завжди скінченим.

2. За алгоритмом Евкліда знаходимо НСД двох поліномів з точністю до числа.

3. , де - поліном з коефіцієнтом біля старшого степеня .

4. Два полінома взаємно прості тоді і тільки тоді, коли .

Приклад 1

За алгоритмом Евкліда найти НСД між та

Розв’язання.

1. Ділимо на .

 
× 3     -1 -4 -3       -3
  _ 3   -3 -12 -9   -1    
        -3          
× 3   -1 -5 -9 -9        
    _-3 -15 -27 -27        
    -3 -10 -2          
: (-5)     -5 -25 -30        
                   

можна подати так:

, тобто

, степінь остачі менша за степінь

Оскільки нас цікавить НСД з точністю до числа, то ми можемо в процесі ділення множити поліном, що ділиться, на число а залишок скоротити на спільний для всіх його коефіцієнтів дільник.

Отже, за можна взяти

2. Ділимо на .

 
  _ 3     -3      
            -5  
    _-5 -16 -3      
    -5 -25 -30      
: 9              
               

можна подати так:

, тобто

, степінь остачі менша за степінь

3. Ділимо на .

_ 1        
         
  _ 2      
         
         

можна подати так:

, тобто

.

Процес поступового ділення можна зупинити. Останній ненульовий залишок ланцюжка ділень є .

Отже, за алгоритмом Евкліда НСД між та дорівнює .

Відповідь.





Поделиться с друзьями:


Дата добавления: 2016-11-12; Мы поможем в написании ваших работ!; просмотров: 509 | Нарушение авторских прав


Поиск на сайте:

Лучшие изречения:

Логика может привести Вас от пункта А к пункту Б, а воображение — куда угодно © Альберт Эйнштейн
==> читать все изречения...

2255 - | 2185 -


© 2015-2024 lektsii.org - Контакты - Последнее добавление

Ген: 0.011 с.