• Гідрологія і Гідрометрія
• Господарське право
• Економіка будівництва
• Економіка природокористування
• Економічна теорія
• Земельне право
• Історія України
• Кримінально виконавче право
• Медична радіологія
• Методи аналізу
• Міжнародне приватне право
• Міжнародний маркетинг
• Основи екології
• Предмет Політологія
• Соціальне страхування
• Технічні засоби організації дорожнього руху
• Товарознавство продовольчих товарів

Найбільший спільний дільник

Спільний дільник многочленів f(x) та g(x), який ділиться на кожний інший спільний дільник цих многочленів, називається їх найбільшим спільним дільником (НСД) і позначається (f,g). НСД многочленів визначається однозначно з точністю до сталого множника (оскільки, якщо d(x) – НСД , то й c·d(x),де , теж НСД).

Многочлени f(x) та g(x) називаються взаємно простими, якщо кожний їхній спільний дільник є ненульовою константою, тобто (f,g)=1.

Розглянемо спосіб знаходження НСД (алгоритм Евкліда).

Нехай дано многочлени f(x) та g(x), причому . Виконаємо послідовне ділення з остачею:

Тут оскільки послідовність степенів многочленів g(x), r₁(x), r₂(x),... є монотонно спадною. Оскільки степінь r₁(x) не вищий за m-1, де m= deg g, то кількість кроків в алгоритмі не перевищує m.

Оскільки (f,g)=(g,r₁)=(r₁,r₂)=(r₂,r₃)=…=(r_n-1,r_n)=(r_n,0)=r_n, що випливає із записаног вище алгоритму Евкліда. то остання відмінна від нуля остача r_n(x) в цьому алгоритмі і є НСД многочленів f(x) і g(x).

Приклад.

З допомогою алгоритму Евкліда знайти НСД многочленів

f(x)=x³–3x²+3x–1, g(x)=x³–1.

x³–3x²+3x–1=(x³–1)·1+(-3x²+3x)

x³–1=(-3x²+3x)·()+(x–1)

-3x²+3x=(x–1)·(-3x).

Отже, (f,g)=x–1.

НСД більшої кількості многочленів, зокрема, f₁(x), f₂(x),…, f_n(x) шукають так:

d₁(x)=(f₁,f₂), d₂(x)=(d₁,f₃), d₃(x)=(d₂,f₄), …, d_n-1(x)=(d_n-2,f_n).

d_n-1(x) і є НСД многочленів f₁(x), f₂(x),…, f_n(x).

Якщо хоча б два многочлени із системи f₁(x), f₂(x),…, f_n(x) взаємно прості, то НСД усіх цих многочленів дорівнює одиниці.

Якщо позначити d(x)=r_n(x), то, піднімаючись вгору рівностями алгоритму Евкліда, можна отримати вираз

d(x)=f(x)·u(x)+g(x)·v(x),

тобто такі що (f,g) виражається через f(x) і g(x).

Читайте також:

1. Загальні|спільний| напрямки|направлення| розвитку підприємств ресторанного господарства. Його функції.
2. Курорт Парк Сіті, найбільший курорт Юти. 93 траси, 14 підйомників.
3. Лекція 11: Суспільний вплив технологій у концепції М.Маклюена
4. Лекція. Тема 2. Виробництво і його основні чинники. Суспільний продукт.
5. Найбільший спільний дільник та найменше спільне кратне у цілісному кільці.
6. Питання 2. Суспільний продукт і його форми
7. Питання 3. Суспільний продукт і його форми
8. Питання четверте. Суспільний продукт, його структура та відтворення.
9. Подільники напруги
10. Подільники напруги
11. Подільники напруги .

Переглядів: 2013