22885

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

Доклад

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

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

Украинкский

2013-08-04

71 KB

3 чел.

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

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

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

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

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

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


 

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

13386. ДИФФЕРЕНЦИАЛЬНАЯ ДИАГНОСТИКА И ЛЕЧЕНИЕ ПРИ СИНДРОМЕ АРТЕРИАЛЬНОЙ ГИПЕРТЕНЗИИ 168 KB
  Алгоритм дифференциальной диагностики заболеваний, сопровождающихся синдромом артериальной гипертензии. Этиологию, патогенез, клинику и диагностику заболеваний и состояний, сопровождающихся синдромом артериальной гипертензии.
13387. CORELDRAW. ПОСТРОЕНИЕ СЛОЖНЫХ ОБЪЕКТОВ 307.38 KB
  Лабораторная работа N 3 CORELDRAW. ПОСТРОЕНИЕ СЛОЖНЫХ ОБЪЕКТОВ Дополнительные приемы работы с объектами Программа CorelDraw предоставляет большие возможности по созданию и редактированию сложных объектов. Команды позволяющие выполнять различные операции над объектами с...
13388. CORELDRAW. ИНТЕРАКТИВНОЕ ПЕРЕТЕКАНИЕ. ИМИТАЦИЯ ОБЪЕМА 345.39 KB
  Лабораторная работа N 4 CORELDRAW. ИНТЕРАКТИВНОЕ ПЕРЕТЕКАНИЕ. ИМИТАЦИЯ ОБЪЕМА Эффект Интерактивное перетекание Инструмент Интерактивное перетекание относится к категории интерактивных инструментов находящихся на панели инструментов. При помощи данного инстр
13389. CORELDRAW. POWERCLIP. ОБРАБОТКА РАСТРОВЫХ ИЗОБРАЖЕНИЙ 267.4 KB
  Лабораторная работа N 5 CORELDRAW. POWERCLIP. ОБРАБОТКА РАСТРОВЫХ ИЗОБРАЖЕНИЙ Совокупность команд PowerClip Фигурная обрезка Команды находятся в меню Эффекты. Данное подменю содержит четыре команды: Place Inside Container Поместить в контейнер Extract Contents Извлечь содержимое Edit Contents Р...
13390. CORELDRAW. ИНТЕРАКТИВНЫЙ ОБЪЕМ 361.88 KB
  Лабораторная работа N 6 CORELDRAW. ИНТЕРАКТИВНЫЙ ОБЪЕМ Инструмент Интерактивный объем Данный инструмент позволяет создавать иллюзию объема для плоских объектов. Иллюзия возникает изза того что за объектом или перед ним достраивается дополнительная плоскость той же ...
13391. CORELDRAW. ИНТЕРАКТИВНОЕ ИСКАЖЕНИЕ. ИМИТАЦИЯ ОБЪЕМА 309.26 KB
  Лабораторная работа N 7 CORELDRAW. ИНТЕРАКТИВНОЕ ИСКАЖЕНИЕ. ИМИТАЦИЯ ОБЪЕМА Эффект Интерактивное искажение Инструмент Интерактивное искажение является инструментом категории интерактивных инструментов и предназначен для деформации формы объекта к которому он при
13392. CORELDRAW. ПРИМЕНЕНИЕ НАВЫКОВ 165.88 KB
  Лабораторная работа N 8 CORELDRAW. ПРИМЕНЕНИЕ НАВЫКОВ Порядок выполнения работы Выполнить построение изображения согласно индивидуальному заданию и предложенным рекомендациям. ВАРИАНТ 1. КОЛЛАЖ ТУПИК РЕКОМЕНДАЦИИ: Д
13393. Побудова плану котеджу 58 KB
  Лабораторна робота № 2 Тема: Побудова плану котеджу. Мета: закріпити практичні навички побудови плану методом напрямоквідстань та використання команд trim extend. Обладнання: ПК програмне забезпечення AutoCAD ...
13394. Створення шаблону в AutoCAD 12 83.5 KB
  Дисципліна ОКТБ ЛР № 9. Тема роботи: створення шаблону. Мета роботи: систематизувати теоретичні знання роботи з файлами повторити команди створення та редагування примітивів в програмі AutoCAD. Обладнання: ПК AutoCAD 12 Завдання для лабораторної роботи. Відкрит