22885

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

Доклад

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

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

Украинкский

2013-08-04

71 KB

3 чел.

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

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

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

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

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

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


 

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

64656. Стратегический и эволюционный менеджмент: сравнение стратегий Японских Американских и Российских компаний 130.8 KB
  Целью курсовой работы является раскрытие понятий стратегического и эволюционного менеджмента, изучение стратегий и проведение анализа стратегий американских, японских и российских организаций.
64657. Статистико-экономический анализ рынка труда Новосибирской области 143.07 KB
  Цель курсовой работы – статистико-экономический анализ рынка труда. Задачи курсовой работы: изучение теоретических основ статистико-экономического анализа рынка труда, группировка выбранных регионов по уровню занятости, изучение связи между уровнем занятости и объемом инвестиций в экономику...
64658. Публицистическое начало в блог-журналистике 157 KB
  Интернет стал наиболее быстрым средством получения и обмена информации и как следствие получили широкое развитие и интернет СМИ. Интернет стал наиболее быстрым средством получения и обмена информации и как следствие получили широкое развитие и интернет СМИ.
64661. АНАЛИЗ МЕТОДОВ КОЛЬКУЛИРОВАНИЯ СЕБЕСТОИМОСТИ ПРОДУКЦИИ 256.15 KB
  Цель курсовой работы - проанализировать методы учета себестоимости продукции. Данная цель реализуется в работе на основе решения следующих задач: раскрыть понятие и сущность себестоимости продукции и описать основные методы учета затрат и калькулирования себестоимости.
64662. Технико-экономическое обоснование предпринимательского решения по созданию нового производства 95.99 KB
  Расчет текущих издержек на производство и реализацию продукции Определение выручки от реализации продукции финансовых результатов реализации проекта и критического объема производства Исходя из поставленной цели курсовой работы необходимо решить следующие задачи: обосновать состав и содержание...
64663. Состояние письма учащихся младших классов школы для детей с ТНР 5.23 MB
  Цель исследования: выявить особенности письма учащихся младших классов школы с ТНР. Гипотеза исследования. Мы предполагаем, что у детей 2 класса с ТНР будут наблюдаться трудности в формировании письма, проявляющиеся в ошибках языкового анализа и синтеза...
64664. КОММЕРЧЕСКИЕ БАНКИ И ИХ ФУНКЦИИ В РЫНОЧНОЙ ЭКОНОМИКЕ 376.41 KB
  Банки составляют неотъемлемую часть современного денежного хозяйства, их деятельность тесно связана с потребностями воспроизводства. Они находятся в центре экономической жизни, обслуживают интересы производителей...