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

дипломная работа: Математика

Документы: [1]   Word-185081.doc Страницы: Назад 1 Вперед

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

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

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

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


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

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


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

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


Вл_____» ____________ 2006 г.


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


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


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

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

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

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

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

Рецензент:

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

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

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



Гомель 2008

Содержание


Введение        3

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

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

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

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

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

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

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

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

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

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

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

Заключение        62

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


Введение


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

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

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

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

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

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

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


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


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


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

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

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

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

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

  1. дискретны;
  2. детерминированы;
  3. потенциально конечны;
  4. преобразовывают некоторые конструктивные объекты.

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

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

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

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

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


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


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

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

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

x = yq + r , 0 яВгяАаr < y ,

r = x - yq = ( au 1 + 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 .

Далее, раз d яГОяАаP , то 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 < b

0 яВгяАаr 2 < r 1

0 яВгяАаr 3 < r 2

0 яВгяАаr 4 < r 3

В· В· В· В· В· В· В· В· В·

r n -3 = r n -2 q n -1 + r n -1

r n -2 = r n -1 q n + r n

r n -1 = r n q n +1

0 яВгяАаr n -1 < r n -2

0 яВгяАаr n < r n -1

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






_


_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 < 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 шагов.

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

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

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

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

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


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

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

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

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


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

{

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

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


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

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

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

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

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

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

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

}

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

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

do {

       do {

               if (isEven(*gcd)){

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

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

                       }

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

               }

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

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

               }

       } while (isEven(*gcd));

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

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

       }

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

} while (g1 > 0);

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

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

}

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

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

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

}


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

Формулы для 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, { x 0 , 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. Следовательно, в евклидовом кольце гарантировано завершение алгоритма Евклида. Строго говоря, именно в евклидовых кольцах и возможна реализация алгоритма Евклида.

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

  • В евклидовом кольце каждый идеал тАФ главный (в частности, все евклидовы кольца нётеровы).
    • Пусть 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, такие что ai делит ai + 1 и при i>k Aui = 0, а при остальных тАФ Aui = aivi. При этом коэффициенты определены однозначно с точностью до умножения на обратимые элементы кольца 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. Сравнения по одинаковому модулю можно почленно складывать.

Доказательство. Пусть a1яВєяАаb1(mod m), a2яВєяАаb2(mod m). Это означает, что a 1 =b 1 +mt 1 , a 2 =b 2 +mt 2 . После сложения последних двух равенств получим a 1 +a 2 =b 1 +b 2 +m(t 1 +t 2 ) , что означает a 1 +a 2 яВєяАаb 1 +b 2 (mod m).

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

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


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

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


яВи


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

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

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


яВи


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

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

a 0 яВєяАаb 0 (mod m) , a 1 яВєяАаb 1 (mod m) ,..., a n яВєяАаb n (mod m) , x яВєяАаy(mod m) ,

то a 0 x n +a 1 x n-1 +...+a n яВєяАаb 0 y n +b 1 y n-1 +...+b n (mod m)

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

Доказательство. Пусть a яВєяАаb(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 яВєяАаb 1 (mod m) .

яВи

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

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


a яВєяАаb(mod m) яГЫяАаa=b+mt яГЫяАаak=bk+mkt яГЫяАаak яВєяАаbk(mod mk) .

яВи


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

Доказательство. Если a яВєяАаb(mod m 1 ) и a яВєяАаb(mod m 2 ) , то a-b делится на m 1 и на m 2 , значит a-b делится на наименьшее общее кратное m 1 и m 2 .

Свойство 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 1 и x 2 из полной системы вычетов оказалось, что ax 1 +b яВєяАаax 2 +b(mod m) . Тогда, по свойствам сравнений из предыдущего пункта, получаем:

ax 1 яВєяАаax 2 (mod m)

x 1 яВєяАаx 2 (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 1 m 2 ...m k =M 1 m 1 =M 2 m 2 =...=M k m k , где M j =m 1 ...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 m 2 ...m k .

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

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


M 1 x 1 +M 2 x 2 + ...+M k x k яВєяАаM 1 x 1 яГСяАа+M 2 x 2 яГСяАа+ ...+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 1 яБёяАа1 +M 2 яБёяАа2 + ...+M k яБёяАаk принимает, очевидно, яБкяАа( m 1 ) яБкяАа( m 2 ) яГЧяАа... яГЧяАаяБкяАа( m k ) = яБкяАа( m 1 m 2 яГЧяАа... яГЧяАаm k )= яБкяАа( m ) (функция Эйлера мультипликативна!) различных значений, которые между собой по модулю m=m 1 m 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 1 яБёяАа1 +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 +...+x k /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 /m 1 +x 2 /m 2 +...+x k /m k }={(M 1 x 1 +M 2 x 2 +...+M k x k )/m} ;

{ яБёяАа1 /m 1 + яБёяАа2 /m 2 +...+ яБёяАаk /m k }={(M 1 яБёяАа1 +M 2 яБёяАа2 +...+M k яБёяАаk )/m} ,


где M j =m 1 ...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 1 ,r 2 ,...,r c

где c= яБкяАа(m) их число, r 1 ,r 2 ,..., r c - наименьшие неотрицательные вычеты по mod m . Следовательно, наименьшие неотрицательные вычеты, соответствующие числам ax суть соответственно:

яБІяАа1 , яБІяАа2 ,..., яБІяАаc

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


a яГЧяАаr 1 яВєяБІяАаяБкяАаяА±яАа(mod m)

a яГЧяАаr 2 яВєяБІяАаяБкяАаяАІяАа(mod m)

...

a яГЧяАаr c яВєяБІяАаяБкяАаяБгяАа(mod m)

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

a c r 1 r 2 ...r c яВєяБІяАаj 1 яБІяАаj 2 ... яБІяАаj c (mod m)


Так как r 1 r 2 ...r c = яБІяАа1 яБІяАа2 ... яБІяАаc яВ№яАа0 и взаимно просто с модулем m , то, поделив последнее сравнение на r 1 r 2 ...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 2 яВєяАа1(mod 3) очевидно не выполняется. Однако можно легко подправить формулировку теоремы Ферма, чтобы снять ограничение взаимной простоты.

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


a p яВєяАаa(mod p) .


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

яВи

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

(кроме C 0 p и C p p ) делятся на р , ибо числитель выписанного выражения содержит р , а знаменатель не содержит этого множителя. Если вспомнить бином Ньютона, то становится понятно, что разность (A+B) p -A p -B p =C p 1 A p-1 B 1 +C p 2 A p-2 B 2 +...+C p p-2 A 2 B p-2 +C p 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 -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, устроена следующим образом


(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 яВгяАаяБвяАаk яВгяАаяБбяАаk , для всех 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 1 p 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 и p 2 , т.е. на p 1 p 2 ; числа вне овала и кружочка взаимно просты с a . Для подсчета числа чисел, взаимно простых с a , нужно из a вычесть количество чисел в N 1 и количество чисел в N 2 (их, соответственно, a / p 1 и a / p 2 штук), при этом общая часть N 1,2 (там a /( p 1 p 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(mod m),


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

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



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


.


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


-aP n-1 яВєяАа(-1) n (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 , а соответствующая цепная дробь такова:



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


0

2

1

9

11

P n

1

2

3

29

322


Числитель предпоследней подходящей дроби равен 29, следовательно, готовая формула дает ответ: x яВєяАа(-1) 3 яГЧяАа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 1 , a=da 1 , m=dm 1 . Тогда обе части сравнения xa 1 d яВєяАаb 1 d(mod m 1 d) и его модуль поделим на d :

xa 1 яВєяАаb 1 (mod m 1 ) ,

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

x яВєяАаx 0 (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(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 и цепная дробь такова:



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

q n

0

2

1

8

4

P n

1

2

3

26

107


Значит, x яВєяАа(-1) 3 яГЧяАа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 1 ,m 2 ,...,m k попарно взаимно просты. Пусть, далее, m 1 m 2 ...m k =M s m s ; M s M s яГСяАаяВєяАа1(mod m s ) (Очевидно, что такое число M s яГСяАавсегда можно подобрать хотя бы с помощью алгоритма Евклида, т.к. (m s ,M s )=1 ); x 0 =M 1 M 1 яГСяАаb 1 +M 2 M 2 яГСяАаb 2 +...+M k M k яГСяАаb k . Тогда система (*) равносильна одному сравнению


x яВєяАаx 0 (mod m 1 m 2 ...m k ) ,


т.е. набор решений (*) совпадает с набором решений сравнения x яВєяАаx 0 (mod m 1 m 2 ...m k ) .

Доказательство. Имеем: m s делит M j , при s яВ№яАаj. Следовательно, x 0 яВєяАаM s M s яГСяАаb s (mod m s ) , откуда x 0 яВєяАаb s (mod m s ) . Это означает, что система (*) равносильна системе



которая, очевидно, в свою очередь, равносильна одному сравнению x яВєяАаx 0 (mod m 1 m 2 ...m k ) .

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

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

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

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


A 1 b 1 +A 2 b 2 +...+A k b k яВєяАаA 1 b' 1 +A 2 b' 2 +...+A k b' k (mod m 1 m 2 ...m k )


Значит,


A 1 b 1 +A 2 b 2 +...+A k b k яВєяАаA 1 b' 1 +A 2 b' 2 +...+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 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
Страницы: Назад 1 Вперед