22885

Алгоритм знаходження НСД

Доклад

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

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

Украинкский

2013-08-04

71 KB

3 чел.

Алгоритм знаходження НСД

Задано два не нульових многочлени  і .   стст (для однозначності).

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

Покажемо, що  для цього перевіримо наступні умови:

  1.  покажемо  і  з останньої рівності слідує , аналогічно  і т.д. Одержимо , , .
  2.  Припустимо ,  оскільки , то , з цього слідує  це співвідношення справедливе для наступних  

Умови НСД виконуються, тому .


 

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

69203. Природа виникнення аеродинамічних сил. Принципи створення піднімальної сили 8.87 MB
  Картина обтікання крила літака потоком повітря показана на рис. Повна аеродинамічна сила крила: а картина обтікання крила літака потоком повітря; б схема створення повної аеродинамічної сили R.21 а наглядно видно що потік обтікає верхню і нижню частини профілю крила неоднаково.
69204. Основні закони руху повітря, що стискається. Загальні відомості про аеродинаміку великих швидкостей 3.81 MB
  Таким чином величина стиснення залежить від відношення швидкості потоку до швидкості звуку. Це відношення називається числом Маха і вважається критерієм стисливості потоку. Чим більше швидкість повітряного потоку швидкість польоту V і менше швидкість звуку...
69205. Хвильова криза. Поняття про критичне число Маха 8.3 MB
  Найменша швидкість дозвукового польоту при якій у якійнебудь точці крила швидкість потоку що обтікає крило стає рівної місцевої швидкості звуку називається критичною швидкістю польоту Vкр а відповідне їй число Маха польоту критичним Мкр.
69206. Основні види руху літального апарату. Горизонтальний політ літака 1.78 MB
  Основними видами руху які розглядаються в динаміці польоту є горизонтальний політ набір висоти зниження зліт посадка віраж та ін. При розрахунках льотних даних літака зручно користуватися графічними залежностями тяги від швидкості і висоти польоту.
69207. Зліт і посадка літака 6.06 MB
  Зліт і посадка є відповідно первинним і завершальним етапами польоту літака. При зльоті й при посадці змінюються швидкість і висота польоту тому рух літака в цих режимах є несталим. Зліт і посадка літака найбільш відповідальні етапи польоту що вимагають від льотчика граничної уваги і точності.
69208. ЛІТАК ТА ЙОГО СИСТЕМИ 1.62 MB
  Швидкісна система координатних осей ОXYZ використовується для вивчення аеродинамічних сил та при розвязанні задач аеродинамічного розрахунку літака рис. Початок швидкісної системи координатних осей розміщено в центрі мас літака. Головною віссю є швидкісна вісь ОХа направлена по вектору швидкості літака.
69209. Середні величини та показники варіації 167.5 KB
  Середня величина це узагальнююча кількісна характеристика сукупності однотипних явищ по одній варіюючій ознаці. Найважливішою умовою наукового використовування середніх величин в статистичному аналізі суспільних явищ в тому числі й методом динамічних...
69211. Статистка робочої сили та робочого часу 291 KB
  Статистка робочої сили та робочого часу. Суть та значення робочої сили та робочого часу. Статистика робочого часу та його структури. Аналіз використання робочого часу.