МИНИСТЕРСТВО ОБРАЗОВАНИЯ РЕСПУБЛИКИ БЕЛАРУСЬ
Учреждение образования
«Гомельский государственный университет
имени Франциска Скорины »
Математический факультет
Кафедра алгебры и геометрии
Допущена к защите
Зав. кафедрой _________ Шеметков Л.А.
«_____» ____________ 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. преобразовывают некоторые конструктивные объекты. ............