Теория остатков
Лемма 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 для любых .
Заключение
История арифметики остатков начинается с исследований К.Ф. Гаусса, который впервые стал рассматривать сравнения. В дальнейшем была обнаружена связь теории сравнений с астрономическими задачами (китайская теорема об остатках). В результате многочисленных исследований теория остатков была распространена на кольца произвольной природы. В последнее время обнаружилось приложение этой теории в криптографии. В дипломной работе изложена теория остатков на современном алгебраическом языке.
Список использованных источников
С. Ленг, Алгебра, М., 1968
С. Коунтинхо, Введение в теорию чисел. Алгоритм RSA, М. 2001
А.И. Кострикин, Введение в алгебру, М., 2000
О. Зарисский, Коммутативная алгебра, т.1., М., 1963