Дипломная работа: Теория остатков

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

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

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

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

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

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

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

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

«_____» ____________ 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 , то Ответ: а . Конец .

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

4. Идти на 2.

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

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

Как и всякая добротно выполненная работа, алгоритм Евклида дает гораздо больше, чем от него первоначально ожидалось получить. Из его разглядывания ясно, например, что совокупность делителей а и b совпадает с совокупностью делителей ( a , b ). Еще он дает практический способ нахождения чисел 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 , b ).

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

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

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

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

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

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

r ₁ = a + b ( - q ₀ )

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

(a ,b ) = r_n = as + bt

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

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

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

ax + by = c ,

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

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

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

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

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

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

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

Так как x должен быть целым числом, то y = at , где t - произвольное целое число (параметр). Значит x = - bt и решениями однородного диофантова уравнения ax + by = 0 являются все пары вида {- bt , at }, где t = 0; ±1; ±2;... Множество всех таких пар называется общим решением линейного однородного диофантова уравнения, любая же конкретная пара из этого множества называется частным решением.

Случай 2. Пусть теперь c  0. Этот случай закрывается следующей теоремой.

Теорема. Пусть ( a , b ) = 1, { x ₀ , y ₀ } - частное решение диофантова уравнения ax + by = c . Тогда его общее решение задается формулами:

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

Доказательство. То, что правые части указанных в формулировке теоремы равенств действительно являются решениями, проверяется их непосредственной подстановкой в исходное уравнение. Покажем, что любое решение уравнения ax + by = c имеет именно такой вид, какой указан в формулировке теоремы. Пусть { x * , y *} - какое-нибудь решение уравнения ax + by = c . Тогда ax * + by * = c , но ведь и ax ₀ + by ₀ = c . Следуя многолетней традиции доказательства подобных теорем, вычтем из первого равенства второе и получим:

a ( x *- x ₀ ) + b ( y *- y ₀ ) = 0

- однородное уравнение. Далее, глядя на случай 1, рассмотрение которого завершилось несколькими строками выше, пишем сразу общее решение: x *- x ₀ = - bt , y *- y ₀ = at , откуда моментально, используя навыки третьего класса средней школы, получаем:



Как же искать то самое частное решение { x ₀ , y ₀ }. Мы договорились, что ( a , b ) = 1. Это означает, что найдутся такие u и v из Z , что au + bv = 1, причем эти u и v мы легко умеем находить с помощью алгоритма Евклида. Умножим теперь равенство au + bv = 1 на c и получим: a ( uc ) + b ( vc ) = c , т.е. x ₀ = uc , y ₀ = vc .

Определение. Цепной (или, непрерывной) дробью называется выражение вида:

(Бедные наборщики в докомпьютерные времена буквально стрелялись, когда им приходилось набирать в книжках подобные многоэтажные выражения.) Договоримся называть числа q ₁ , q ₂ ,..., q _n ,... - неполными частными и считаем, что q ₁ Z , а q ₂ ,..., q _n ,... N . Числа называются подходящими дробями цепной дроби .

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

Пусть Q , = a / b ; a , b Z , b > 0. Оказывается, что при этих условиях, указанный выше процесс разложения числа в цепную дробь всегда конечен и выполним с помощью достопочтенного и любимого нами алгоритма Евклида. Действительно, отдадим алгоритму числа a и b , и внимательно посмотрим, что получится.

Значит:

где q ₁ , q ₂ ,..., q _{n +1} - как раз те самые неполные частные из алгоритма Евклида (вот откуда название этих чисел в цепных дробях). Таким образом, в случае рационального числа a / b , процесс разложения в цепную дробь конечен и дробь содержит не более b этажей. Наиболее одаренные читатели в этом месте уже поняли, что основная теорема о цепных дробях для рациональных чисел оказалась почти доказана (не доказали только единственность разложения, но она в случае конечных цепных дробей почти очевидна - приравняйте две цепных дроби и, рассуждая по индукции, получите, что у равных дробей совпадают все неполные частные).

Пример. П ример заимствован из книги И. М. Виноградова "Основы теории чисел". Итак: разложить 105/38 в цепную дробь.

Включаем алгоритм Евклида:

105 = 38 · 2 + 29

38 = 29 · 1 + 9

29 = 9 · 3 + 2

9 = 2 · 4 + 1

2 = 1 · 2

Неполные частные я специально подчеркнул потому, что теперь для написания ответа нужно аккуратно расположить их подряд на этажах цепной дроби перед знаками плюс:

2 Делимость в кольцах

2.1 Область целостности

Область целостности (или целостное кольцо , или область цельности ) — понятие абстрактной алгебры: ассоциативное коммутативное кольцо с единицей, в котором 0≠1 и произведение двух ненулевых элементов не равно нулю. Условие 0≠1 исключает из рассмотрения тривиальное кольцо {0}.

Эквивалентное определение: область целостности — это ассоциативное коммутативное кольцо, в котором нулевой идеал {0} является простым. Любая область целостности является подкольцом своего поля частных.

Примеры

· Простейший пример области целостности — кольцо целых чисел .

· Любое поле является областью целостности. С другой стороны, любая артинова область целостности есть поле. В частности, все конечные области целостности суть конечные поля.

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

· Множество действительных чисел вида есть подкольцо поля , а значит, и область целостности. То же самое можно сказать про множество комплексных чисел вида a + bi , где a и b целые (множество Гауссовых целых).

· Пусть U — связное открытое подмножество комплексной плоскости . Тогда кольцо H (U ) всех голоморфных функций будет целостным. То же самое верно для любого кольца аналитических функций, определённых на связном подмножестве аналитического многообразия.

· Если K — коммутативное кольцо, а I — идеал в K , то факторкольцо K / I целостное тогда и только тогда, когда I — простой идеал.

Делимость, простые и неприводимые элементы

Пусть a и b — элементы целостного кольца K . Говорят, что «a делит b » или «a — делитель b » (и пишут ), если и только если существует элемент такой, что ax = b .

Делимость транзитивна: если a делит b и b делит c , то a делит c . Если a делит b и c , то a делит также их сумму b + c и разность b - c .

Для кольца K с единицей элементы , которые делят 1, называются делителями единицы , а иногда и просто единицами . Они и только они, обратимы в K . Единицы делят все остальные элементы кольца.

Элементы a и b называются ассоциированными , если a делит b и b делит a. a и b ассоциированны тогда и только тогда, когда a = b * e , где e — обратимый элемент.

Необратимый элемент q целостного кольца называется неприводимым , если его нельзя разложить в произведение двух необратимых элементов.

Ненулевой необратимый элемент p называется простым , если из того, что , следует или . Это определение обобщает понятие простого числа в кольце , однако учитывает и отрицательные простые числа. Если p — простой элемент кольца, то порождаемый им главный идеал (p ) будет простым. Любой простой элемент неприводим, но обратное верно не во всех областях целостности.

Свойства

· Любое поле, а также любое кольцо с единицей, содержащееся в некотором поле, является областью целостности.

Обратно, любая область целостности может быть вложена в некоторое поле. Такое вложение дает конструкция поля частных.

· Если A ― область целостности, то кольцо многочленов и кольцо формальных степенных рядов над A также будут областями целостности.

· Если A ― коммутативное кольцо с единицей и I ― некоторый идеал в A , то кольцо A / I является областью целостности тогда и только тогда, когда идеал I прост.

· Кольцо будет областью целостности тогда и только тогда, когда его спектр есть неприводимое топологическое пространство.

· Прямое произведение колец никогда не бывает областью целостности, так как единица первого кольца, умноженная на единицу второго кольца, даст 0.

· Тензорное произведение целостных колец тоже будет целостным кольцом.

Вариации и обобщения

Иногда в определении области целостности не требуют коммутативности. Примерами некоммутативных областей целостности являются тела, а также подкольца тел, содержащие единицу, например целые кватернионы. Однако, вообще говоря, неверно, что любая некоммутативная область целостности может быть вложена в некоторое тело.

2.2 Кольцо частных

В коммутативной алгебре кольцом частных S^-1 R кольца R (коммутативного с единицей) по мультипликативной системе называется пространство дробей с числителями из R и знаменателями из S с арифметическими операциями и отождествлениями, обычными для дробей.

Мультипликативной системой в кольце R называется подмножество S в R , содержащее 1, не содержащее нуля и замкнутое по умножению (в кольце R ). Для мультипликативной системы S множество образует идеал в кольце R . В случае, когда множество S не содержит делителей нуля кольца R , идеал I_S = (0) и система S называется регулярной. Если R - целостное кольцо, в ней всякая мультипликативная система регулярна.

Элементами кольца частных кольца R по мультипликативной системе S являются формальные дроби вида r/s , где r - произвольный элемент R , а s - элемент множества S . Две дроби r ₁ / s ₁ и r ₂ / s ₂ считаются эквивалентными (представляют один и тот же элемент кольца частных), если . Операции сложения и умножения определяются как обычно:

Проверяется, что если в сумме или произведении дроби заменить на эвивалентные, новый результат будет выражаться дробью, эквивалентной прежней. С такими операциями множество S ^{− 1} R приобретает структуру коммутативного кольца с единицей. Нулём в нём служит дробь 0/1 , единицей - дробь 1/1 .

Свойства

· Кольцо частных имеет каноническую структуру алгебры над кольцом R, так как вместе с кольцом S^-1 R сразу определён и канонический гомоморфизм кольца R в S^-1 R (каждому элементу r из R соответствует дробь r/1 ). Ядром этого гомоморфизма является идеал I_S . В случае, если система S регулярна (не содержит делителей нуля), этот гомоморфизм инъективен, и кольцо R , таким образом, вложено в своё кольцо частных по системе S . При этом дробь r/s является единственным решением уравнения sx = r .

· Если оба элемента r и s принадлежат S , тогда в кольце S^-1 R содержатся дроби r/s и s/r . Их произведение равно 1, следовательно, они обратимы. Обратно: каждый обратимый элемент кольца S^-1 R имеет вид er/s , где r и s принадлежат S, а e - обратимый элемент кольца R .

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

· Если R - евклидово кольцо, то всякое кольцо, промежуточное между R и его полем частных, является кольцом частных кольца R по некоторой мультипликативной системе S .

· Если система S состоит из одних только обратимых элементов кольца R , канонический гомоморфизм кольца R в S^-1 R превращается в изоморфизм, так как каждая дробь r/s оказывается сократимой в кольце R .

· Если кольцо R ' является подкольцом кольца R , то множество всех элементов из R ', обратимых в кольце R , образует регулярную мультипликативную систему S в кольце R' . Тогда каждой дроби r/s однозначно соответствует некоторый элемент кольца R . Множество всех таких элементов кольца R образует кольцо частных кольца R' в кольце R .

Примеры

· Полем частных кольца целых чисел является поле рациональных чисел .

· Степени числа 10 в образуют мультипликативную систему. Кольцом частных по ней будет кольцо конечных десятичных дробей.

· Полем частных кольца многочленов k [X ₁ ,X ₂ ,...,X_n ] над полем k будет поле рациональных функций k (X ₁ ,X ₂ ,...,X_n ).

· Пусть — простой идеал в R . Тогда дополнение к нему - мультипликативная система. Кольцо частных по ней называется локализацией кольца R по простому идеалу .

· Чётные числа в образуют простой идеал. Локализацией кольца по нему будет кольцо рациональных дробей, у которых в несократимом виде знаменатель — нечётное число.

2.3 Евклидовы кольца

Неформально, евклидово кольцо — в абстрактной алгебре — кольцо, в котором «работает» алгоритм Евклида.

Евклидово кольцо — это область целостности R , для которой определена евклидова функция (евклидова норма ) , причём , и возможно деление с остатком, по норме меньшим делителя, то есть для любых имеется представление a = bq + r , для которого d (r ) < d (b ).

Замечание

Часто на евклидову норму накладывают дополнительное ограничение: для любых a и ненулевых b из кольца R . Если на R задана норма, не удовлетворяющая этому условию, её можно поправить, переопределив:

Такая норма нужному неравенству удовлетворяет, однако прежний алгоритм деления с остатком уже не годится — его тоже надо поправлять. Пусть таков, что d '(b ) = d (bx ). Разделим с остатком ax на bx : ax = bxq ' + r 'x , где r ' = a − bq ' и d (r 'x ) < d (bx ) = d '(b ). Так как из определения , мы получили представление a = bq ' + r ' с d '(r ') < d '(b ), что и требовалось.

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

Примеры

· Кольцо целых чисел Z . Пример евклидовой функции — абсолютное значение .

· Кольцо целых гауссовых чисел Z [i] (где i — мнимая единица, i ² = − 1) с нормой d (a + ib ) = a ² + b ² — евклидово.

· Произвольное поле K является евклидовым кольцом с нормой, равной 1 для всех элементов, кроме 0.

· Кольцо многочленов в одной переменной K [x ] над полем K . Пример евклидовой функции — степень deg.

· Кольцо формальных степенных рядов K [[x ]] над полем K является евклидовым кольцом. Норма степенного ряда — номер первого ненулевого коэффициента в нём (для нулевого ряда норма равна минус бесконечности).

· Обобщая предыдущий пример, всякое локальное кольцо является евклидовым, если в нём максимальный идеал является главным и пересечение всех его степеней состоит только из нуля. Норма обратимого элемента — 0, необратимого ненулевого — равна максимальной степени максимального идеала, которая содержит данный элемент, а норма нуля — минус бесконечность.

· Кольцо функций H(K) , голоморфных на связном компакте K в C (каждая из них должна быть голоморфна в какой-нибудь окрестности этого компакта; две такие функции считаются равными в H(K) , если они совпадают в некоторой окрестности K ), тоже евклидово. За норму ненулевой функции принимается число нулей (с учётом кратности), которые она принимает на K .

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

· Кольцо частных S^-1 R евклидова кольца R по мультипликативной системе S тоже является евклидовым. Нормой дроби x из S^-1 R принимается

, где d_R — евклидова норма в R , а d_S — норма в S^-1 R .

Деление с остатком определяется так. Пусть есть две ненулевые дроби x = r / t и y из S^-1 R . По определению нормы в S^-1 R существует элементы u в R и s в S , такие что y = u / s и d_S (y ) = d_R (u ). Произведём деление с остатком в кольце R элементов rs и u :

rs = uq + r' , так что d_R (r ') < d_R (u ). Тогда r / t = (u / s )(q / t ) + r ' / ts . Из построения следуют неравенства .

· Евклидовыми являются кольца конечных двоичных и конечных десятичных дробей, так как они являются кольцами частных кольца целых чисел Z .

· Евклидовыми являются кольца рациональных функций над полем C с фиксированными полюсами, так как такие кольца являются кольцами частных кольца многочленов C [x ].

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

В евклидовом кольце осуществим алгоритм Евклида нахождения наибольшего общего делителя двух чисел (элементов). Пусть изначально даны два элемента a₀ и a₁ , причём и . Деление с остатком даёт элемент a ₂ = a ₀ − a ₁ q ₁ с d (a ₂ ) < d (a ₁ ). Если он не равен нулю, можно опять применить деление с остатком, и получить элемент a ₃ = a ₁ − a ₂ q ₂ , и т. д. Таким образом генерируется цепочка значений с . Однако эта цепочка прерывается, поскольку всякое число из может строго превосходить лишь конечное количество других таких чисел. Это означает, что при некотором n остаток a_n+1 равен нулю, а a_n не равен, он и есть НОД элементов a₀ и a₁ . Следовательно, в евклидовом кольце гарантировано завершение алгоритма Евклида. Строго говоря, именно в евклидовых кольцах и возможна реализация алгоритма Евклида.

Свойства евклидовых колец

· В евклидовом кольце каждый идеал — главный (в частности, все евклидовы кольца нётеровы).

o Пусть I — произвольный идеал в евклидовом кольце. Если он содержит лишь 0, — он главный. В противном случае среди его ненулевых элементов найдётся элемент f с минимальной нормой (принцип минимума для натуральных чисел). Он делит все остальные элементы идеала: Если g — произвольный элемент идеала I , представим его в виде g = fq + r с d(r)<d(f) . Тогда r - тоже элемент идеала I и он обязан быть нулём, так как его норма меньше, чем у f . Следовательно, идеал I содержится в идеале (f) . С другой стороны, всякий идеал, содержащий элемент f , содержит идеал (f) . Значит, I = (f) - главный идеал.

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

· Каждое евклидово кольцо R целозамкнуто, то есть если дробь , является корнем многочлена со старшим коэффициентом, равным 1, тогда a делится на b . Целозамкнутость - общее свойство всех факториальных колец.

Свойства модулей над евклидовым кольцом

Пусть R - евклидово кольцо. Тогда конечнопорождённые R -модули обладают следующими свойствами:

· Всякий подмодуль N конечнопорождённого R -модуля M конечно порождён. (следствие нётеровости кольца R )

· Ранг подмодуля N не превосходит ранга модуля M . (следствие главности идеалов в R )

· Подмодуль свободного R -модуля свободен. (то же)

· Гомоморфизм конечнопорождённых R -модулей всегда приводится к нормальной форме. То есть существуют образующие (базис, если модуль свободен) модуля N , образующие (базис) модуля M , номер и - элементы кольца R , такие что a_i делит a_{i + 1} и при i>k Au_i = 0, а при остальных — Au_i = a_i v_i . При этом коэффициенты определены однозначно с точностью до умножения на обратимые элементы кольца R . (Тут прямо задействована евклидовость кольца R .)

3 Сравнения и арифметика остатков

Определение. Пусть а, b Z , m N . Говорят, что число а сравнимо с b по модулю m , если а и b при делении на m дают одинаковые остатки. Запись этого факта выглядит так:

a b(mod m) .

Очевидно, что бинарное отношение сравнимости _m (неважно, по какому модулю) есть отношение эквивалентности на множестве целых чисел, а любители алгебры скажут, что это отношение является даже конгруэнцией кольца Z , фактор-кольцо по которой Z/ _m называется кольцом вычетов и обозначается Z _m .

Ясно, что число a сравнимо с b по модулю m тогда и только тогда, когда a-b делится на m нацело. Очевидно, это, в свою очередь, бывает тогда и только тогда, когда найдется такое целое число t , что a=b+mt . Знатоки алгебры добавят к этим эквивалентным утверждениям, что сравнимость a с b по модулю m означает, что a и b представляют один и тот же элемент в кольце Z _m .

Свойство 1. Сравнения по одинаковому модулю можно почленно складывать.

Доказательство. Пусть a₁ b₁ (mod m) , a₂ b₂ (mod m) . Это означает, что a ₁ =b ₁ +mt ₁ , a ₂ =b ₂ +mt ₂ . После сложения последних двух равенств получим a ₁ +a ₂ =b ₁ +b ₂ +m(t ₁ +t ₂ ) , что означает a ₁ +a ₂ b ₁ +b ₂ (mod m) .

Свойство 2. Слагаемое, стоящее в какой-либо части сравнения, можно переносить в другую часть, изменив его знак на обратный.

Доказательство.

Свойство 3. К любой части сравнения можно прибавить любое число, кратное модулю.

Доказательство.



Свойство 4. Сравнения по одинаковому модулю можно почленно перемножать и, следовательно,

Свойство 5. Обе части сравнения можно возвести в одну и ту же степень.

Доказательство.



Как следствие из вышеперечисленных свойств, получаем

Свойство 6. Если

a ₀  b ₀ (mod m) , a ₁  b ₁ (mod m) ,..., a _n  b _n (mod m) , x  y(mod m) ,

то a ₀ x ⁿ +a ₁ x ^n-1 +...+a _n  b ₀ y ⁿ +b ₁ y ^n-1 +...+b _n (mod m)

Свойство 7. Обе части сравнения можно разделить на их общий делитель, взаимно простой с модулем.

Доказательство. Пусть a b(mod m) , a=a ₁ d , b=b ₁ d . Тогда (a ₁ -b ₁ ) d делится на m . Поскольку d и m взаимно просты, то на m делится именно (a ₁ -b ₁ ) , что означает a ₁ b ₁ (mod m) .



Свойство 8. Обе части сравнения и его модуль можно умножить на одно и то же целое число или разделить на их общий делитель.

Доказательство.

a b(mod m) a=b+mt ak=bk+mkt ak bk(mod mk) .



Свойство 9. Если сравнение a b имеет место по нескольким разным модулям, то оно имеет место и по модулю, равному наименьшему общему кратному этих модулей.

Доказательство. Если a b(mod m ₁ ) и a b(mod m ₂ ) , то a-b делится на m ₁ и на m ₂ , значит a-b делится на наименьшее общее кратное m ₁ и m ₂ .

Свойство 10. Если сравнение имеет место по модулю m , то оно имеет место и по модулю d , равному любому делителю числа m .

Доказательство очевидно следует из транзитивности отношения делимости: если a b(mod m) , то a-b делится на m , значит a-b делится на d , где d|m .



Свойство 11. Если одна часть сравнения и модуль делятся на некоторое число, то и другая часть сравнения должна делиться на то же число.

Доказательство.

a  b(mod m)  a=b+mt .



Отношение _m сравнимости по произвольному модулю m есть отношение эквивалентности на множестве целых чисел. Это отношение эквивалентности индуцирует разбиение множества целых чисел на классы эквивалентных между собой элементов, т.е. в один класс объединяются числа, дающие при делении на m одинаковые остатки. Число классов эквивалентности _m (знатоки скажут - "индекс эквивалентности _m ") в точности равно m .

Определение. Любое число из класса эквивалентности _m будем называть вычетом по модулю m . Совокупность вычетов, взятых по одному из каждого класса эквивалентности _m , называется полной системой вычетов по модулю m (в полной системе вычетов, таким образом, всего m штук чисел). Непосредственно сами остатки при делении на m называются наименьшими неотрицательными вычетами и, конечно, образуют полную систему вычетов по модулю m . Вычет называется абсолютно наименьшим, если наименьший среди модулей вычетов данного класса.

Пример : Пусть m = 5 . Тогда:

0, 1, 2, 3, 4 - наименьшие неотрицательные вычеты;

-2, -1, 0, 1, 2 - абсолютно наименьшие вычеты.

Обе приведенные совокупности чисел образуют полные системы вычетов по модулю 5 .

Лемма 1. 1) Любые m штук попарно не сравнимых по модулю m чисел образуют полную систему вычетов по модулю m .

2) Если а и m взаимно просты, а x пробегает полную систему вычетов по модулю m , то значения линейной формы аx+b , где b - любое целое число, тоже пробегают полную систему вычетов по модулю m .

Доказательство. Утверждение 1) – очевидно. Докажем утверждение 2). Чисел аx+b ровно m штук. Покажем, что они между собой не сравнимы по модулю m . Ну пусть для некоторых различных x ₁ и x ₂ из полной системы вычетов оказалось, что ax ₁ +b ax ₂ +b(mod m) . Тогда, по свойствам сравнений из предыдущего пункта, получаем:

ax ₁ ax ₂ (mod m)

x ₁ x ₂ (mod m)

– противоречие с тем, что x ₁ и x ₂ различны и взяты из полной системы вычетов.

Поскольку все числа из данного класса эквивалентности получаются из одного числа данного класса прибавлением числа, кратного m , то все числа из данного класса имеют с модулем m один и тот же наибольший общий делитель. По некоторым соображениям, повышенный интерес представляют те вычеты, которые имеют с модулем m наибольший общий делитель, равный единице, т.е. вычеты, которые взаимно просты с модулем.

Определение. Приведенной системой вычетов по модулю m называется совокупность всех вычетов из полной системы, взаимно простых с модулем m .

Приведенную систему обычно выбирают из наименьших неотрицательных вычетов. Ясно, что приведенная система вычетов по модулю m содержит ( m ) штук вычетов, где ( m )– функция Эйлера – число чисел, меньших m и взаимно простых с m . Если к этому моменту вы уже забыли функцию Эйлера, загляните в пункт 14 и убедитесь, что про нее там кое-что говорилось.

Пример. Пусть m = 42. Тогда приведенная система вычетов суть:

1, 5, 11, 13, 17, 19, 23, 25, 29, 31, 37, 41.

Лемма 2. 1) Любые ( m ) чисел, попарно не сравнимые по модулю m и взаимно простые с модулем, образуют приведенную систему вычетов по модулю m .

2) Если ( a,m ) = 1 и x пробегает приведенную систему вычетов по модулю m , то аx так же пробегает приведенную систему вычетов по модулю m .

Доказательство. Утверждение 1) – очевидно. Докажем утверждение 2). Числа аx попарно несравнимы (это доказывается так же, как в лемме 1 этого пункта), их ровно ( m ) штук. Ясно также, что все они взаимно просты с модулем, ибо (a,m)=1, (x,m)=1 (ax.m)=1 . Значит, числа аx образуют приведенную систему вычетов.

Лемма 3. Пусть m ₁ , m ₂ , ..., m _k – попарно взаимно просты и m ₁ m ₂ ...m _k =M ₁ m ₁ =M ₂ m ₂ =...=M _k m _k , где M _j =m ₁ ...m _j-1 m _j+1 ...m _k

1) Если x ₁ , x ₂ , ..., x _k пробегают полные системы вычетов по модулям m ₁ , m ₂ , ..., m _k соответственно, то значения линейной формы M ₁ x ₁ +M ₂ x ₂ + ...+M _k x _k пробегают полную систему вычетов по модулю m=m ₁ m ₂ ...m _k .

2) Если ₁ , ₂ , ..., _k пробегают приведенные системы вычетов по модулям m ₁ , m ₂ , ..., m _k соответственно, то значения линейной формы M ₁ ₁ +M ₂ ₂ + ...+M _k _k пробегают приведенную систему вычетов по модулю m=m ₁ m ₂ ...m _k .

Доказательство.

1) Форма M ₁ x ₁ +M ₂ x ₂ + ...+M _k x _k принимает, очевидно, m ₁ m ₂ ...m _k =m значений. Покажем, что эти значения попарно несравнимы. Ну пусть

M ₁ x ₁ +M ₂ x ₂ + ...+M _k x _k M ₁ x ₁ ^ +M ₂ x ₂ ^ + ...+M _k x _k ^ (mod m)

Всякое M _j , отличное от M _s , кратно m _s . Убирая слева и справа в последнем сравнении слагаемые, кратные m _s , получим:

M _s x _s  M _s x _s ^ (mod m _s )  x _s  x _s ^ (mod m _s )

– противоречие с тем, что x _s пробегает полную систему вычетов по модулю m _s .

2). Форма M ₁ ₁ +M ₂ ₂ + ...+M _k _k принимает, очевидно, ( m ₁ ) ( m ₂ ) ... ( m _k ) = ( m ₁ m ₂ ... m _k )= ( m ) (функция Эйлера мультипликативна!) различных значений, которые между собой по модулю m=m ₁ m ₂ ...m _k попарно несравнимы. Последнее легко доказывается рассуждениями, аналогичными рассуждениям, проведенным при доказательстве утверждения 1) этой леммы. Так как ( M ₁ ₁ +M ₂ ₂ + ...+M _k _k ,m _s )=(M _s _s ,m _s )=1 для каждого 1 s k , то ( M ₁ ₁ +M ₂ ₂ + ...+M _k _k ,m _s )=1 , следовательно множество значений формы M ₁ ₁ +M ₂ ₂ + ...+M _k _k образует приведенную систему вычетов по модулю m .



Лемма 4. Пусть x ₁ , x ₂ , ..., x _k ,x пробегают полные, а ₁ , ₂ ,..., _k ,  – пробегают приведенные системы вычетов по модулям m ₁ , m ₂ , ..., m _k и m=m ₁ m ₂ ...m _k соответственно, где (m _i m _j )=1 при i j . Тогда дроби {x ₁ /m ₁ +x ₂ /m ₂ +...+x _k /m _k } совпадают с дробями {x/m} , а дроби { ₁ /m ₁ + ₂ /m ₂ +...+ _k /m _k } совпадают с дробями { /m} .

Доказательство. Доказательство обоих утверждений леммы 4 легко получается применением предыдущей леммы 3 после того, как вы приведете каждую сумму {x ₁ /m ₁ +x ₂ /m ₂ +...+x _k /m _k } и { ₁ /m ₁ + ₂ /m ₂ +...+ _k /m _k } к общему знаменателю:

{x ₁ /m ₁ +x ₂ /m ₂ +...+x _k /m _k }={(M ₁ x ₁ +M ₂ x ₂ +...+M _k x _k )/m} ;

{ ₁ /m ₁ + ₂ /m ₂ +...+ _k /m _k }={(M ₁ ₁ +M ₂ ₂ +...+M _k _k )/m} ,

где M _j = m ₁ ... m _{j -1} m _{j +1} ... m _k .

Если теперь принять во внимание, что дробные части чисел, получающихся при делении на модуль m любых двух чисел, сравнимых по модулю m , одинаковы (они равны r/m , где r – наименьший неотрицательный вычет из данного класса), то утверждения настоящей леммы становятся очевидными.

Теорема (Эйлер). Пусть m>1 , (a,m)=1 , ( m ) – функция Эйлера. Тогда:

a ^{( m )} 1(mod m) .

Доказательство. Пусть х пробегает приведенную систему вычетов по mod m :

x=r ₁ ,r ₂ ,...,r _c

где c= (m) их число, r ₁ ,r ₂ ,..., r _c - наименьшие неотрицательные вычеты по mod m . Следовательно, наименьшие неотрицательные вычеты, соответствующие числам ax суть соответственно:

₁ , ₂ ,..., _c

– тоже пробегают приведенную систему вычетов, но в другом порядке (см. Лемму 2 из пункта 17). Значит:

a r ₁ _ (mod m)

a r ₂ _ (mod m)

...

a r _c _ (mod m)

Перемножим эти с штук сравнений. Получится:

a ^c r ₁ r ₂ ...r _c _{j 1} _{j 2} ... _{j c} (mod m)

Так как r ₁ r ₂ ...r _c = ₁ ₂ ... _c 0 и взаимно просто с модулем m , то, поделив последнее сравнение на r ₁ r ₂ ...r _c , получим a ^{( m )} 1(mod m) .



Вторая теорема этого пункта – теорема Ферма – является непосредственным следствием теоремы Эйлера (конечно, при схеме изложения материала, принятой в этой книжке).

Теорема (Ферма). Пусть р – простое число, р не делит a . Тогда:

a ^p-1  1(mod p) .

Доказательство 1. Положим в условии теоремы Эйлера m=p , тогда (m)=p-1 (см. пункт 14 ) . Получаем a ^p-1 1(mod p) .



Необходимо отметить важность условия взаимной простоты модуля и числа a в формулировках теорем Эйлера и Ферма. Простой пример: сравнение 6 ² 1(mod 3) очевидно не выполняется. Однако можно легко подправить формулировку теоремы Ферма, чтобы снять ограничение взаимной простоты.

Следствие 1. Без всяких ограничений на a Z ,

a ^p a(mod p) .

Доказательство. Умножим обе части сравнения a ^p-1 1(mod p) на a . Ясно, что получится сравнение, справедливое и при a , кратном р .



Доказательство 2. Так как р - простое число, то все биномиальные коэффициенты:

(кроме C ₀ ^p и C _p ^p ) делятся на р , ибо числитель выписанного выражения содержит р , а знаменатель не содержит этого множителя. Если вспомнить бином Ньютона, то становится понятно, что разность (A+B) ^p -A ^p -B ^p =C _p ¹ A ^p-1 B ¹ +C _p ² A ^p-2 B ² +...+C _p ^p-2 A ² B ^p-2 +C _p ^p-1 A ¹ B ^p-1 , где А и В – какие угодно целые числа, всегда делится на р . Последовательным применением этого незатейливого наблюдения получаем, что (A+B+C) ^p -A ^p -B ^p -C ^p ={[(A+B)+C] ^p -(A+B) ^p -C ^p }+(A+B) ^p -A ^p -B ^p всегда делится на р ; (A+B+C+D) ^p -A ^p -B ^p -C ^p -D ^p всегда делится на р ; и вообще, (A+B+C+...+K) ^p -A ^p -B ^p -C ^p -...-K ^p всегда делится на р . Положим теперь в последнем выражении A=B=C=...=K=1 и возьмем количество этих чисел равным a . Получится, что a ^p -a делится на р , а это и есть теорема Ферма в более общей формулировке.

Следствие 2. (a+b) ^p a ^p +b ^p (mod p) .

Система шифрования RSA

Пусть и натуральные числа. Функция , реализующая схему RSA, устроена следующим образом

Для дешифрования сообщения достаточно решить сравнение

При некоторых условиях на и это сравнение имеет единственное решение .

Для того, чтобы описать эти условия и объяснить, как можно найти решение, нам потребуется одна теоретико-числовая функция, так называемая функция Эйлера. Эта функция натурального аргумента обозначается и равняется количеству целых чисел на отрезке от до , взаимно простых с . Так и для любого простого числа и натурального . Кроме того, для любых натуральных взаимно простых и . Эти свойства позволяют легко вычислить значение , если известно разложение числа на простые сомножители.

Если показатель степени в сравнении (2) взаимно прост с , то сравнение (2) имеет единственное решение. Для того, чтобы найти его, определим целое число , удовлетворяющее условиям

Такое число существует, поскольку , и притом единственно. Здесь и далее символом будет обозначаться наибольший общий делитель чисел и . Классическая теорема Эйлера, см. [3], утверждает, что для каждого числа , взаимно простого с , выполняется сравнение и, следовательно,

Таким образом, в предположении , единственное решение сравнения (2) может быть найдено в виде

Если дополнительно предположить, что число состоит из различных простых сомножителей, то сравнение (5) будет выполняться и без предположения . Действительно, обозначим и . Тогда делится на , а из (2) следует, что . Подобно (4), теперь легко находим . А кроме того, имеем . Получившиеся сравнения в силу дают нам (5).

Функция (1), принятая в системе RSA, может быть вычислена достаточно быстро. Как это сделать, мы обсудим чуть ниже. Пока отметим лишь, что обратная к функция вычисляется по тем же правилам, что и , лишь с заменой показателя степени на . Таким образом, для функции (1) будут выполнены указанные выше свойства а) и б).

Для вычисления функции (1) достаточно знать лишь числа и . Именно они составляют открытый ключ для шифрования. А вот для вычисления обратной функции требуется знать число , оно и является ``секретом'' , о котором речь идет в пункте в). Казалось бы, ничего не стоит, зная число , разложить его на простые сомножители, вычислить затем с помощью известных правил значение и, наконец, с помощью (3) определить нужное число . Все шаги этого вычисления могут быть реализованы достаточно быстро, за исключением первого. Именно разложение числа на простые множители и составляет наиболее трудоемкую часть вычислений. В теории чисел несмотря на многолетнюю ее историю и на очень интенсивные поиски в течение последних 20 лет, эффективный алгоритм разложения натуральных чисел на множители так и не найден. Конечно, можно, перебирая все простые числа до , и, деля на них , найти требуемое разложение. Но, учитывая, что количество простых в этом промежутке, асимптотически равно , находим, что при , записываемом 100 десятичными цифрами, найдется не менее простых чисел, на которые придется делить при разложении его на множители. Очень грубые прикидки показывают, что компьютеру, выполняющему миллион делений в секунду, для разложения числа таким способом на простые сомножители потребуется не менее, чем лет. Известны и более эффективные способы разложения целых чисел на множители, чем простой перебор простых делителей, но и они работают очень медленно. Таким образом, название статьи М. Гарднера вполне оправдано.

Авторы схемы RSA предложили выбирать число в виде произведения двух простых множителей и , примерно одинаковых по величине. Так как

то единственное условие на выбор показателя степени в отображении (1) есть

Итак, лицо, заинтересованное в организации шифрованной переписки с помощью схемы RSA, выбирает два достаточно больших простых числа и . Перемножая их, оно находит число . Затем выбирается число , удовлетворяющее условиям (7), вычисляется с помощью (6) число и с помощью (3) - число . Числа и публикуются, число остается секретным. Теперь любой может отправлять зашифрованные с помощью (3) сообщения организатору этой системы, а организатор легко сможет дешифровывать их с помощью (5).

Для иллюстрации своего метода Ривест, Шамир и Адлеман зашифровали таким способом некоторую английскую фразу. Сначала она стандартным образом (a=01, b=02, ..., z=26, пробел=00) была записана в виде целого числа , а затем зашифрована с помощью отображения (1) при

и . Эти два числа были опубликованы, причем дополнительно сообщалось, что , где и - простые числа, записываемые соответственно и десятичными знаками. Первому, кто дешифрует соответствующее сообщение

была обещана награда в 100$.

Эта история завершилась спустя 17 лет в 1994 г., когда D. Atkins, M. Graff, A. K. Lenstra и P. C. Leyland сообщили о дешифровке фразы, предложенной в [1]. Она1) была вынесена в заголовок статьи, а соответствующие числа и оказались равными

4 Функция Эйлера

Определение. Функция : R R (или, более общо, : C C ) называется мультипликативной если:

1). Функция определена всюду на N и существует а N такой, что ( а ) 0.

2). Для любых взаимно простых натуральных чисел а ₁ и а ₂ выполняется ( а ₁ · а ₂ ) = ( а ₁ ) · ( а ₂ ).

Пример 1. ( а ) = а ^s , где s - любое (хоть действительное, хоть комплексное) число. Проверка аксиом 1) и 2) из определения мультипликативной функции не составляет труда, а сам пример показывает, что мультипликативных функций по меньшей мере континуум, т.е. много.

Перечислим, кое-где доказывая, некоторые свойства мультипликативных функций. Пусть всюду ниже ( а ) - произвольная мультипликативная функция.

Свойство 1. (1) = 1.

Доказательство. Пусть а - то самое натуральное число, для которого

( а ) 0. Тогда ( а · 1) = ( а ) · (1) = ( а ).

Свойство 2.

,

где р ₁ , р ₂ ,..., р _n - различные простые числа.

Доказательство очевидно.

Свойство 3. Обратно, мы всегда построим некоторую мультипликативную функцию ( a ), если зададим (1) = 1 и произвольно определим ( р  ) для всех простых р и всех натуральных , а для остальных натуральных чисел доопределим функцию ( a ) используя равенство

.

Доказательство сразу следует из основной теоремы арифметики.

Пример 2. Пусть (1) = 1 и ( р  ) = 2 для всех р и . Тогда, для произвольного числа,

.

Свойство 4. Произведение нескольких мультипликативных функций является мультипликативной функцией.

Доказательство. Сначала докажем для двух сомножителей: Пусть ₁ и ₂ - мультипликативные функции = ₁ · ₂ , тогда (проверяем аксиомы определения)

1) (1) = ₁ (1) · ₂ (1) = 1 и, кроме того, существует такое a (это a = 1), что ( a ) 0.

2) Пусть ( a , b ) = 1 - взаимно просты. Тогда

( a · b ) = ₁ ( a · b ) · ₂ ( a · b ) =

= ₁ ( a ) ₁ ( b ) ₂ ( a ) ₂ ( b ) =

= ₁ ( a ) ₂ ( a ) · ₁ ( b ) ₂ ( b ) = ( a ) ( b ).

Доказательство для большего числа сомножителей проводится стандартным индуктивным рассуждением.



Введем удобное обозначение. Всюду далее, символом

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

Лемма 1. Пусть

- каноническое разложение числа a N , - любая мультипликативная функция. Тогда:

Если a = 1, то считаем правую часть равной 1.

Доказательство. Раскроем скобки в правой части. Получим сумму всех (без пропусков и повторений) слагаемых вида

,

где 0 _k _k , для всех k n . Так как различные простые числа заведомо взаимно просты, то

,

а это как раз то, что стоит в доказываемом равенстве слева.



Лемма 2. Пусть ( a ) - любая мультипликативная функция. Тогда

,

- также мультипликативная функция.

Доказательство. Проверим для ( a ) аксиомы определения мультипликативной функции.

1).

2). Пусть

и все р и q различны. Тогда, по предыдущей лемме, имеем: (благо, делители у чисел a и b различны)



Пример 1. Число делителей данного числа.

Пусть ( а ) = а ⁰ 1 - тождественная единица (заведомо мультипликативная функция). Тогда, если

,

то тождество леммы 1 пункта 13 принимает вид:

,

- это не что иное, как количество делителей числа a . По лемме 2 пункта 13, количество делителей ( a ) числа a есть мультипликативная функция.

Пример 2. Сумма делителей данного числа.

Пусть ( a ) = a ¹ a - тождественная мультипликативная функция. Тогда, если

,

то тождество леммы 1 пункта 13 принимает вид:

- сумма всех делителей числа a . По лемме 2 пункта 13, сумма всех делителей есть мультипликативная функция.

Пример 3. Функция Мебиуса.

Функция Мебиуса ( a ) - это мультипликативная функция, определяемая следующим образом: если p - простое число, то ( p ) = -1; ( p  ) = 0, при > 1; на остальных натуральных числах функция доопределяется по мультипликативности.

Таким образом, если число a делится на квадрат натурального числа, отличный от единицы, то ( a ) = 0; если же a = p ₁ p _{2· · ·} p _n (теоретик-числовик сказал бы на своем жаргоне: "если a свободно от квадратов"), то ( a ) = (-1) ^k , где k - число различных простых делителей a . Понятно, что (1) = (-1) ⁰ = 1, как и должно быть.

Лемма 1. Пусть ( a ) - произвольная мультипликативная функция,

.

Тогда:

(при a = 1 считаем правую часть равной 1).

Доказательство. Рассмотрим функцию ₁ ( x ) = ( x ) · ( x ). Эта функция мультипликативна, как произведение мультипликативных функций. Для ₁ ( x ) имеем ( p - простое): ₁ ( p ) = - ( x ); ₁ ( p  ) = 0, при > 1. Следовательно, для ₁ ( x ) тождество леммы 1 пункта 13 выглядит так:



Следствие 1. Пусть ( d ) = d ^-1 = 1/ d (это, конечно, мультипликативная функция),

Тогда:

Пример 4. Функция Эйлера.

Функция Эйлера, пожалуй, самая знаменитая и "дары приносящая" функция из всех функций, рассматриваемых в этом пункте. Функция Эйлера ( a ) есть количество чисел из ряда 0, 1, 2,..., a - 1, взаимно простых с a . Полезность и практическое применение этой функции я продемонстрирую в следующих пунктах, а сейчас давайте поймем, как ее вычислять.

Лемма 2. Пусть

.

Тогда:

1) (формула Эйлера);

2)

в частности, ( p ^ ) = p ^ - p ^{ -1} , ( p ) = p - 1.

Доказательство. Пусть x пробегает числа 0, 1, 2,..., a - 1. Положим _x = ( x , a ) - наибольший общий делитель. Тогда ( a ) есть число значений _x , равных 1. Придумаем такую функцию ( _x ), чтобы она была единицей, когда _x единица, и была нулем в остальных случаях. Вот подходящая кандидатура:

Последнее легко понять, если вспомнить лемму 1 из этого пункта и в ее формулировке взять ( d ) 1. Далее, сделав над собой некоторое усилие, можно усмотреть, что:

Поскольку справа сумма в скобках берется по всем делителям d числа _x = ( x , a ), то d делит x и d делит a . Значит в первой сумме справа в суммировании участвуют только те x , которые кратны d . Таких x среди чисел 0, 1, 2,..., a - 1 ровно a / d штук. Получается, что:

что и требовалось.

Пояснение для читателей, у которых предыдущие соображения не захотели укладываться в голову, например, из-за плохих погодных условий. Имеем

Зафиксируем некоторое d ₀ такое, что d ₀ делит a , d ₀ делит x , x < a . Значит в сумме справа в скобках слагаемых ( d ₀ ) ровно a / d ₀ штук и ( a ) есть просто сумма

После этого, равенство

получается применением следствия из леммы 1 этого пункта. Должен признать, что приведенное доказательство формулы Эйлера и, в особенности, его последний момент с изменением порядка суммирования, объективно тяжеловаты для понимания. Но мы не боимся трудностей!

Второе утверждение леммы следует из первого внесением впереди стоящего множителя a внутрь скобок.

Оказывается, только что доказанная формула

для вычисления функции Эйлера имеет ясный "физический смысл". Дело в том, что в ней отражено так называемое правило включений и исключений:

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

Проиллюстрирую это правило на примере подсчета функции Эйлера для чисел вида

Посмотрите на рисунок 1.

Рис. 1.

Прямоугольник изображает множество всех целых чисел от 0 до a ; овал N ₁ - множество чисел, кратных p ₁ ; кружок N ₂ - числа, кратные p ₂ ; пересечение N _1,2 - множество чисел, делящихся одновременно на p ₁ и p ₂ , т.е. на p ₁ p ₂ ; числа вне овала и кружочка взаимно просты с a . Для подсчета числа чисел, взаимно простых с a , нужно из a вычесть количество чисел в N ₁ и количество чисел в N ₂ (их, соответственно, a / p ₁ и a / p ₂ штук), при этом общая часть N _1,2 (там a /( p ₁ p ₂ ) штук чисел) вычтется дважды, значит ее надо один раз прибавить (вот оно, "включение - исключение"!). В результате получим:

что я вам и утверждал. Мне кажется, что таким способом можно объяснить формулу Эйлера любому смышленому школьнику.

Кстати, любому смышленому школьнику вполне возможно объяснить и то, что при a > 2, ( a ) всегда число четное. Действительно, если k взаимно просто с a и k < a , то число a - k тоже меньше a , взаимно просто с a и не равно k . (Если бы a и a - k имели общий делитель, то их разность a - ( a - k ) = k тоже делилась бы на этот делитель, что противоречит взаимной простоте a и k .) Значит числа, взаимно простые с a разбиваются на пары k и a - k , следовательно, их четное число.

Из леммы 2 вытекают приятные следствия.

Следствие 2. Функция Эйлера мультипликативна.

Доказательство. Имеем:

- произведение двух мультипликативных функций, первая из которых мультипликативна по лемме 2 пункта 13. Значит, ( a ) - мультипликативна.

Следствие 3. .

Доказательство. Пусть

.

Тогда, по лемме 1 пункта 13 имеем:

.

5 Китайская теорема об остатках

В этом пункте детально рассмотрим только сравнения первой степени вида

ax b(mod m),

оставив более высокие степени на съедение следующим пунктам. Как решать такое сравнение? Рассмотрим два случая.

Случай 1. Пусть а и m взаимно просты. Тогда несократимая дробь m/a сама просится разложиться в цепную дробь:

Эта цепная дробь, разумеется, конечна, так как m/a - рациональное число. Рассмотрим две ее последние подходящие дроби:

.

Вспоминаем (пункт 9) важное свойство числителей и знаменателей подходящих дробей: mQ _n-1 -aP _n-1 =(-1) ⁿ . Далее (слагаемое mQ _n-1 , кратное m , можно выкинуть из левой части сравнения):

-aP _n-1  (-1) ⁿ (mod m) т.е.

aP _n-1  (-1) ^n-1 (mod m) т.е.

a[(-1) ^n-1 P _n-1 b]  b(mod m)

и единственное решение исходного сравнения есть:

x (-1) ^n-1 P _n-1 b(mod m)

Пример. Решить сравнение 111x 75(mod 322).

Решение. (111, 322)=1. Включаем алгоритм Евклида:

322=11 · 2+100

111=100 · 1+11

100=11 · 9+1

11=1 · 11

(В равенствах подчеркнуты неполные частные.) Значит, n=4 , а соответствующая цепная дробь такова:

Посчитаем числители подходящих дробей, составив для этого стандартную таблицу:

Числитель предпоследней подходящей дроби равен 29, следовательно, готовая формула дает ответ: x (-1) ³ 29 75 -2175 79(mod 322)



Ох уж эти мне теоретико-числовые рассуждения из разных учебников, продиктованные традицией изложения и необходимостью обязательно использовать ранее изложенную теорию! О чем идет речь в нескольких строках выше? Дано сравнение ax b(mod m) , где a и m взаимно просты. Ну возьмите вы алгоритм Евклида, найдите те самые пресловутые u , v Z такие, что au+vm=1 , умножьте это равенство на b : aub+vmb=b , откуда немедленно следует: aub b(mod m) . Значит решением исходного сравнения является x ub(mod m) . Собственно, и все. Поворчал.

Случай 2. Пусть (a,m)=d . В этом случае, для разрешимости сравнения ax b(mod m) необходимо, чтобы d делило b , иначе сравнение вообще выполняться не может. Действительно, ax b(mod m) бывает тогда, и только тогда, когда ax- b делится на m нацело, т.е. ax- b=t · m ,

t  Z , откуда b=ax- t m , а правая часть последнего равенства кратна d .

Пусть b=db ₁ , a=da ₁ , m=dm ₁ . Тогда обе части сравнения xa ₁ d b ₁ d(mod m ₁ d) и его модуль поделим на d :

xa ₁ b ₁ (mod m ₁ ) ,

где уже а ₁ и m ₁ взаимно просты. Согласно случаю 1 этого пункта, такое сравнение имеет единственное решение x ₀ :

x x ₀ (mod m ₁ ) (*)

По исходному модулю m , числа (*) образуют столько решений исходного сравнения, сколько чисел вида (*) содержится в полной системе вычетов: 0,1,2,..., m-2, m-1 . Очевидно, что из чисел x=x ₀ +t m в полную систему наименьших неотрицательных вычетов попадают только x ₀ , x ₀ +m ₁ , x ₀ +2m ₁ , ..., x ₀ +(d-1)m ₁ , т.е. всего d чисел. Значит у исходного сравнения имеется d решений.

Подведем итог рассмотренных случаев в виде следующей теоремы

Теорема 1. Пусть (a,m)=d . Если b не делится на d , сравнение ax b(mod m) не имеет решений. Если b кратно d , сравнение ax b(mod m) имеет d штук решений.

Пример. Решить сравнение 111x 75(mod 321) .

Решение. (111,321)=3 , поэтому поделим сравнение и его модуль на 3:

37x 25(mod 107) и уже (37,107)=1 .

Включаем алгоритм Евклида (как обычно, подчеркнуты неполные частные):

107=37 2+33

37=33 1+4

33=4 8+1

4=1 4

Имеем n=4 и цепная дробь такова:

Таблица для нахождения числителей подходящих дробей:

Значит, x  (-1) ³  26  25  -650( mod 107)  -8( mod 107)  99( mod 107) .

Три решения исходного сравнения:

x 99(mod 321), x 206(mod 321), x 313(mod 321) ,

и других решений нет.

Теорема 2. Пусть m>1, (a,m)=1 Тогда сравнение ax b(mod m) имеет решение: x ba ^(m)-1 (mod m) .

Доказательство. По теореме Эйлера, имеем: a ^(m) 1(mod m) , следовательно, a ba ^(m)-1 b(mod m) .

Пример. Решить сравнение 7x 3(mod 10) . Вычисляем:

(10)=4; x 3 7 ^4-1 (mod 10) 1029(mod 10) 9(mod 10) .

Видно, что этот способ решения сравнений хорош (в смысле минимума интеллектуальных затрат на его осуществление), но может потребовать возведения числа а в довольно большую степень, что довольно трудоемко. Для того, чтобы как следует это прочувствовать, возведите самостоятельно число 24789 в степень 46728.

Теорема 3. Пусть р – простое число, 0<a<p . Тогда сравнение ax b(mod p) имеет решение:

где C _a ^p – биномиальный коэффициент.

Доказательство непосредственно следует из очевидного сравнения

которое нужно почленно поделить на взаимно простое с модулем число 1 2 3 ... a-1 .

Пример. Решить сравнение 7x 2(mod 11) . Вычисляем:

На этом пункт 19 можно было бы и закончить, но невозможно, говоря о решении сравнений первой степени, обойти стороной вопрос о решении систем сравнений первой степени. Дело в том, что умение решать простейшие системы сравнений не только является неотъемлемой частью общечеловеческой культуры, позволяющей гражданину не падать в ямы, расщелины и открытые люки. Такое умение, кроме всего прочего, пригодится нам при изучении сравнений произвольной степени, о которых пойдет речь в следующих пунктах.

Лемма 1 (Китайская теорема об остатках). Пусть дана простейшая система сравнений первой степени:

где m ₁ ,m ₂ ,...,m _k попарно взаимно просты. Пусть, далее, m ₁ m ₂ ...m _k =M _s m _s ; M _s M _s ^ 1(mod m _s ) (Очевидно, что такое число M _s ^ всегда можно подобрать хотя бы с помощью алгоритма Евклида, т.к. (m _s ,M _s )=1 ); x ₀ =M ₁ M ₁ ^ b ₁ +M ₂ M ₂ ^ b ₂ +...+M _k M _k ^ b _k . Тогда система (*) равносильна одному сравнению

x x ₀ (mod m ₁ m ₂ ...m _k ) ,

т.е. набор решений (*) совпадает с набором решений сравнения x x ₀ (mod m ₁ m ₂ ...m _k ) .

Доказательство. Имеем: m _s делит M _j , при s j. Следовательно, x ₀ M _s M _s ^ b _s (mod m _s ) , откуда x ₀ b _s (mod m _s ) . Это означает, что система (*) равносильна системе

которая, очевидно, в свою очередь, равносильна одному сравнению x x ₀ (mod m ₁ m ₂ ...m _k ) .

В следующей лемме, для краткости формулировки, сохранены обозначения леммы 1.

Лемма 2. Если b ₁ ,b ₂ ,...,b _k пробегают полные системы вычетов по модулям m ₁ ,m ₂ ,...,m _k соответственно, то x ₀ пробегает полную систему вычетов по модулю m ₁ m ₂ ...m _k .

Доказательство. Действительно, x ₀ =A ₁ b ₁ +A ₂ b ₂ +...+A _k b _k пробегает m ₁ m ₂ ...m _k различных значений. Покажем, что все они попарно не сравнимы по модулю m ₁ m ₂ ...m _k .

Ну пусть оказалось, что

A ₁ b ₁ +A ₂ b ₂ +...+A _k b _k  A ₁ b' ₁ +A ₂ b' ₂ +...+A _k b' _k (mod m ₁ m ₂ ...m _k )

Значит,

A ₁ b ₁ +A ₂ b ₂ +...+A _k b _k  A ₁ b' ₁ +A ₂ b' ₂ +...+A _k b' _k (mod m _s )

для каждого s , откуда

M _s M _s ^ b _s  M _s M _s ^ b' _s

Вспомним теперь, что M _s M _s ^  1(mod m _s ) , значит M _s M _s ^  1+m _s  t , откуда (M _s M _s ^ ,m _s )=1 . Разделив теперь обе части сравнения

M _s M _s ^ b _s M _s M _s ^ b' _s

на число M _s M _s ^ , взаимно простое с модулем, получим, что b _s b' _s (mod m _s ) , т.е. b _s =b' _s для каждого s .

Итак, x ₀ пробегает m ₁ m ₂ ...m _k различных значений, попарно не сравнимых по модулю m ₁ m ₂ ...m _k , т.е. полную систему вычетов.

Формулировка для колец

Пусть - коммутативные ассоциативные кольца с единицей, сюрьективные гомоморфизмы, обладающие свойством для всех . Тогда гомоморфизм , заданный формулой

является сюрьективным. Более того, Φ опеределяет изоморфизм

.

Если положить , и определить гомоморфизмы следующим образом

то мы получим арифметическую версию теоремы.

Также часто встречается следующая эквивалентная формулировка для колец, где B_i имеют форму A / I_i , φ_i являются естественными проекциями на A / I_i и требуется, чтобы I_i + I_j = A для любых .

Заключение

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

Список использованных источников

1. С. Ленг, Алгебра, М., 1968

2. С. Коунтинхо, Введение в теорию чисел. Алгоритм RSA, М. 2001

3. А.И. Кострикин, Введение в алгебру, М., 2000

4. О. Зарисский, Коммутативная алгебра, т.1., М., 1963