МИНИСТЕРСТВО ОБРАЗОВАНИЯ РЕСПУБЛИКИ БЕЛАРУСЬ
Учреждениеобразования
«Гомельскийгосударственный университет
имениФранциска Скорины »
Математическийфакультет
Кафедраалгебры и геометрии
Допущена кзащите
Зав. кафедрой_________ Шеметков Л.А.
«_____» ____________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 Алгоритм Евклида
Определение.Число dZ , делящее одновременно числа а , 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 ry ,
r = x – yq= ( au1 + bv 1 ) – ( au 2 + bv 2) q = a ( u 1 – u 2 q )+b ( v 1 – v 2 q ) P.
Пусть d P — наименьшее положительное число из P (призадумайтесь, почему такоеимеется!). Тогда а делится на d . В самом деле, a = dq + r 1, 0 r 1 d , a P, d P , значит r 1 P, следовательно r 1 = 0. Аналогичными рассуждениямиполучается, что b делится на d , значит d — общий делительa и b .
Далее, раз dP , то d = au 0 + bv 0. Если теперь d 1 — общий делитель a и b ,то d 1 | ( au 0 + bv 0 ),т.е. d 1 | d . Значит d d 1и 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
0 r 2
0 r 3
0 r 4 · · · · · · · · ·
r n -3 = r n -2 q n -1 + r n -1
r n -2 = r n -1 q n + r n
r n -1 = r n q n +1
0 r n -1
0 r n
r n +1 = 0
3.Заменить r := «остаток от деления а наb », а := b , b := r .
4. Идти на 2.
В современнойбуквенной записи, алгоритм Евклида выглядит так: a > b; a, b Z.
Имеем: b >r 1 > r 2 >… > r n >0, следовательно процесс оборвется максимум через b шагов. Оченьинтересный и практически важный народохозяйственный вопрос о том, когдаалгоритм Евклида работает особенно долго, а когда справляется с работоймолниеносно, мы рассмотрим чуть позже. Давайте сейчас покажем, что r n =( a , b ). Просмотрим последовательно равенства сверху вниз:всякий делитель а и b делит r 1, r 2,..., r n . Если же просматривать эту цепочку равенствот последнего к первому, то видно, что r n | r n -1, r n | r n -2, и т.д., т.е. rn делит а и 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 -2q n -1 ) q n = …
(идем по цепочке равенств снизу вверх, выражая из каждого следующегоравенства остаток и подставляя его в получившееся уже к этому моментувыражение)
… = au + bv = ( a , b ).
Пример. Пусть а = 525, b = 231.(ниже приводится запись деления уголком, и каждый раз то, что было в уголке,т.е. делитель, приписывается к остатку от деления с левой стороны, а остаток,как новый делитель, берется в уголок)
_
_42|
42 |
0
_
63|
42 |
21
2
_
231|
189 |
42
1
525|
462 |
63
3
231
2
Запись тогоже самого в виде цепочки равенств:
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 N), откуда моментально даже n 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
if (*u
// Если 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
swap(*a, a1); swap(*b, b1); swap(*gcd, g1);
}
} while (isEven(*gcd));
while(*a
*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
}
Расширенный алгоритм Евклида и соотношение Безу
Формулы для ri могут быть переписаны следующимобразом:
r1 = a+ b( — q0)
r2 = b− r1q1 = a( − q1)+ b(1 + q1q0)
/>
(a,b) = rn = as + bt
здесь s и t целые. Это представление наибольшего общегоделителя называется соотношением Безу, а числа s и t — коэффициентамиБезу. Соотношение Безу является ключевым в доказательстве основной теоремыарифметики.1.3Применения алгоритма Евклида
Пусть требуется решить линейное диофантовоуравнение:
ax + by = c ,
где a , b , c Z; a и b — не нули.
Попробуемпорассуждать, глядя на это уравнение.
Пусть ( a ,b ) = d . Тогда a = a 1 d ; b =b 1 d и уравнение выглядит так:
a 1 d· x + b 1 d· y = c , т.е. d· ( a 1 x + b 1 y) = c .
Теперь ясно,что у такого уравнения имеется решение (пара целых чисел x и y )только тогда, когда d | c . Пусть d | c . Поделимобе части уравнения на d , и всюду далее будем считать, что ( a ,b ) = 1.
Рассмотримнесколько случаев.
Случай 1.Пусть c = 0, уравнение имеет вид ax + by = 0 — " однородноелинейное диофантово уравнение". x = -
b />
a y .
Так как x должен быть целымчислом, то y = at , где t — произвольное целое число (параметр).Значит x = — bt и решениями однородного диофантова уравнения ax + by= 0 являются все пары вида {- bt , at }, где t = 0;±1; ±2;… Множество всех таких пар называется общим решением линейногооднородного диофантова уравнения, любая же конкретная пара из этого множестваназывается частным решением.
Случай 2.Пусть теперь c 0. Этот случай закрываетсяследующей теоремой.
Теорема. Пусть ( a , b ) = 1, { x0, y 0 } — частное решение диофантовауравнения ax + by = c . Тогда его общее решение задается формулами:
x = x 0 — bt
y = y 0 + at.
Такимобразом, и в теории линейных диофантовых уравнений общее решение неоднородногоуравнения есть сумма общего решения соответствующего однородного уравнения инекоторого (любого) частного решения неоднородного уравнения.
Доказательство.То, что правые частиуказанных в формулировке теоремы равенств действительно являются решениями,проверяется их непосредственной подстановкой в исходное уравнение. Покажем, чтолюбое решение уравнения ax + by = c имеет именно такой вид, какой указанв формулировке теоремы. Пусть { x * , y *} — какое-нибудь решениеуравнения ax + by = c . Тогда ax * + by * = c , новедь и ax 0 + by 0 = c . Следуямноголетней традиции доказательства подобных теорем, вычтем из первогоравенства второе и получим:
a (x *- x 0 ) + b ( y *- y 0 )= 0
— однородное уравнение. Далее, глядяна случай 1, рассмотрение которого завершилось несколькими строками выше, пишемсразу общее решение: x *- x 0 = — bt , y *-y 0 = at , откуда моментально, используя навыкитретьего класса средней школы, получаем:
x * = x 0- bt,
y * = y 0 + at.
Как же искать то самое частноерешение { x 0, y 0 }. Мы договорились, что( a , b ) = 1. Это означает, что найдутся такие u и v изZ , что au + bv = 1, причем эти u и v мы легкоумеем находить с помощью алгоритма Евклида. Умножим теперь равенство au + bv= 1 на c и получим: a ( uc ) + b ( vc )= c , т.е. x 0 = uc , y 0 =vc .
Определение.Цепной(или, непрерывной) дробью называется выражение вида:
/>
(Бедныенаборщики в докомпьютерные времена буквально стрелялись, когда им приходилосьнабирать в книжках подобные многоэтажные выражения.) Договоримся называть числаq 1, q 2 ,..., q n ,…- неполными частными и считаем, что q 1 Z ,а q 2 ,..., q n ,… N .Числа называются подходящими дробями цепной дроби . 1 = q 1, 2, = q 1 +
1 />
q 2 , 3 = q 1 +
1 /> q 2 +
1 />
q 3 , и т. д.
Цепная дробьможет быть как конечной (содержащей конечное число дробных линий и неполныхчастных), так и бесконечной вниз и вправо (на юго-восток). В первом случае она,очевидно, представляет некоторое рациональное число, во втором случае — поканепонятно что она вообще из себя представляет, но ясно, что все ее подходящиедроби — рациональные числа.
Пусть Q , = a / b; a , b Z , b > 0. Оказывается, что при этихусловиях, указанный выше процесс разложения числа в цепную дробь всегда конечени выполним с помощью достопочтенного и любимого нами алгоритма Евклида.Действительно, отдадим алгоритму числа a и b , и внимательнопосмотрим, что получится.
a = bq 1 + r 1 т.е.
a />
b = q 1 +
1 />
b / r 1 b = r 1 q 2 + r 2 т.е.
b />
r 1 = q 2 +
1 />
r 1 / r 2 r 1 = r 2 q 3 + r 3 т.е.
r 1 />
r 2 = q 3 +
1 />
r 2 / r 3 … . r n -2 = r n -1 q n + r n т.е.
r n -2 />
r n -1 = q n +
1 />
r n -1 / r n r n -1 = r n q n +1 т.е.
r n -1 />
r n = q n +1 .
Значит:
/>
где q 1, q 2 ,..., 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-1R кольца R(коммутативного с единицей) по мультипликативной системе />называетсяпространство дробей с числителями из R и знаменателями из S сарифметическими операциями и отождествлениями, обычными для дробей.
Мультипликативнойсистемой в кольце Rназывается подмножество S в R, содержащее 1, не содержащее нуля изамкнутое по умножению (в кольце R). Для мультипликативной системы Sмножество />образует идеал в кольце R.В случае, когда множество S не содержит делителей нуля кольца R,идеал IS = (0) и система Sназывается регулярной. Если R — целостное кольцо, в ней всякаямультипликативная система регулярна.
Элементами кольцачастных кольца R по мультипликативной системе S являютсяформальные дроби вида r/s, где r — произвольный элемент R,а s — элемент множества S. Две дроби r1/ s1 и r2 / s2считаются эквивалентными (представляют один и тот же элемент кольца частных),если />. Операции сложения и умножения определяются какобычно:
/>
/>
Проверяется,что если в сумме или произведении дроби заменить на эвивалентные, новыйрезультат будет выражаться дробью, эквивалентной прежней. С такими операциямимножество S − 1Rприобретает структуру коммутативного кольца с единицей. Нулём в нём служитдробь 0/1, единицей — дробь 1/1.
Свойства
· Кольцо частныхимеет каноническую структуру алгебры над кольцом R, так как вместе с кольцом S-1Rсразу определён и канонический гомоморфизм кольца R в S-1R(каждому элементу r из R соответствует дробь r/1). Ядромэтого гомоморфизма является идеал IS.В случае, если система S регулярна (не содержит делителей нуля), этотгомоморфизм инъективен, и кольцо R, таким образом, вложено в своё кольцочастных по системе S. При этом дробь r/s является единственнымрешением уравнения sx = r.
· Если оба элементаr и s принадлежат S, тогда в кольце S-1Rсодержатся дроби r/s и s/r. Их произведение равно 1,следовательно, они обратимы. Обратно: каждый обратимый элемент кольца S-1Rимеет вид er/s, где r и s принадлежат S, а e — обратимый элемент кольца R.
· Если кольцо Rне имеет (собственных) делителей нуля (т.е. это целостное кольцо), множествовсех ненулевых элементов образует мультипликативную систему S.Соответствующее кольцо частных будет полем, которое называется полем частныхцелостного кольца. Отсюда следует, что каждое целостное кольцо вложено внекоторое поле, а именно — в своё поле частных.
· Если R — евклидово кольцо, то всякое кольцо, промежуточное между R и его полемчастных, является кольцом частных кольца R по некотороймультипликативной системе S.
· Если система Sсостоит из одних только обратимых элементов кольца R, каноническийгомоморфизм кольца R в S-1R превращается в изоморфизм,так как каждая дробь r/s оказывается сократимой в кольце R.
· Если кольцо R' является подкольцом кольца R, томножество всех элементов из R', обратимых вкольце R, образует регулярную мультипликативную систему S вкольце R'. Тогда каждой дроби r/s однозначно соответствуетнекоторый элемент кольца R. Множество всех таких элементов кольца Rобразует кольцо частных кольца R' в кольце R.
Примеры
· Полем частныхкольца целых чисел />является полерациональных чисел />.
· Степени числа 10в /> образуют мультипликативную систему. Кольцом частных по нейбудет кольцо конечных десятичных дробей.
· Полем частныхкольца многочленов k[X1,X2,...,Xn]над полем k будет поле рациональных функций k(X1,X2,...,Xn).
· Пусть />— простой идеал в 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 — мнимая единица, i2= − 1) с нормой d(a + ib)= a2 + b2 — евклидово.
· Произвольное поле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-1Rевклидова кольца R по мультипликативной системе S тоже являетсяевклидовым. Нормой дроби x из S-1R принимается
/>, где dR — евклидова норма в R, а dS — норма в S-1R.
Деление с остаткомопределяется так. Пусть есть две ненулевые дроби x =r / t и y из S-1R.По определению нормы в S-1R существует элементы u в Rи s в S, такие что y = u / sи dS(y) = dR(u).Произведём деление с остатком в кольце R элементов rs и u:
rs = uq + r', так что dR(r')dR(u). Тогда r/ t = (u / s)(q / t) + r' / ts.Из построения следуют неравенства />.
· Евклидовымиявляются кольца конечных двоичных и конечных десятичных дробей, так как ониявляются кольцами частных кольца целых чисел Z.
· Евклидовымиявляются кольца рациональных функций над полем C с фиксированнымиполюсами, так как такие кольца являются кольцами частных кольца многочленов C[x].
/>/>Алгоритм Евклида
В евклидовомкольце осуществим алгоритм Евклида нахождения наибольшего общего делителя двухчисел (элементов). Пусть изначально даны два элемента a0 и a1,причём />и />. Деление состатком даёт элемент a2 = a0− a1q1 с d(a2)d(a1). Если он не равен нулю, можно опятьприменить деление с остатком, и получить элемент a3= a1 − a2q2,и т. д. Таким образом генерируется цепочка значений />с />. Однако эта цепочка прерывается,поскольку всякое число из />можетстрого превосходить лишь конечное количество других таких чисел. Это означает,что при некотором n остаток an+1 равен нулю, а anне равен, он и есть НОД элементов a0 и a1.Следовательно, в евклидовом кольце гарантировано завершение алгоритма Евклида.Строго говоря, именно в евклидовых кольцах и возможна реализация алгоритмаЕвклида.
Свойства евклидовых колец
· В евклидовомкольце каждый идеал — главный (в частности, все евклидовы кольца нётеровы).
o Пусть I —произвольный идеал в евклидовом кольце. Если он содержит лишь 0, — он главный.В противном случае среди его ненулевых элементов найдётся элемент f сминимальной нормой (принцип минимума для натуральных чисел). Он делит всеостальные элементы идеала: Если g — произвольный элемент идеала I,представим его в виде g = fq + r с d(r). Тогда 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, такие что aiделит ai+ 1 и при i>kAui = 0, а при остальных — Aui = aivi.При этом коэффициенты />определеныоднозначно с точностью до умножения на обратимые элементы кольца R. (Тутпрямо задействована евклидовость кольца R.)
3 Сравнения и арифметика остатков
Определение. Пусть а, b Z, m N . Говорят, что число а сравнимо с bпо модулю m , если а и b при делении на m даютодинаковые остатки. Запись этого факта выглядит так:
a b(modm) .
Очевидно, чтобинарное отношение сравнимости m (неважно, покакому модулю) есть отношение эквивалентности на множестве целых чисел, алюбители алгебры скажут, что это отношение является даже конгруэнцией кольца Z, фактор-кольцо по которой Z/ m называетсякольцом вычетов и обозначается Z m.
Ясно, чточисло a сравнимо с b по модулю m тогда и только тогда,когда a-b делится на m нацело. Очевидно, это, в свою очередь,бывает тогда и только тогда, когда найдется такое целое число t , что a=b+mt. Знатоки алгебры добавят к этим эквивалентным утверждениям, чтосравнимость a с b по модулю m означает, что a и bпредставляют один и тот же элемент в кольце Z m.
Свойство1. Сравненияпо одинаковому модулю можно почленно складывать.
Доказательство.Пусть a1b1(modm), a2b2(mod m). Это означает,что a 1 =b 1 +mt 1 , a 2 =b2 +mt 2 . После сложения последних двух равенствполучим a 1 +a 2 =b 1 +b 2 +m(t 1+t 2 ) , что означает a 1 +a 2 b1 +b 2 (mod m).
Свойство2. Слагаемое,стоящее в какой-либо части сравнения, можно переносить в другую часть, изменивего знак на обратный.
Доказательство.
/>
Свойство3. Клюбой части сравнения можно прибавить любое число, кратное модулю.
Доказательство.
/>
Свойство4. Сравненияпо одинаковому модулю можно почленно перемножать и, следовательно,
Свойство5. Обечасти сравнения можно возвести в одну и ту же степень.
Доказательство.
/>
Как следствиеиз вышеперечисленных свойств, получаем
Свойство6. Если
a0 b 0 (mod m) , a 1 b 1 (modm) ,..., a n b n (mod m) , x y(mod m) ,
то a 0x n +a 1 x n-1 +...+a n b 0 yn +b 1 y n-1 +...+b n (mod m)
Свойство7. Обечасти сравнения можно разделить на их общий делитель, взаимно простой смодулем.
Доказательство.Пусть ab(mod m) , a=a 1 d , b=b 1 d. Тогда (a 1 -b 1 ) d делитсяна m . Поскольку d и m взаимно просты, то на m делитсяименно (a 1 -b 1 ) , что означает a 1 b1 (mod m) .
Свойство8. Обечасти сравнения и его модуль можно умножить на одно и то же целое число илиразделить на их общий делитель.
Доказательство.
a b(modm) a=b+mt ak=bk+mkt ak bk(modmk) .
Свойство9. Еслисравнение a b имеет место по нескольким разным модулям,то оно имеет место и по модулю, равному наименьшему общему кратному этихмодулей.
Доказательство.Если ab(mod m 1 ) и a b(mod m 2) , то a-b делится на m 1 и на m 2 ,значит a-b делится на наименьшее общее кратное m 1 и m2 .
Свойство10. Еслисравнение имеет место по модулю m , то оно имеет место и по модулю d ,равному любому делителю числа m .
Доказательствоочевидноследует из транзитивности отношения делимости: если a b(mod m), то a-b делится на m , значит a-b делится на d ,где d|m .
Свойство11. Еслиодна часть сравнения и модуль делятся на некоторое число, то и другая частьсравнения должна делиться на то же число.
Доказательство.
ab(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 1 и x 2 из полнойсистемы вычетов оказалось, что ax 1 +b ax 2 +b(modm) . Тогда, по свойствам сравнений из предыдущего пункта, получаем:
ax 1 ax2 (mod m)
x 1 x2 (mod m)
–противоречие с тем, что x 1 и x 2 различныи взяты из полной системы вычетов.
Поскольку всечисла из данного класса эквивалентности получаются из одногочисла данного класса прибавлением числа, кратного 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 1,m 2, ..., m k – попарно взаимно просты и m 1m 2 ...m k =M 1 m 1 =M 2m 2 =...=M k m k , где M j =m1 ...m j-1 m j+1 ...m k
1) Если x 1, x 2, ..., x k пробегают полные системывычетов по модулям m 1, m 2, ..., m k соответственно,то значения линейной формы M 1 x 1 +M 2 x 2+ ...+M k x k пробегают полную систему вычетовпо модулю m=m 1 m 2 ...m k .
2) Если 1, 2, ..., k пробегаютприведенные системы вычетов по модулям m 1, m 2,..., m k соответственно, то значения линейной формы M 1 1+M 2 2 + ...+M k kпробегают приведенную систему вычетов по модулю m=m 1 m2 ...m k .
Доказательство.
1) Форма M1 x 1 +M 2 x 2 + ...+M k xk принимает, очевидно, m 1 m 2 ...m k=m значений. Покажем, что эти значения попарно несравнимы. Ну пусть
M 1 x1 +M 2 x 2 + ...+M k x k M1 x 1 +M 2 x 2+ ...+M k x k (modm)
Всякое M j, отличное от M s , кратно m s .Убирая слева и справа в последнем сравнении слагаемые, кратные m s ,получим:
Ms x s M s x s (mod m s )x s x s (mod m s )
–противоречие с тем, что x s пробегает полную систему вычетовпо модулю m s .
2). Форма M1 1 +M 2 2+ ...+M k k принимает,очевидно, ( m 1 ) ( m 2) … ( m k )= ( m 1 m 2 … mk )= ( m ) (функция Эйлерамультипликативна!) различных значений, которые между собой по модулю m=m 1m 2 ...m k попарно несравнимы. Последнее легкодоказывается рассуждениями, аналогичными рассуждениям, проведенным придоказательстве утверждения 1) этой леммы. Так как ( M 1 1+M 2 2 + ...+M k k,m s )=(M s s ,m s )=1для каждого 1 s k , то ( M 11 +M 2 2 +...+M k k ,m s )=1 ,следовательно множество значений формы M 1 1+M 2 2 + ...+M k kобразует приведенную систему вычетов по модулю m .
Лемма 4. Пусть x 1,x 2, ..., x k ,x пробегают полные, а 1, 2 ,..., k, –пробегают приведенные системы вычетов по модулям m 1, m 2,..., m k и m=m 1 m 2 ...m k соответственно,где (m i m j )=1 при i j .Тогда дроби {x 1 /m 1 +x 2 /m 2 +...+xk /m k } совпадают с дробями {x/m} , а дроби {1 /m 1 + 2 /m 2+...+ k /m k } совпадают сдробями { /m} .
Доказательство.Доказательствообоих утверждений леммы 4 легко получается применением предыдущей леммы 3 послетого, как вы приведете каждую сумму {x 1 /m 1 +x 2/m 2 +...+x k /m k } и { 1/m 1 + 2 /m 2 +...+ k/m k } к общему знаменателю:
{x 1 /m1 +x 2 /m 2 +...+x k /m k }={(M1 x 1 +M 2 x 2 +...+M k xk )/m} ;
{ 1/m 1 + 2 /m 2 +...+ k/m k }={(M 1 1 +M 22 +...+M k k )/m},
где Mj=m1 ...mj-1 mj+1 ...mk.
Если теперьпринять во внимание, что дробные части чисел, получающихся при делении намодуль m любых двух чисел, сравнимых по модулю m , одинаковы (ониравны r/m , где r – наименьший неотрицательный вычет из данногокласса), то утверждения настоящей леммы становятся очевидными.
Теорема(Эйлер). Пусть m>1, (a,m)=1 , ( m ) – функция Эйлера. Тогда:
a (m ) 1(mod m) .
Доказательство.Пусть х пробегаетприведенную систему вычетов по mod m :
x=r 1 ,r 2 ,...,r c
где c= (m)их число, r 1 ,r 2 ,..., r c — наименьшие неотрицательные вычеты по mod m . Следовательно, наименьшиенеотрицательные вычеты, соответствующие числам ax суть соответственно:
1, 2 ,...,c
– тожепробегают приведенную систему вычетов, но в другом порядке (см. Лемму 2 изпункта 17). Значит:
a r 1 (modm)
a r 2 (modm)
…
a r c (modm)
Перемножимэти с штук сравнений. Получится:
a c r 1 r 2 ...r c j1 j 2 … j c (mod m)
Так как r 1r 2 ...r c = 1 2… c 0 и взаимно просто смодулем m , то, поделив последнее сравнение на r 1 r 2...r c , получим a ( m ) 1(modm) .
Втораятеорема этого пункта – теорема Ферма – является непосредственным следствиемтеоремы Эйлера (конечно, при схеме изложения материала, принятой в этойкнижке).
Теорема(Ферма). Пусть р –простое число, р не делит a . Тогда:
a p-1 1(mod p) .
Доказательство1. Положим в условиитеоремы Эйлера m=p , тогда (m)=p-1 (см. пункт 14). Получаем a p-1 1(mod p) .
Необходимоотметить важность условия взаимной простоты модуля и числа a вформулировках теорем Эйлера и Ферма. Простой пример: сравнение 6 2 1(mod3) очевидно не выполняется. Однако можно легко подправить формулировку теоремыФерма, чтобы снять ограничение взаимной простоты.
Следствие1. Без всякихограничений на a Z ,
a p a(mod p) .
Доказательство.Умножим обе частисравнения a p-1 1(mod p) на a . Ясно,что получится сравнение, справедливое и при a , кратном р .
Доказательство2. Так как р — простое число, то все биномиальные коэффициенты:
(кроме C 0p и C p p ) делятся на р ,ибо числитель выписанного выражения содержит р , а знаменатель несодержит этого множителя. Если вспомнить бином Ньютона, то становится понятно,что разность (A+B) p -A p -B p =C p 1A p-1 B 1 +C p 2 A p-2 B2 +...+C p p-2 A 2 B p-2 +Cp p-1 A 1 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 -Bp всегда делится на р ; (A+B+C+D) p -A p-B p -C p -D p всегда делится на р; и вообще, (A+B+C+...+K) p -A p -B p -Cp -...-K p всегда делится на р . Положимтеперь в последнем выражении A=B=C=...=K=1 и возьмем количество этихчисел равным a . Получится, что a p -a делится на р, а это и есть теорема Ферма в более общей формулировке.
Следствие2. (a+b) p ap +b p (mod p) .
Система шифрования RSA
/>/>Пусть />и />натуральныечисла. Функция />, реализующая схемуRSA, устроена следующим образом
/>/> (1)
Для дешифрованиясообщения />достаточно решить сравнение
/>/> (2)
При некоторых условиях на/>и/>этосравнение имеет единственное решение />.
Для того,чтобы описать эти условия и объяснить, как можно найти решение, нам потребуетсяодна теоретико-числовая функция, так называемая функция Эйлера. Эта функциянатурального аргумента />обозначается />иравняется количеству целых чисел на отрезке от />до />, взаимнопростых с />. Так />и />для любого простого числа />инатурального />. Кроме того, />для любых натуральных взаимно простых />и />.Эти свойства позволяют легко вычислить значение />, если известноразложение числа />на простые сомножители.
Еслипоказатель степени />в сравнении (2) взаимнопрост с />, то сравнение (2) имеет единственное решение. Для того, чтобынайти его, определим целое число />, удовлетворяющее условиям
/>/> (3)
Такое числосуществует, поскольку />, и притомединственно. Здесь и далее символом />будет обозначатьсянаибольший общий делитель чисел />и />.Классическая теорема Эйлера, см. [3], утверждает, что для каждого числа />, взаимнопростого с />, выполняется сравнение />и,следовательно,
/>/> (4)
Таким образом, впредположении />, единственноерешение сравнения (2) может быть найдено в виде
/>/> (5)
Еслидополнительно предположить, что число />состоит из различныхпростых сомножителей, то сравнение (5) будет выполняться и без предположения />.Действительно, обозначим />и />. Тогда />делитсяна />, а из (2) следует, что />. Подобно (4),теперь легко находим />. Акроме того, имеем />. Получившиеся сравнения в силу />даютнам (5).
Функция (1),принятая в системе RSA, может быть вычислена достаточно быстро. Как этосделать, мы обсудим чуть ниже. Пока отметим лишь, что обратная к />функция />вычисляется по тем же правилам, что и/>, лишь с заменой показателя степени />на />. Такимобразом, для функции (1) будут выполнены указанные выше свойства а) и б).
Длявычисления функции (1) достаточно знать лишь числа />и />. Именно онисоставляют открытый ключ для шифрования. А вот для вычисления обратной функциитребуется знать число />, оно и является``секретом'', о котором речь идет в пункте в). Казалось бы, ничего не стоит,зная число />, разложить его на простые сомножители, вычислить затем с помощьюизвестных правил значение />и, наконец, спомощью (3) определить нужное число />. Все шаги этоговычисления могут быть реализованы достаточно быстро, за исключением первого.Именно разложение числа />на простые множители исоставляет наиболее трудоемкую часть вычислений. В теории чисел несмотря намноголетнюю ее историю и на очень интенсивные поиски в течение последних 20лет, эффективный алгоритм разложения натуральных чисел на множители так и ненайден. Конечно, можно, перебирая все простые числа до />, и, деля на них/>,найти требуемое разложение. Но, учитывая, что количество простых в этомпромежутке, асимптотически равно />,находим, что при />, записываемом 100 десятичнымицифрами, найдется не менее />простыхчисел, на которые придется делить />при разложении его намножители. Очень грубые прикидки показывают, что компьютеру, выполняющемумиллион делений в секунду, для разложения числа />такимспособом на простые сомножители потребуется не менее, чем />лет.Известны и более эффективные способы разложения целых чисел на множители, чемпростой перебор простых делителей, но и они работают очень медленно. Такимобразом, название статьи М. Гарднера вполне оправдано.
Авторы схемыRSA предложили выбирать число />в виде произведениядвух простых множителей />и />, примерноодинаковых по величине. Так как
/>/> (6)
то единственное условиена выбор показателя степени />в отображении (1) есть
/>/> (7)
Итак, лицо,заинтересованное в организации шифрованной переписки с помощью схемы 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 и а 2 выполняется( а 1 · а 2 ) = (а 1 ) · ( а 2 ).
Пример 1. ( а )= а s , где s — любое (хоть действительное, хотькомплексное) число. Проверка аксиом 1) и 2) из определения мультипликативнойфункции не составляет труда, а сам пример показывает, что мультипликативныхфункций по меньшей мере континуум, т.е. много.
Перечислим,кое-где доказывая, некоторые свойства мультипликативных функций. Пусть всюду ниже( а ) — произвольная мультипликативная функция.
Свойство1. (1)= 1.
Доказательство.Пусть а — то самое натуральное число, для которого
(а ) 0. Тогда ( а · 1) = (а ) · (1) = ( а ).
Свойство2.
/>,
где р 1, р 2 ,..., р n — различные простыечисла.
Доказательствоочевидно.
Свойство3. Обратно,мы всегда построим некоторую мультипликативную функцию ( a ),если зададим (1) = 1 и произвольно определим ( р) для всех простых р и всех натуральных ,а для остальных натуральных чисел доопределим функцию ( a )используя равенство
/>.
Доказательствосразуследует из основной теоремы арифметики.
Пример 2. Пусть (1)= 1 и ( р ) = 2 для всех р и .Тогда, для произвольного числа,
/>.
Свойство4. Произведениенескольких мультипликативных функций является мультипликативной функцией.
Доказательство.Сначаладокажем для двух сомножителей: Пусть 1 и 2 — мультипликативные функции = 1 ·2, тогда (проверяем аксиомы определения)
1) (1)= 1 (1) · 2 (1) = 1 и,кроме того, существует такое a (это a = 1), что (a ) 0.
2) Пусть ( a, b ) = 1 — взаимно просты. Тогда
( a · b) = 1 ( a · b) · 2 ( a · b) =
= 1 ( a ) 1 ( b ) 2 ( a ) 2 ( b ) =
= 1 ( a ) 2 ( a ) ·1 ( b ) 2 ( b ) =( a ) ( b ).
Доказательстводля большего числа сомножителей проводится стандартным индуктивнымрассуждением.
Введемудобное обозначение. Всюду далее, символом
/>
будемобозначать сумму чего-либо, в которой суммирование проведено по всем делителям dчисла n . Следующие менее очевидные, чем предыдущие, свойствамультипликативных функций я сформулирую в виде лемм, ввиду их важности иудобства дальнейших ссылок.
Лемма 1. Пусть
/>
— каноническое разложение числа a N , -любая мультипликативная функция. Тогда:
/>
Если a =1, то считаем правую часть равной 1.
Доказательство.Раскроемскобки в правой части. Получим сумму всех (без пропусков и повторений)слагаемых вида
/>,
где 0 kk , для всех k n. Так как различные простые числа заведомо взаимно просты, то
/>,
а это как разто, что стоит в доказываемом равенстве слева.
Лемма 2. Пусть ( a) — любая мультипликативная функция. Тогда
/>,
— такжемультипликативная функция.
Доказательство.Проверимдля ( a ) аксиомы определения мультипликативной функции.
1). />
2). Пусть
/>
и все р иq различны. Тогда, по предыдущей лемме, имеем: (благо, делители у чисел aи b различны)
/>
Пример 1. Число делителей данногочисла.
Пусть (а ) = а 0 1 — тождественная единица(заведомо мультипликативная функция). Тогда, если
/>,
то тождестволеммы 1 пункта 13 принимает вид:
/>,
— это не чтоиное, как количество делителей числа a . По лемме 2 пункта 13,количество делителей ( a ) числа a естьмультипликативная функция.
Пример 2.Сумма делителей данного числа.
Пусть (a ) = a 1 a — тождественнаямультипликативная функция. Тогда, если
/>,
то тождестволеммы 1 пункта 13 принимает вид:
/>
/>
сумма первых ( + 1) членов
геометрической прогрессии
/>
— сумма всехделителей числа a . По лемме 2 пункта 13, сумма всех делителей естьмультипликативная функция.
Пример 3. Функция Мебиуса.
ФункцияМебиуса ( a ) — это мультипликативная функция,определяемая следующим образом: если p — простое число, то (p ) = -1; ( p ) = 0, при >1; на остальных натуральных числах функция доопределяется помультипликативности.
Такимобразом, если число a делится на квадрат натурального числа, отличный отединицы, то ( a ) = 0; если же a = p 1p 2· · · p n (теоретик-числовиксказал бы на своем жаргоне: «если a свободно от квадратов»),то ( a ) = (-1) k , где k — число различных простых делителей a . Понятно, что (1) =(-1) 0 = 1, как и должно быть.
Лемма 1. Пусть ( a) — произвольная мультипликативная функция,
/>.
Тогда:
/>
(при a =1 считаем правую часть равной 1).
Доказательство.Рассмотримфункцию 1 ( x ) = ( x )· ( x ). Эта функция мультипликативна, как произведениемультипликативных функций. Для 1 ( x ) имеем( p — простое): 1 ( p ) = — (x ); 1 ( p ) = 0, при >1. Следовательно, для 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 0 такое, что d 0 делит a ,d 0 делит x , x a . Значит в суммесправа в скобках слагаемых ( d 0 ) ровно a/ d 0 штук и ( a ) есть простосумма
/>
После этого,равенство
/>
получаетсяприменением следствия из леммы 1 этого пункта. Должен признать, что приведенноедоказательство формулы Эйлера и, в особенности, его последний момент сизменением порядка суммирования, объективно тяжеловаты для понимания. Но мы небоимся трудностей!
Второеутверждение леммы следует из первого внесением впереди стоящего множителя a внутрьскобок.
Оказывается,только что доказанная формула
/>
длявычисления функции Эйлера имеет ясный «физический смысл». Дело в том,что в ней отражено так называемое правило включений и исключений:
Правиловключений и исключений. Пусть задано множество А и выделено k егоподмножеств. Количество элементов множества А , которые не входят ни водно из выделенный подмножеств, подсчитывается так: надо из общего числаэлементов А вычесть количества элементов всех k подмножеств,прибавить количества элементов всех их попарных пересечений, вычесть количестваэлементов всех тройных пересечений, прибавить количества элементов всехпересечений по четыре и т.д. вплоть до пересечения всех k подмножеств.
Проиллюстрируюэто правило на примере подсчета функции Эйлера для чисел вида
/>
Посмотрите нарисунок 1.
/>
Рис. 1.
Прямоугольникизображает множество всех целых чисел от 0 до a ; овал N 1 — множество чисел, кратных p 1; кружок N 2 — числа, кратные p 2; пересечение N 1,2 — множество чисел, делящихся одновременно на p 1 и p2, т.е. на p 1 p 2; числавне овала и кружочка взаимно просты с a . Для подсчета числа чисел,взаимно простых с a , нужно из a вычесть количество чисел в N1 и количество чисел в N 2 (их,соответственно, a / p 1 и a / p 2 штук),при этом общая часть N 1,2 (там a /( p 1p 2 ) штук чисел) вычтется дважды, значит ее надо одинраз прибавить (вот оно, «включение — исключение»!). В результатеполучим:
/>
что я вам иутверждал. Мне кажется, что таким способом можно объяснить формулу Эйлералюбому смышленому школьнику.
Кстати,любому смышленому школьнику вполне возможно объяснить и то, что при 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(modm),
оставив болеевысокие степени на съедение следующим пунктам. Как решать такое сравнение?Рассмотрим два случая.
Случай 1. Пусть а и m взаимнопросты. Тогда несократимая дробь m/a сама просится разложиться в цепнуюдробь:
/>
Эта цепнаядробь, разумеется, конечна, так как m/a — рациональное число. Рассмотримдве ее последние подходящие дроби:
/>.
Вспоминаем(пункт 9) важное свойство числителей и знаменателей подходящих дробей: mQ n-1-aP n-1 =(-1) n . Далее (слагаемое mQ n-1, кратное m , можно выкинуть из левой части сравнения):
-aPn-1 (-1) n (mod m) т.е.
aPn-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(mod322).
Решение. (111, 322)=1. Включаемалгоритм Евклида:
322=11 ·2+100
111=100 ·1+11
100=11 · 9+1
11=1 · 11
(В равенствахподчеркнуты неполные частные.) Значит, n=4 , а соответствующая цепнаядробь такова:
/>
Посчитаемчислители подходящих дробей, составив для этого стандартную таблицу: 2 1 9 11 P n 1 2 3 29 322
Числительпредпоследней подходящей дроби равен 29, следовательно, готовая формула даетответ: x (-1) 3 29 75-2175 79(mod 322)
Ох уж эти мнетеоретико-числовые рассуждения из разных учебников, продиктованные традициейизложения и необходимостью обязательно использовать ранее изложенную теорию! Очем идет речь в нескольких строках выше? Дано сравнение ax b(modm) , где 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=db1 , a=da 1 , m=dm 1. Тогда обе части сравнения xa 1 d b 1d(mod m 1 d) и его модуль поделим на d :
xa 1 b1 (mod m 1 ) ,
где уже а 1и m 1 взаимно просты. Согласно случаю 1 этогопункта, такое сравнение имеет единственное решение x 0 :
x x0 (mod m 1 ) (*)
По исходномумодулю m , числа (*) образуют столько решений исходного сравнения,сколько чисел вида (*) содержится в полной системе вычетов: 0,1,2,..., m-2,m-1 . Очевидно, что из чисел x=x 0 +t m вполную систему наименьших неотрицательных вычетов попадают только x 0,x 0 +m 1, x 0 +2m 1, ..., x 0+(d-1)m 1 , т.е. всего d чисел. Значит у исходногосравнения имеется d решений.
Подведем итограссмотренных случаев в виде следующей теоремы
Теорема 1.Пусть (a,m)=d. Если b не делится на d , сравнение ax b(modm) не имеет решений. Если b кратно d , сравнение ax b(modm) имеет d штук решений.
Пример. Решить сравнение 111x 75(mod321) .
Решение. (111,321)=3 , поэтому поделимсравнение и его модуль на 3:
37x 25(mod107) иуже (37,107)=1 .
Включаемалгоритм Евклида (как обычно, подчеркнуты неполные частные):
107=37 2+33
37=33 1+4
33=4 8+1
4=1 4
Имеем n=4 ицепная дробь такова:
/>
Таблица длянахождения числителей подходящих дробей: q n 2 1 8 4 P n 1 2 3 26 107
Значит,x(-1) 3 26 25 -650(mod107) -8(mod107) 99(mod107) .
Три решенияисходного сравнения:
x 99(mod321), x 206(mod 321), x 313(mod 321) ,
и другихрешений нет.
Теорема 2.Пусть m>1,(a,m)=1 Тогда сравнение ax b(mod m) имеет решение: xba (m)-1 (mod m) .
Доказательство.Потеореме Эйлера, имеем: a (m) 1(modm) , следовательно, a ba (m)-1 b(modm) .
Пример. Решить сравнение 7x 3(mod10) . Вычисляем:
(10)=4;x 3 7 4-1 (mod 10) 1029(mod10) 9(mod 10) .
Видно, чтоэтот способ решения сравнений хорош (в смысле минимума интеллектуальных затратна его осуществление), но может потребовать возведения числа а вдовольно большую степень, что довольно трудоемко. Для того, чтобы как следуетэто прочувствовать, возведите самостоятельно число 24789 в степень 46728.
Теорема 3.Пусть р– простое число, 0. Тогда сравнение ax b(modp) имеет решение:
/>
где C ap – биномиальный коэффициент.
Доказательствонепосредственноследует из очевидного сравнения
/>
которое нужнопочленно поделить на взаимно простое с модулем число 1 2 3… a-1 .
Пример. Решить сравнение 7x 2(mod11) . Вычисляем:
/>
/>
На этом пункт19 можно было бы и закончить, но невозможно, говоря о решении сравнений первойстепени, обойти стороной вопрос о решении систем сравнений первой степени. Делов том, что умение решать простейшие системы сравнений не только являетсянеотъемлемой частью общечеловеческой культуры, позволяющей гражданину не падатьв ямы, расщелины и открытые люки. Такое умение, кроме всего прочего, пригодитсянам при изучении сравнений произвольной степени, о которых пойдет речь вследующих пунктах.
Лемма 1(Китайская теорема об остатках). Пусть дана простейшая система сравнений первойстепени:
/>
где m 1,m 2 ,...,m k попарно взаимно просты. Пусть,далее, m 1 m 2 ...m k =M s m s; M s M s 1(modm s ) (Очевидно, что такое число M s всегдаможно подобрать хотя бы с помощью алгоритма Евклида, т.к. (m s ,Ms )=1 ); x 0 =M 1 M 1 b1 +M 2 M 2 b 2+...+M k M k b k .Тогда система (*) равносильна одному сравнению
x x0 (mod m 1 m 2 ...m k ) ,
т.е. наборрешений (*) совпадает с набором решений сравнения x x 0(mod m 1 m 2 ...m k ) .
Доказательство.Имеем: ms делит M j , при s j.Следовательно, x 0 M s M s bs (mod m s ) , откуда x 0 bs (mod m s ) . Это означает, что система (*)равносильна системе
/>
которая,очевидно, в свою очередь, равносильна одному сравнению x x 0(mod m 1 m 2 ...m k ) .
В следующейлемме, для краткости формулировки, сохранены обозначения леммы 1.
Лемма 2. Если b 1 ,b2 ,...,b k пробегают полные системы вычетов помодулям m 1 ,m 2 ,...,m k соответственно,то x 0 пробегает полную систему вычетов по модулю m 1m 2 ...m k .
Доказательство.Действительно,x 0 =A 1 b 1 +A 2 b 2 +...+Ak b k пробегает m 1 m 2 ...mk различных значений. Покажем, что все они попарно не сравнимыпо модулю m 1 m 2 ...m k .
Ну пусть оказалось, что
A1 b 1 +A 2 b 2 +...+A k bk A 1 b' 1 +A 2 b'2 +...+A k b' k (mod m 1 m 2 ...mk )
Значит,
A1 b 1 +A 2 b 2 +...+A k bk A 1 b' 1 +A 2 b'2 +...+A k b' k (mod m s )
для каждого s , откуда
Ms M s b s M s Ms b' s
Вспомним теперь, что M sM s 1(mod m s) , значит M s M s 1+m s t , откуда (M sM s ,m s )=1. Разделив теперь обе части сравнения
M s Ms b s M sM s b' s
на число Ms M s , взаимно простое смодулем, получим, что b s b' s (mod m s) , т.е. b s =b' s для каждого s .
Итак, x 0пробегает m 1 m 2 ...m k различныхзначений, попарно не сравнимых по модулю m 1 m 2 ...m k, т.е. полную систему вычетов.
Формулировка для колец
Пусть /> — коммутативные ассоциативные кольца с единицей, />сюрьективные гомоморфизмы, обладающие свойством />для всех />. Тогдагомоморфизм />, заданный формулой
/>
являетсясюрьективным. Более того, Φ опеределяетизоморфизм
/>.
Если положить/>, />и определить гомоморфизмы следующимобразом
/>
то мы получимарифметическую версию теоремы.
Также частовстречается следующая эквивалентная формулировка для колец, где Bi имеют форму A/ Ii, φiявляются естественными проекциями на A / Iiи требуется, чтобы Ii + Ij= A для любых />.
Заключение
История арифметикиостатков начинается с исследований К.Ф. Гаусса, который впервые сталрассматривать сравнения. В дальнейшем была обнаружена связь теории сравнений састрономическими задачами (китайская теорема об остатках). В результатемногочисленных исследований теория остатков была распространена на кольцапроизвольной природы. В последнее время обнаружилось приложение этой теории вкриптографии. В дипломной работе изложена теория остатков на современномалгебраическом языке.
Список использованных источников
1. С.Ленг, Алгебра, М., 1968
2. С.Коунтинхо, Введение в теорию чисел. Алгоритм RSA, М. 2001
3. А.И.Кострикин, Введение в алгебру, М., 2000
4. О.Зарисский, Коммутативная алгебра, т.1., М., 1963