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

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

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

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

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

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

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

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

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

«_____» ____________ 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 , делящее одновременно числа а , , c , ... , k Z , называется общим делителем этих чисел. Наибольшее d с таким свойством называется наибольшим общим делителем. Обозначение: d = ( a , , c , ..., k ) .

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

Доказательство. Рассмотрим множество P = { au + bv u,v Z }. Очевидно, что P Z , а знатоки алгебры могут проверить, что P – идеал в Z . Очевидно, что a , , 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 )+ ( v ₁ – v ₂ q ) P .

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

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

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

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

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

1. Ввести a и .

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

3. Заменить r := "остаток от деления а на ", а := , := r .

4. Идти на 2.

В современной буквенной записи, алгоритм Евклида выглядит так: a > b; a, b Z .

Имеем: > r ₁ > r ₂ >... > r _n > 0, следовательно процесс оборвется максимум через шагов. Очень интересный и практически важный народохозяйственный вопрос о том, когда алгоритм Евклида работает особенно долго, а когда справляется с работой молниеносно, мы рассмотрим чуть позже. Давайте сейчас покажем, что r _n = ( a , ). Просмотрим последовательно равенства сверху вниз: всякий делитель а и делит r ₁ , r ₂ ,..., r _n . Если же просматривать эту цепочку равенств от последнего к первому, то видно, что r _n | r _{n -1} , r _n | r _{n -2} , и т.д., т.е. r _n делит а и . Поэтому r _n - наибольший общий делитель чисел а и .

Как и всякая добротно выполненная работа, алгоритм Евклида дает гораздо больше, чем от него первоначально ожидалось получить. Из его разглядывания ясно, например, что совокупность делителей а и совпадает с совокупностью делителей ( a , ). Еще он дает практический способ нахождения чисел u и v из Z (или, если угодно, из теоремы пункта 2) таких, что r _n = au + bv = ( a, b ).

Действительно, из цепочки равенств имеем:

r _n = r _{n -2} - r _{n -1} q _n = r _{n -2} - ( r _{n -3} - r _{n -2} q _{n -1} ) q _n = ...

(идем по цепочке равенств снизу вверх, выражая из каждого следующего равенства остаток и подставляя его в получившееся уже к этому моменту выражение)

... = au + bv = ( a , ).

Пример. Пусть а = 525, = 231. (ниже приводится запись деления уголком, и каждый раз то, что было в уголке, т.е. делитель, приписывается к остатку от деления с левой стороны, а остаток, как новый делитель, берется в уголок)

Запись того же самого в виде цепочки равенств:

525 = 231 · 2 + 63

231 = 63 · 3 + 42

63 = 42 · 1 + 21

42 = 21 · 2

Таким образом, (525, 231) = 21. Линейное представление наибольшего общего делителя:

21 = 63 - 42 · 1 = 63 - (231 - 63 · 3) · 1 =

= 525 - 231 · 2 - (231 - (525 - 231 · 2) · 3) =

= 525 · 4 - 231 · 9,

и наши пресловутые u и v из Z равны, соответственно, 4 и - 9.

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

Теорема (Ламэ, 1845 г.). Пусть n N , и пусть a > b > 0 такие, что алгоритму Евклида для обработки а и b необходимо выполнить точно n шагов (делений с остатком), причем а - наименьшее с таким свойством. Тогда а = _{n +2} , b = _{n +1} , где _k - k- ое число Фибоначчи.

Следствие. Если натуральные числа a и не превосходят N N , то число шагов (операций деления с остатком), необходимых алгоритму Евклида для обработки a и не превышает log _Ф ( 5 N ) - 2, где - верхнее целое , = (1 + 5)/2 - больший корень характеристического уравнения последовательности Фибоначчи.

Доказательство. Максимальное число шагов достигается при а = _n+2 , = _{n +1} , где - наибольший номер такой, что _{n +2} < N . Рассматривая формулу для -ого члена последовательности Фибоначчи, легко понять, что _{n +2} - ближайшее целое к (1/ 5) ^{n +2} . Значит (1/ 5) ^{n +2} < N , следовательно, +2 < log _Ф ( 5 N ), откуда моментально даже < log _Ф ( 5 N ) - 3 (именно "минус три", ведь рассматривается верхнее целое).

log _Ф ( 5 N ) 4,785 · lg N + 1,672, поэтому, например, с любой парой чисел, меньших миллиона, алгоритм Евклида разбирается не более, чем за 4,785 · 6 + 1,672 - 3 = 31 - 3 = 28 шагов.

Листинг алгоритма Евклида на языке С

// Обобщенный алгоритм Евклида для поиска наибольшего общего

// делителя gcd = НОД(u,v) целых положительных чисел u и v

// и коэффициентов a и b уравнения a*u + b*v = gcd

// Все числа полагаются типа long

// Подстановки упрощающие запись исходного текста

#define isEven(x) ((x & 0x01L) == 0)                 // x - четное?

#define isOdd(x) ((x & 0x01L))                           // x - нечетное?

#define swap(x,y) (x ^= y, y ^= x, x ^= y) // обмен значений x и y

void GenEuclid(long *u, long *v, long *a, long *b, long *gcd)

{

int k;       // Параметр циклов

long a1, b1, g1;   // Вспомогательные переменные

// Алгоритм предполагает, что u > v, если u < v, то они переставляются

if (*u < *v) swap(*u, *v);

// Если u = n * 2^k1 или v = m * 2^k2, то перед поиском НОД

// производим сокращение u = u/(2^k), v = v/(2^k),

// где k - минимальное из k1, k2. Показатель k запоминаем.

for (k = 0; isEven(*u) && isEven(*v); ++k){

   *u >>= 1; *v >>= 1;

}

// Задание начальных значений

*a = 1; *b = 0; *gcd = *u; a1 = *v; b1 = *u - 1; g1 = *v;

do {

   do {

               if (isEven(*gcd)){

                           if (isOdd(*a) || isOdd(*b)){

                                       *a += *v; *b += *u;

                           }

                           *a >>= 1; *b >>= 1; *gcd >>= 1;

               }

               if (isEven(g1) || *gcd < g1){

                           swap(*a, a1); swap(*b, b1); swap(*gcd, g1);

               }

   } while (isEven(*gcd));

   while(*a < a1 || *b < b1){

               *a += *v; *b += *u;

   }

   *a -= a1; *b -= b1; *gcd -= g1;

} while (g1 > 0);

while (*a >= *v && *b >= *u){

   *a -= *v; *b -= *u;

}

// производим умножение коэффициентов уравнения

// на сокращенный ранее множитель 2^k

*a <<= k; *b <<= k; *gcd <<= k;

}

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

Формулы для r_i могут быть переписаны следующим образом:

r₁ = a + ( - q₀)

r₂ = − r₁q₁ = a( − q₁) + (1 + q₁q₀)

(a,) = r_n = as + bt

здесь и t целые. Это представление наибольшего общего делителя называется соотношением Безу, а числа и t — коэффициентами Безу. Соотношение Безу является ключевым в доказательстве основной теоремы арифметики.

1.3 Применения алгоритма Евклида

Пусть требуется решить линейное диофантово уравнение:

ax + by = c ,

где a , , c Z ; a и - не нули.

Попробуем порассуждать, глядя на это уравнение.

Пусть ( a , ) = d . Тогда a = a ₁ d ; = ₁ d и уравнение выглядит так:

a ₁ d· x + ₁ d· y = c , т.е. d· ( a ₁ x + ₁ y ) = c .

Теперь ясно, что у такого уравнения имеется решение (пара целых чисел x и y ) только тогда, когда d | c . Пусть d | c . Поделим обе части уравнения на d , и всюду далее будем считать, что ( a , ) = 1.

Рассмотрим несколько случаев.

Случай 1. Пусть c = 0, уравнение имеет вид ax + by = 0 - " однородное линейное диофантово уравнение".