86061

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

Лекция

Математика и математический анализ

Вивчити алгоритм Евкліда знаходження найбільшого спільного дільника многочленів; вивчити основну властивість НСД двох многочленів; вивести критерій взаємно простих многочленів...

Украинкский

2017-02-21

367.5 KB

6 чел.

Лекція № 2.

Тема.Найбільший спільний дільник.

Мета вивчання:

  • вивчити алгоритм Евкліда знаходження найбільшого спільного дільника многочленів;
  • вивчити основну властивість НСД двох многочленів;
  • вивести критерій взаємно простих многочленів.

План

  1. Найбільший спільний дільник многочленів. Алгоритм Евкліда.
  2. Основна властивість НСД многочленів.
  3. Взаємно прості многочлени та їх властивості.

Література:[13], стор.137-143, 149.

Зміст лекції

1. Нехай дано довільні ненульові многочлени  і . Многочлен  називаєтьсяспільним дільником для  і , якщо він служить дільником для кожного з цих многочленів.

Властивість V показує, що до числа спільних дільників многочленів  і  належать усі многочлени нульового степеня. Якщо інших спільних дільників ці два многочлена не мають, то вони називаютьсявзаємнопростими.

Найбільшим спільним дільником ненульових многочленів і називається такий многочлен , який є їх спільним дільником, і разом з тим сам ділиться на будь-який інший спільний дільник цих многочленів. НСД позначається так: ().

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

Теорема (про існування НСД многочленів).НСД многочленів  і співпадає з останньою ненульовою остачею в алгоритмі Евкліда.

# Для доведення запишемо викладене вище у вигляді наступних рівностей:

(1)

Остання рівність показує, що  є дільником для . Звідси виходить, що обидва доданки правої частини передостанньої рівності діляться на , а тому  буде дільником і для . Далі, таким самим шляхом, підіймаючись угору, ми отримаємо, що  є дільником і для . Звідси, ураховуючи другу рівність, буде слідувати, що  служить дільником для , а тому, на підставі першої рівності, - і для . Таким чином,  є спільним дільником для  і .

Візьмемо тепер довільний спільний дільник  многочленів  і . Тому що ліва частина і перший доданок правої частини першої з рівностей (1) діляться на , то  також буде ділитися на . Переходячи до другого і наступних рівностей ми таким самим засобом одержимо, що на  діляться  многочлени . Нарешті, якщо вже буде доведено, що  і  діляться на , то із передостанньої рівності ми одержимо, що  ділиться  на . Таким чином,  дійсно буде найбільшим спільним дільником для  і .   #

Теорема (про єдність НСД многочленів).НСД многочленів  і  є єдиним з точністю до множника нульового степеня (число), тобто усі НСД двох даних ненульових многочленів є асоційованими многочленами.

# Нехай  і  - НСД многочленів  і , тоді, якщо  - НСД, то він повинен ділитися на , а з другого боку  - НСД, значить він повинен ділитися на , звідси слідує, що #

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

Користуючись цією умовою, можна сказати, що два многочлени тоді і тільки тоді взаємно прості, якщо їх найбільший спільний дільник дорівнює одиниці.

Приклад. Знайти НСД многочленів  і

     

          

Відповідь: .

2.Теорема.Якщо  НСД многочленів  і , то можна знайти такі многочлени  і , що

(2)

можна вважати при цьому, якщо степінь многочленів  і  більше 0, що степінь  менше степеня , а степінь  менше степеня  (всі многочлени з кільця ).

# Доведення основане на рівностях (1). Якщо ми вважаємо, що  і позначимо , то передостання з рівностей (1) дасть:

.

Підставляючи сюди вираз  через  і  із попередньої рівності (2), одержуємо:

,

де, очевидно, . Продовжуючи підніматися вгору по рівностям (1), прийдемо, нарешті, до рівності (2). Для доведення другого твердження теореми припустимо, що многочлени і , що задовольняють рівності (2), вже знайдені, але, наприклад, степінь  більший або дорівнює степеню . Ділимо  на :

,

де степінь  менший за степінь , і підставляємо цей вираз у (2). Одержуємо рівність

.

Степінь, що стоїть при , вже менший степеня . Степінь многочлена, що стоїть у дужках, буде в свою чергу, менший степеня , тому що у протилежному випадку степінь другого додатку лівої частини був би не менший степеня добутку , а тому що степінь першого доданку менший степеня цього добутку, то уся  ліва частина мала б степінь, більший або рівний степеню , тоді як многочлен  свідомо має при наших припущеннях, менший степінь. #

Приклад 2. Знайти многочлени  і , що задовольняють рівність (2), якщо , .

# 1). Знаходимо НСД:

2). Відшукуємо  і :

Запишемо (2) у вигляді

, в результаті чого робота спроститься  степ.,  степ.,.

.

.

3. Два многочлени називаютьсявзаємно простими, якщо їх НСД є многочлен нульового степеня (з точністю до постійного множника – це 1).

Теорема (критерій взаємно простих многочленів)

Два многочлени  і  є взаємно простими тоді, і тільки тоді, коли існують многочлени  і  що задовольняють умові:

.(3)

# Відомо, що для будь-яких многочленів і  існують многочлени  і , що задовольняють (2). Нехай і  взаємно прості, тобто їх НСД є многочлен нульового степеня, тоді рівність (2) буде мати вигляд: .

Навпаки, нехай  і  такі, що для них існують  і  такі, що виконується (3).

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

Ізвластивостей взаємно простих многочленів відзначимо наступні:

1). Якщо многочлен  взаємно простий з кожним із многочленів   та , то він взаємно простий із їх добутком.

# Дійсно, існують за (3) такі многочлени  і , що

.

Помножуючи цю рівність на , одержимо:

.

Звідки слідує, що будь-який спільний дільник  і  був би дільником і для ; однак, за умови .#

2). Якщо добуток многочленів  і  ділиться на , але  і  взаємно прості, то  ділиться на .

# Дійсно, помножуючи рівність

на , одержимо:

.

Обидва доданки лівої частини цієї рівності діляться на ; на нього діляться, отож, і . #

3). Якщо многочлен  ділиться на кожний з многочленів  і , які між собою взаємно прості, то  ділиться і на їх добуток.

# Дійсно, , так що добуток, що стоїть справа, ділиться на . Тому за властивістю 2,  ділиться на , звідки .  #

Зауваження. Усі доведені властивості взаємно простих многочленів можуть бути узагальнені на випадок будь-якого скінченого числа многочленів, що задовольняють згаданим умовам.

Питання для самостійної роботи.

Виконання розрахункової роботи №2. Тема: “Подільність многочленів”.

Дробово-раціональні функції. Розклад на найпростіші дроби. ([2], стор.210-213)


 

А также другие работы, которые могут Вас заинтересовать

67147. Язык и речь. Речевая деятельность 110.5 KB
  Различение языка и речи было намечено выдающимся немецким теоретиком языкознания Вильгельмом фон Гумбольдтом (1767–1835). Позже, в отечественном языкознании эту мысль развивал Иван Александрович Бодуэн де Куртенэ (1845–1929). Более детально и последовательно идею о противопоставлении языка и речи разработал...
67148. ДИАГРАММЫ СОСТОЯНИЯ СПЛАВОВ. ПРАВИЛО ФАЗ 35.5 KB
  В сплавах: фазами могут быть чистые металлы жидкие или твердые растворы химические соединения. Число степеней свободы Степень свободы определяется числом независимых переменных например температура концентрация сплава давление которые можно изменять в определенных пределах не нарушая равновесия.
67149. Споживчий ринок товарів. Товарні ресурси 27.87 KB
  Поняття товарних ресурсів класифікація джерела їх створення Баланс ресурсів товарів народного споживання їх роль у прогнозуванні та плануванні внутрішнього ринку товарів народного споживання. За рахунок товарної продукції промисловості сільського господарства а також імпорту товарів формуються товарні ресурси держави.
67150. Геоинформатика и геоинформационные системы 88.5 KB
  Геоинформационная система (ГИС) это система направленная на хранение исходных данных и (или) решение задач связанных с получением конечных данных необходимых для пользователя данной системы.
67151. Последовательностные ИМС 324 KB
  Если выходные сигналы логических элементов и комбинационных микросхем однозначно определяются их текущими входными сигналами то выходные сигналы микросхем с внутренней памятью зависят также еще и от того какие входные сигналы и в какой последовательности поступали...
67152. Технико-экономическое обоснование проектов программных средств 230 KB
  Номенклатура работ их трудоемкость длительность и другие экономические характеристики на этих этапах ЖЦ существенно зависят от характеристик объекта технологии и инструментальной среды разработки. Сокращение этой потребности в ресурсах часто возможно только за счет принципиального изменения...
67154. ПЕРЕЛИВАНИЕ КРОВИ И ЕЕ КОМПОНЕНТОВ 273 KB
  Знать: противопоказания к донорству; антигенные системы крови АВО и Rh; показания противопоказания осложнения технику гемотрансфузий. Уметь: Определять группы крови по системе АВО прямым способом ставить пробы на совместимость при гемтрансфузии оказывать первую...
67155. Становлення української національної культури у першій половині XIX століття 190 KB
  Українське національне відродження розпочалося на східноукраїнських землях на межі ХVІІІ – ХІХ ст. Воно стимулювалося, з одного боку, природними процесами загальнокультурного розвитку, з іншого – необхідністю протидії упосліджувальній політиці російського царизму.