Теория остатков

История арифметики остатков. Понятие остатка, наибольшего общего делителя, расширенного алгоритма Евклида и применение его для решения линейных диофантовых уравнений. Алгебраический подход к делимости в кольцах и разложение чисел в цепные дроби.
Краткое сожержание материала:

1

МИНИСТЕРСТВО ОБРАЗОВАНИЯ РЕСПУБЛИКИ БЕЛАРУСЬ

Учреждение образования

«Гомельский государственный университет

имени Франциска Скорины »

Математический факультет

Кафедра алгебры и геометрии

Допущена к защите

Зав. кафедрой _________ Шеметков Л.А.

«_____» ____________ 2006 г.

ТЕОРИЯ ОСТАТКОВ

ДИПЛОМНАЯ РАБОТА

Исполнитель:

студентка группы М-52 ____________ Клименко Ю.

Научный руководитель:

к.ф-м.н., доцент кафедры

алгебры и геометрии ____________ Подгорная В.

Рецензент:

ст. преподаватель

кафедры высшей

математики ____________ Курносенко Н.

Гомель 2008

Содержание

• Введение 3
• 1 Алгоритм Евклида 4
• 1.1 Определения алгоритма 4
• 1.2 Алгоритм Евклида 5
• 1.3 Применения алгоритма Евклида 12
• 2 Делимость в кольцах 17
• 2.1 Область целостности 17
• 2.2 Кольцо частных 19
• 2.3 Евклидовы кольца 21
• 3 Сравнения и арифметика остатков 27
• 4 Функция Эйлера 41
• 5 Китайская теорема об остатках 53
• Заключение 62
• Список использованных источников 63

Введение

История арифметики остатков начинается с исследований К.Ф. Гаусса, который впервые стал рассматривать сравнения. В дальнейшем была обнаружена связь теории сравнений с астрономическими задачами (китайская теорема об остатках). В результате многочисленных исследований теория остатков была распространена на кольца произвольной природы. В последнее время обнаружилось приложение этой теории в криптографии. В дипломной работе изложена теория остатков на современном алгебраическом языке.

Дипломная работа состоит из пяти разделов.

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

Во втором разделе изложен алгебраический подход к делимости в кольцах. Рассмотрена область целостности, кольцо частных и евклидовы кольца.

В третьем разделе изложены теории вычетов по модулю и теория сравнений. Приведено применении теории остатков в криптографии (алгоритм RSA).

В четвертом разделе изложена теория мультипликативных функция и подробно рассмотрена функция Эйлера, с её свойствами.

В пятом разделе изложена китайская теорема об остатках для колец.

1 Алгоритм Евклида

1.1 Определения алгоритма

Единого «истинного» определения понятия «алгоритм» нет.

«Алгоритм -- это всякая система вычислений, выполняемых по строго определённым правилам, которая после какого-либо числа шагов заведомо приводит к решению поставленной задачи.» (А. Колмогоров)

«Алгоритм -- это точное предписание, определяющее вычислительный процесс, идущий от варьируемых исходных данных к искомому результату.» (А. Марков)

«Алгоритм есть формализованная последовательность действий (событий). Алгоритм может быть записан словами и изображен схематически. Практически любое неслучайное повторяемое действие поддается описанию через алгоритм.»

«Алгоритм -- это система операторов, взятых из множества операторов некоторого исполнителя, которая полностью определяет некоторый класс алгоритмических процессов, то есть процессов, которые:

1. дискретны;

2. детерминированы;

3. потенциально конечны;

4. преобразовывают некоторые конструктивные объекты.

Между операторами алгоритма и операциями (элементарными действиями) алгоритмического процесса существует гомоморфное соответствие. Поэтому алгоритм следует также считать моделью алгоритмического процесса». (А. Копаев)

Формальные признаки алгоритмов

Различные определения алгоритма в явной или неявной форме содержат следующий ряд общих требований:

· детерминированность -- определённость. В каждый момент времени следующий шаг работы однозначно определяется состоянием системы. Таким образом, алгоритм выдаёт один и тот же результат (ответ) для одних и тех же исходных данных. В современной трактовке у разных реализаций одного и того же алгоритма должен быть изоморфный граф. С другой стороны, существуют вероятностные алгоритмы, в которых следующий шаг работы зависит от текущего состояния системы и генерируемого случайного числа.

· понятность -- алгоритм для исполнителя должен включать только те команды, которые ему (исполнителю) доступны, которые входят в его систему команд.

· завершаемость (конечность) -- при корректно заданных исходных данных алгоритм должен завершать работу и выдавать результат за конечное число шагов. С другой стороны, вероятностный алгоритм может и никогда не выдать результат, но вероятность этого равна 0.

· массовость -- алгоритм должен быть применим к разным наборам исходных данных.

Современное формальное определение алгоритма было дано в 30-50-х гг. XX века в работах Тьюринга, Поста, Чёрча (тезис Чёрча -- Тьюринга), Н. Винера, А. А. Маркова.

1.2 Алгоритм Евклида

Определение. Число d ??Z , делящее одновременно числа а , b , c , ... , k ??Z , называется общим делителем этих чисел. Наибольшее d с таким свойством называется наибольшим общим делителем. Обозначение: d = ( a , b , c , ..., k ) .

Теорема. Если ( a , b ) = d , то найдутся такие целые числа u и v , что d = au + bv .

Доказательство. Рассмотрим множество P = { au + bv ??u,v ??Z }. Очевидно, что P ??Z , а знатоки алгебры могут проверить, что P - идеал в Z . Очевидно, что a , b , 0 ??P . Пусть x , y ??P и y ??0 . Тогда остаток от деления x на y принадлежит P . Действительно:

x = yq + r , 0 ??r < y ,

r = x - yq = ( au ₁ + bv ₁ ) - ( au ₂ + bv ₂ ) q = a ( u ₁ - u ₂ q )+ b ( v ₁ - v ₂ q ) ??P .

Пусть d ??P - наименьшее положительное число из P (призадумайтесь, почему такое имеется!). Тогда а делится на d . В самом деле, a = dq + r ₁ , 0 ??r ₁ < d , a ??P , d ??P , значит r ₁ ??P , следовательно r ₁ = 0. Аналогичными рассуждениями получается, что b делится на d , значит d - общий делитель a и b .

Далее, раз d ??P , то d = au ₀ + bv ₀ . Если теперь d ₁ - общий делитель a и b , то d ₁ | ( au ₀ + bv ₀ ), т.е. d ₁ | d . Значит d ??d ₁ и d - наибольший общий делитель.

Определение. Целые числа a и b называются взаимно простыми, если (a , b ) = 1.

Вспоминая свойство 1 из предыдущего пункта, легко заметить, что два числа a и b являются взаимно простыми тогда и только тогда, когда найдутся целые числа u и v такие, что au + bv = 1.

Пусть даны два числа a и b ; a ??0, b ??0, считаем, что a > b . Символом := в записи алгоритма обозначаем присваивание. Алгоритм:

1. Ввести a и b .

2. Если b = 0 , то Ответ: а . Конец .

a = bq 1 + r 1 b = r 1 q 2 + r 2 r 1 = r 2 q 3 + r 3 r 2 = r 3 q 4 + r 4	0 ??r 1 < b 0 ??r 2 < r 1 0 ??r 3 < r 2 0 ??r 4 < r 3
· · · · · · · · ·
r n -3 = r n -2 q n -1 + r n -1 r n -2 = r n -1 q n + r n Другие файлы: Методы решения уравнений линейной регрессии Определение параметров уравнения линейной регрессии. Экономическая интерпретация коэффициента регрессии. Вычисление остатков, расчет остаточной суммы... Теории денег Теория денег как одна из самых политически острых областей экономической науки. Дифференциация позитивистского мировоззрения. Общие проблемы эволюции... Теория остатков История арифметики остатков начинается с исследований К.Ф. Гаусса, который впервые стал рассматривать сравнения. В дальнейшем была обнаружена связь те... Разложение растительных остатков в почве Сборник включает статьи специалистов разного профиля (геоботаников» зоологов, микробиологов, биохимиков), отражающие основные аспекты и методы изучени... Модели множественной линейной регрессии Определение наличия зависимости показателя Заработная плата от Возраста и Стажа с использованием корреляционной матрицы. Нормальность распределения ос...