рефераты конспекты курсовые дипломные лекции шпоры

Раздел Образование
/
Расширенный алгоритм Евклида.

Реферат Курсовая Конспект

Выберите учебное заведение

Расширенный алгоритм Евклида.

Расширенный алгоритм Евклида. - раздел Образование, Основы теории групп С Помощью Алгоритма Евклида, Вычисляя Нод...

С помощью алгоритма Евклида, вычисляя НОД, можно выяснить , обратимо ли число по модулю . Однако встает вопрос, как найти обратный к элемент. Так как алгоритм Евклида – это последовательное деление с остатком , , где , и НОД. Можно выразить все остатки от деления через и . Расширенный алгоритм Евклида позволяет найти НОДчерез сами эти числа.

Теперь найдем обратный элемент для по модулю . Применим сначала расширенный алгоритм Евклида к числам и и получим такие числа , и такие, что . Поэтому . Теперь видно, что уравнение имеет решение только тогда, когда . При этом решение имеет вид .

Пример. Найти обратный элемент к 7 по модулю 19.

Решение. Пусть , . Тогда , , или или . Отсюда .

Развернуть

Открыть в широком формате

– Конец работы –

Эта тема принадлежит разделу:

Основы теории групп

Некоторые общие понятия алгебры Определение Полугруппой называется множество в котором определено... Классы смежности...

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Расширенный алгоритм Евклида.

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Все темы данного раздела:

Некоторые общие понятия алгебры.
Определение. Полугруппой называется множество, в котором определено действие, ставящее в соответствие каждой упорядоченной паре элементов данного множества трет

Аксиомы группы.
Теорема 1. Если в полугруппе существует левый нейтральный элемент е такой, что при любом

Подгруппы
Определение. Подмножество элементов группы наз

Циклические группы.
Определение. Группа, составленная положительными и отрицательными степенями одного элемента , называетс

Арифметика остатков.
Зафиксируем некоторое натуральное число , которое назовем модулем. Если разность двух чисел

Функция Эйлера.
Одной из главных задач арифметики остатков является решение уравнения относительно

Мультипликативные обратные по модулю .
Решая уравнение вида , приходим к вопросу о существовании мультипликативного обратного

Алгоритм Евклида.
Рассмотрим алгоритм Евклида только для целых чисел. На многочлены алгоритм Евклида распространяется аналогичным образом, т. к. они, как и целые числа, обладают свойством евлидовости

Китайская теорема об остатках.
Китайская теорема об остатках (КТО) является очень древней находкой математики, которой около 2000 лет. КТО утверждает, что система уравнений

Конечные поля.
Множество остатков с операциями сложения и умножения является коммутативным кольцом, которое часто называется кольцом вычето

Нормальные подгруппы и факторгруппы.
Определение. Элемент группы называется сопряженным

Гомоморфизм.
Пусть - группа и - другая группа или полугруппа. Пусть каждому эле