22885

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

Доклад

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

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

Украинкский

2013-08-04

71 KB

3 чел.

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

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

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

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

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

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


 

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

11434. Исследование методики перехода от графической формы записи математических моделей к матрично-векторной 113.45 KB
  Лабораторная работа №1 Исследование методики перехода от графической формы записи математических моделей к матричновекторной Цель работы: освоение методики преобразования ММ ОУ из графической формы описания структурная схема в матричновект...
11435. Порядок установления важнейших показателей качества упаковки 71.5 KB
  ЛАБОРАТОРНАЯ РАБОТА №2 Порядок установления важнейших показателей качества упаковки 1. Цель работы: Ознакомиться с порядком определения оценки и анализа уровня качества упаковки. 2. Задание: для конкретного вида упаковки1 установить основную номенклатуру показ...
11436. Инвестиции в основной капитал и во внеоборотные активы 113.5 KB
  Экономическое содержание вложений во внеоборотные активы. Амортизация и ее роль в воспроизводственном процессе. Источники финансирования прямых инвестиций. Нематериальные активы, источники формирования, способы начисления амортизации.
11437. РЕАКЦИИ ОКИСЛЕНИЯ - ВОССТАНОВЛЕНИЯ 97.5 KB
  ЛАБОРАТОРНАЯ РАБОТА №8. РЕАКЦИИ ОКИСЛЕНИЯ ВОССТАНОВЛЕНИЯ Введение. Реакции связанные с изменением степени окисления атомов в молекулах реагирующих веществ называются окислительновосстановительными. Степень окисления условный электрический з
11438. ЭЛЕКТРОХИМИЧЕСКИЕ ПРОЦЕССЫ 108.5 KB
  ЛАБОРАТОРНАЯ РАБОТА №9 ЭЛЕКТРОХИМИЧЕСКИЕ ПРОЦЕССЫ Основные понятия Характерной особенностью окислительновосстановительных реакций является возможность пространственного разделения процессов окисления и восстановления т.е. проведения их на отдельных электр
11439. Знакомство с процессором командного языка ОС семейства Windows 106.5 KB
  Лабораторная работа № 1 : Знакомство с процессором командного языка ОС семейства Windows. Для того чтобы сдать лабораторную работу все примеры приводимые в теоретическом материале должны быть представлены преподавателю в виде созданных студентом bat файлов. Вопросы: ...
11440. Командная консоль ОС семейства Windows 102 KB
  Лабораторная работа № 1 Командная консоль ОС семейства Windows Задания. Традиционно все имена идентификаторы объектов лабораторной работы должны содержать суффикс FIO например именование файла My_File_LAS.odt если ФИО студента Луканов Алесандр Сергеевич. Оз...
11441. Форматирования текста 72 KB
  Лабораторная работа № 3 1.Форматирования текста Примеры форматирования текста приведены в файлах form_str.py и form_operat.py. 1Форматирование данных строкового типа производиться методами / функциями соответствующего модуля. Полное описание модуля можно вызвать командой ...
11442. Архитектура персонального компьютера. Классификация программного обеспечения 81.5 KB
  Лабораторная работа № 1 Тема: Архитектура персонального компьютера. Классификация программного обеспечения. Цель работы: изучить устройство персонального компьютера приобрести навыки в исследовании и описании аппаратного и программного обеспечения ЭВМ; изучить