Розглядаємо два ненульових полінома та степенів та відповідно, нехай .
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 | ||||
можна подати так:
, тобто
.
Процес поступового ділення можна зупинити. Останній ненульовий залишок ланцюжка ділень є .
Отже, за алгоритмом Евкліда НСД між та дорівнює .
Відповідь.