22885

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

Доклад

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

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

Украинкский

2013-08-04

71 KB

3 чел.

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

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

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

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

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

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


 

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

36878. Определение ёмкости конденсаторов измерительным мостиком Соти 85 KB
  Тема: Определение ёмкости конденсаторов измерительным мостиком Соти. Цель работы: измерение теплоёмкостей двух конденсаторов проверка закона последовательного и параллельного соединения конденсаторов. Пусть Δφ1 Δφ2 – мгновенные значения напряжений на обкладках конденсаторов а ΔφN ΔφNB – мгновенные значения напряжений на сопротивлениях R1 R2.
36880. Определение заряда иона водорода 63.5 KB
  Тема: Определение заряда иона водорода. Цель работы: изучить прохождение тока в электролитах определить заряд иона водорода оценить погрешность данного метода определения заряда иона водорода и ознакомиться с явлением наводораживания металлов. КРАТКАЯ ТЕОРИЯ Для определения заряда иона водорода можно использовать прохождение тока в электролитах явление электролиза.
36882. Word: Ввод и редактирование текста. Операции с фрагментами текста 99 KB
  ввод пробела: при нажатии клавиши Пробел вводится занимающий определенное место в строке символ пробела; наличие или отсутствие пробела в конце строки может быть определено при нажатии на кнопку Непечатаемые знаки на Стандартной панели инструментов в правой стороне; Введите в расположенной ниже строке по одному пробелу между цифрами 1 и 2 и еще три пробела в конце строки. Ввод пробелов: 1111122222311112222311122231122313 Отобразите на экране символы пробела абзаца разрыва строки нажатием на кнопку Непечатаемые знаки на Стандартной панели...
36883. Визначення відношення теплоємності повітря при постійному тиску до теплоємності повітря при постійному об’ємі 544 KB
  Визначення відношення теплоємності повітря при постійному тиску до теплоємності повітря при постійному об’ємі. Якщо у балон з’єднаний з відкритим водяним манометром накачати повітря і зачекати встановлення теплової рівноваги повітря в балоні з навколишнім середовищем то в цьому початковому стані 1 газ має параметри причому температура газу в балоні дорівнює температурі навколишнього середовища а тиск трохи більший від атмосферного. Якщо тепер на короткий час з’єднати балон з атмосферою то станеться адіабатичне розширення повітря....
36884. Прилади індукційної, електростатичної, термоелектричної та випрямляючої систем 301 KB
  Прилади індукційної системи ПРИЗНАЧЕННЯ Й ОБЛАСТЬ ЗАСТОСУВАННЯ Електровимірювальні прилади індукційної системи призначаються для вимірювання електричних величин тільки в ланцюгах змінного струму. Причому на відміну від приладів змінного струму інших систем індукційні прилади можуть бути застосовані в ланцюгах з однією певною частотою і незначна зміна цієї частоти в ту або іншу сторону від номінальної спричиняє більші погрішності показань. У цей час із числа індукційних приладів наші заводи виготовляють тільки лічильники електричної енергії...
36885. Ознайомлення з роботою програмного симулятора dScope-51 123.5 KB
  1 Запуск програми dScope відбувається в середовищі Windows з вікна програм DSW51 Після запуску на екрані монітору з`являється типове вікно Windows з строчкою заголовку вікна кнопками системного меню згортання мінімізації та розгортання. За допомогою команда меню View Вид викликаються робочі вікна: Toolbr дозволяють підключати в вікно програми лінійку кнопкових перемикачів прискореного доступу до певних команд та вікон. Sttus Br дозволяють підключати в вікно програми лінійку статусу де наводиться інформація про...
36886. Прилади магнітоелектричної, електродинамічної та електромагнітної систем 229 KB
  Мета роботи: Вивчення будови принципу дії приладів магнітоелектричної електродинамічної та електромагнітної системи та методами їх використання. Завдання: Ознайомитись з призначенням та областю використання приладів магнітоелектричної електродинамічної та електромагнітної систем. Вивчити принцип дії приладів та методику їх використання. Ознайомитись із властивостями та технічними характеристиками приладів.