22885

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

Доклад

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

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

Украинкский

2013-08-04

71 KB

3 чел.

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

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

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

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

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

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


 

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

49323. СИНТЕЗ СХЕМЫ ГЕНЕРАТОРА ЧИСЕЛ СО СТРУКТУРОЙ АВТОМАТА МУРА 6.4 MB
  Синтезировать схему генератора чисел 0-15-2-1-5-6-10-9 0-13-1-7-5-2-11-6-12 со структурой автомата Мура и Мили на RS и D триггерах в базисе ИЛИ-НЕ, определить схему с минимальным количеством входов, проверить правильность синтеза в MicroCap.
49324. ПРОЕКТИРОВАНИЕ И РЕАЛИЗАЦИЯ МОДУЛЯ ПРОХОЖДЕНИЯ ТЕСТИРОВАНИЯ СИСТЕМЫ ПРОВЕРКИ УЧАЩИХСЯ НА ЗНАНИЕ АЛГОРИТМОВ 1.58 MB
  Обзор систем тестирования Приложение Визуальная студия тестирования Система тестирования INDIGO
49325. Методы локализации неисправностей на аппаратуре СВ и РМ 1.63 MB
  После записи числа Х в ячейку памяти У при наличии свободных оперативных регистров контролируем содержимое ячейки ЗУ: на информационном поле оперативного пульта управления набираем адрес У; нажимаем клавиши НУ ЗАП ССП ПУСК; на поле индикации при переключателе режимов установленном на значении ОР число Х не отображается. Вычислительное устройство ВчУ является основным операционным устройством СВ предназначенным для обработки цифровой и логической информации реагирования на сигналы прерывания внешних устройств и управления...
49328. Возможности Hex-редакторов 843.76 KB
  Актуальность: в настоящее время hexредакторы используются в основном профессиональными программистами которые работают с языками низкого уровня. Hexредакторы вместе с дизассемблерами активно применяются хакерами для написания вирусов взлома программ и создания crck’ов. Понятие hexредактора Hexредактор англ.
49329. Цепи постоянного тока 136.43 KB
  Оглавление Цель курсовой работы Постановка задачи Расчет схемы Определение токов и напряжений в ветвях методом контурных токов Определение токов и напряжений в ветвях методом узловых потенциалов Баланс мощности Определение номинальных значений пассивных элементов цепи R LC Моделирование Список использованной литературы Целью курсовой работы является закрепление и...