От 9 произвести вычеты по модулю 4. Полная и приведенная системы вычетов. Теоремы Эйлера и Ферма. Классы вычетов. Системы вычетов

Согласно свойству сравнений №15, числа одного и того же класса по модулю m имеют с модулем m один и тот же НОД. Особенно важны классы, для которых он равен 1.

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

Приведенная система наименьших неотрицательных вычетов по модулю m обозначается U m .

Количество чисел в приведенной системе вычетов по модулю m , очевидно, равно φ(m ).

Пример :

Приведенная система вычетов по модулю 15 есть {1; 2; 4; 7; 8; 11; 13; 14}. Заметим, что φ(15)=(5–1)∙(3–1)= 8 и действительно, в приведенной системе вычетов по модулю 15 ровно 8 элементов.

Утверждение 1

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

(Доказательство очевидно как в утверждении 1 пункт 2)

Утверждение 2

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

Обратный элемент.

Говорят, что элемент b называется обратным к a по модулю m , если a∙b ≡1(mod m ), и пишут b ≡ a –1 (mod m ).

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

Возникает вопрос – для всех ли элементов по данному модулю m существует обратный (по умножению), и если для каких-то элементов обратный существует, как его найти?

Для ответа на этот вопрос воспользуемся расширенным алгоритмом Евклида. Рассмотрим сначала взаимно простые число a и модуль m . Тогда, очевидно, (a ,m )=1. Расширенный алгоритм Евклида позволяет получить числа x и y , такие, что ax+my= (a ,m ), или, что то же самое, ax+my =1. Из последнего выражения получаем сравнение ax+my ≡1(mod m ). Поскольку my ≡0(mod m ), то ax ≡1(mod m ), а значит полученное с помощью расширенного алгоритма Евклида число x как раз и есть искомый обратный элемент к числу a по модулю m .

Пример.

a =5, m =7. Требуется найти a -1 mod m .

Воспользуемся расширенным алгоритмом Евклида.

Обратный ход:

1=5–2∙2=5–(7–5∙1)∙2=5∙3–7∙2.

x =3, y =–2.

5 -1 ≡3(mod 7)

Проверка: 5∙3=15. 15≡1(mod 7).

Действительно, 3 является обратным элементом к 5 по модулю 7.

Итак, конструктивным образом убедились в том, что для чисел, взаимно простых с модулем, существует обратный по этому модулю. А существуют ли обратные элементы для чисел, не являющихся с модулем взаимно простыми?

Пусть (a ,m )=d ≠1. Тогда a и m представимы в виде a =d ∙a 1 , m =d ∙m 1 . Допустим, что для a существует обратный элемент по модулю m, то есть b : a ∙b ≡1(modm ). Тогда a ∙b= m ∙k +1. Или, что то же самое, d ∙a 1 ∙b= d ∙m 1 ∙k +1. Но тогда по теореме 2 из §1 п.1, в силу того, что и левая часть данного уравнения, и первое слагаемое в правой части делятся на d , то d \1, а это не так, поскольку d ≠1. Пришли к противоречию, следовательно предположение о существовании обратного элемента неверно.

Итак, мы только что доказали

Теорему обратимости

a -1 (mod m ) (a , m ) = 1.

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

Пункт 17. Полная и приведенная системы вычетов.

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

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

Пример : Пусть 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 содержит j (m ) штук вычетов, где j (m )– функция Эйлера – число чисел, меньших m и взаимно простых с m . Если к этому моменту вы уже забыли функцию Эйлера, загляните в пункт 14 и убедитесь, что про нее там кое-что говорилось.

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

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

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

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

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

Таковы определения и основные свойства полной и приведенной систем вычетов, однако в багаже математических знаний существует еще целый ряд очень интересных и полезных фактов, касающихся систем вычетов. Если умолчать про них в этом пункте, то это, боюсь, будет прямым нарушением Закона Российской Федерации об Информации, злонамеренное утаивание которой является, согласно этому закону, административно и, даже, уголовно наказуемым деянием. Кроме того, без знакомства с дальнейшими важными свойствами систем вычетов пункт 17 получится весьма куцым. Продолжим.

Лемма 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 , где

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) Если 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 .

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

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 x 1 +M 2 x 2 + ...+M k x k принимает, очевидно, j (m 1 ) j (m 2 ) Ч ... Ч j (m k ) = j (m 1 m 2 Ч ... Ч m k )= j (m ) (функция Эйлера мультипликативна!) различных значений, которые между собой по модулю m=m 1 m 2 ...m k попарно несравнимы. Последнее легко доказывается рассуждениями, аналогичными рассуждениям, проведенным при доказательстве утверждения 1) этой леммы. Так как (M 1 x 1 +M 2 x 2 + ...+M k x k ,m s)=(M s x s ,m s)=1 для каждого 1 Ј s Ј k , то (M 1 x 1 +M 2 x 2 + ...+M k x k ,m s)=1 , следовательно множество значений формы M 1 x 1 +M 2 x 2 + ...+M k x k образует приведенную систему вычетов по модулю m .

Лемма 4. Пусть x 1 , x 2 , ..., x k ,x пробегают полные, а x 1 , x 2 ,..., x k , x – пробегают приведенные системы вычетов по модулям 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} , а дроби { x 1 /m 1 + x 2 /m 2 +...+ x k /m k } совпадают с дробями { x /m} .

Доказательство. Доказательство обоих утверждений леммы 4 легко получается применением предыдущей леммы 3 после того, как вы приведете каждую сумму {x 1 /m 1 +x 2 /m 2 +...+x k /m k } и { x 1 /m 1 + x 2 /m 2 +...+ x 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} ;

{ 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} ,

где M j =m 1 ...m j-1 m j+1 ...m k .

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

В оставшейся части этого пункта произойдет самое интересное – мы будем суммировать комплексные корни m -ой степени из единицы, при этом нам откроются поразительные связи между суммами корней, системами вычетов и уже знакомой мультипликативной функцией Мебиуса m (m ) .

Обозначим через e k k -ый корень m- ой степени из единицы:

Эти формы записи комплексных чисел мы хорошо помним с первого курса. Здесь k=0,1,...,m-1 – пробегает полную систему вычетов по модулю m .

Напомню, что сумма e 0 + e 1 +...+ e m-1 всех корней m -ой степени из единицы равна нулю для любого m . Действительно, пусть e 0 + e 1 +...+ e m-1 =a . Умножим эту сумму на ненулевое число e 1 . Такое умножение геометрически в комплексной плоскости означает поворот правильного m -угольника, в вершинах которого расположены корни e 0 , e 1 ,..., e m-1 , на ненулевой угол 2 p /m . Ясно, что при этом корень e 0 перейдет в корень e 1 , корень e 1 перейдет в корень e 2 , и т.д., а корень e m-1 перейдет в корень e 0 , т.е. сумма e 0 + e 1 +...+ e m-1 не изменится. Имеем e 1 a=a , откуда a=0 .

Теорема 1. Пусть m>0 - целое число, a О Z , x пробегает полную систему вычетов по модулю m . Тогда, если а кратно m , то

в противном случае, при а не кратном m ,

.

Доказательство. При а кратном m имеем: a=md и

При а не делящемся на m , разделим числитель и знаменатель дроби a/m на d – наибольший общий делитель а и m , получим несократимую дробь a 1 /m 1 . Тогда, по лемме 1, a 1 x будет пробегать полную систему вычетов по модулю m . Имеем:

ибо сумма всех корней степени m 1 из единицы равна нулю.

Напомню, что корень e k m -ой степени из единицы называется первообразным, если его индекс k взаимно прост с m . В этом случае, как доказывалось на первом курсе, последовательные степени e k 1 , e k 2 ,..., e k m-1 корня e k образуют всю совокупность корней m -ой степени из единицы или, другими словами, e k является порождающим элементом циклической группы всех корней m -ой степени из единицы.

Очевидно, что число различных первообразных корней m -ой степени из единицы равно j (m ), где j – функция Эйлера, так как индексы у первообразных корней образуют приведенную систему вычетов по модулю m .

Теорема 2. Пусть m>0 – целое число, x пробегает приведенную систему вычетов по модулю m . Тогда (сумма первообразных корней степени m ):

где m (m ) – функция Мебиуса.

Доказательство. Пусть m=p 1 a 1 p 2 a 2 ...p k a k – каноническое разложение числа m ; m 1 =p 1 a 1 , m 2 =p 2 a 2 , m 3 =p 3 a 3 ; x i пробегает приведенную систему вычетов по модулю m i . Имеем:

При a s =1 получается, что только корень e 0 =1 не является первообразным, поэтому сумма всех первообразных корней есть сумма всех корней минус единица:

стало быть, если m свободно от квадратов (т.е. не делится на r 2 , при r >1 ), то

Если же какой-нибудь показатель a s больше единицы (т.е. m делится на r 2 , при r>1 ), то сумма всех первообразных корней степени m s есть сумма всех корней степени m s минус сумма всех не первообразных корней, т.е. всех корней некоторой степени, меньшей m s . Именно, если m s =p s m s * , то:

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

Задачки

1 . Выпишите на листочке все наименьшие неотрицательные вычеты и все абсолютно наименьшие вычеты а) по модулю 6 , б) по модулю 8 . Чуть ниже выпишите приведенные системы вычетов по этим модулям. Нарисуйте отдельно на комплексной плоскости корни шестой и корни восьмой степени из единицы, на обоих рисунках обведите кружочком первообразные корни и найдите в каждом случае их сумму. 2 . Пусть e – первообразный корень степени 2n из единицы. Найдите сумму: 1+ e + e 2 +...+ e n-1 . 3 . Найдите сумму всех первообразных корней: а) 15-й; б) 24-й; в) 30-й степени из единицы. 4 . Найдите сумму всевозможных произведений первообразных корней n -ой степени из единицы, взятых по два. 5 . Найдите сумму k -х степеней всех корней n -ой степени из единицы. 6 . Пусть m>1 , (a, m)=1 , b – целое число, х пробегает полную, а x – приведенную систему вычетов по модулю m . Докажите, что: а) б) 7 . Докажите, что: , где р пробегает все простые делители числа а .

Кольцо вычетов по модулю n обозначают или . Его мультипликативную группу, как и в общем случае групп обратимых элементов колец, обозначают ∗ × × .

Простейший случай

Чтобы понять структуру группы , можно рассмотреть частный случай , где - простое число, и обобщить его. Рассмотрим простейший случай, когда , то есть .

Теорема: - циклическая группа.

Пример : Рассмотрим группу

= {1,2,4,5,7,8} Генератором группы является число 2. ≡ ≡ ≡ ≡ ≡ ≡ Как видим, любой элемент группы может быть представлен в виде , где ≤ℓφ . То есть группа - циклическая.

Общий случай

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

Примеры: 2 11 ; 8 - примитивный корень по модулю 11 ; 3 не является примитивным корнем по модулю 11 .

В случае целого модуля определение такое же.

Структуру группы определяет следующая теорема: Если p - нечётное простое число и l - целое положительное, то существуют примитивные корни по модулю , то есть - циклическая группа.

Пример

Приведённая система вычетов по модулю состоит из классов вычетов: . Относительно определённого для классов вычетов умножения они образуют группу, причём и взаимно обратны (то есть ⋅ ), а и обратны сами себе.

Структура группы

Запись означает «циклическая группа порядка n».

Структура группы (Z/ n Z) ×

	×	φ	λ	Генератор группы			×	φ	λ	Генератор группы			×	φ	λ	Генератор группы			×	φ	λ	Генератор группы
1	C 1	1	1	0		33	C 2 ×C 10	20	10	2, 10		65	C 4 ×C 12	48	12	2, 12		97	C 96	96	96	5
2	C 1	1	1	1		34	C 16	16	16	3		66	C 2 ×C 10	20	10	5, 7		98	C 42	42	42	3
3	C 2	2	2	2		35	C 2 ×C 12	24	12	2, 6		67	C 66	66	66	2		99	C 2 ×C 30	60	30	2, 5
4	C 2	2	2	3		36	C 2 ×C 6	12	6	5, 19		68	C 2 ×C 16	32	16	3, 67		100	C 2 ×C 20	40	20	3, 99
5	C 4	4	4	2		37	C 36	36	36	2		69	C 2 ×C 22	44	22	2, 68		101	C 100	100	100	2
6	C 2	2	2	5		38	C 18	18	18	3		70	C 2 ×C 12	24	12	3, 69		102	C 2 ×C 16	32	16	5, 101
7	C 6	6	6	3		39	C 2 ×C 12	24	12	2, 38		71	C 70	70	70	7		103	C 102	102	102	5
8	C 2 ×C 2	4	2	3, 5		40	C 2 ×C 2 ×C 4	16	4	3, 11, 39		72	C 2 ×C 2 ×C 6	24	6	5, 17, 19		104	C 2 ×C 2 ×C 12	48	12	3, 5, 103
9	C 6	6	6	2		41	C 40	40	40	6		73	C 72	72	72	5		105	C 2 ×C 2 ×C 12	48	12	2, 29, 41
10	C 4	4	4	3		42	C 2 ×C 6	12	6	5, 13		74	C 36	36	36	5		106	C 52	52	52	3
11	C 10	10	10	2		43	C 42	42	42	3		75	C 2 ×C 20	40	20	2, 74		107	C 106	106	106	2
12	C 2 ×C 2	4	2	5, 7		44	C 2 ×C 10	20	10	3, 43		76	C 2 ×C 18	36	18	3, 37		108	C 2 ×C 18	36	18	5, 107
13	C 12	12	12	2		45	C 2 ×C 12	24	12	2, 44		77	C 2 ×C 30	60	30	2, 76		109	C 108	108	108	6
14	C 6	6	6	3		46	C 22	22	22	5		78	C 2 ×C 12	24	12	5, 7		110	C 2 ×C 20	40	20	3, 109
15	C 2 ×C 4	8	4	2, 14		47	C 46	46	46	5		79	C 78	78	78	3		111	C 2 ×C 36	72	36	2, 110
16	C 2 ×C 4	8	4	3, 15		48	C 2 ×C 2 ×C 4	16	4	5, 7, 47		80	C 2 ×C 4 ×C 4	32	4	3, 7, 79		112	C 2 ×C 2 ×C 12	48	12	3, 5, 111
17	C 16	16	16	3		49	C 42	42	42	3		81	C 54	54	54	2		113	C 112	112	112	3
18	C 6	6	6	5		50	C 20	20	20	3		82	C 40	40	40	7		114	C 2 ×C 18	36	18	5, 37
19	C 18	18	18	2		51	C 2 ×C 16	32	16	5, 50		83	C 82	82	82	2		115	C 2 ×C 44	88	44	2, 114
20	C 2 ×C 4	8	4	3, 19		52	C 2 ×C 12	24	12	7, 51		84	C 2 ×C 2 ×C 6	24	6	5, 11, 13		116	C 2 ×C 28	56	28	3, 115
21	C 2 ×C 6	12	6	2, 20		53	C 52	52	52	2		85	C 4 ×C 16	64	16	2, 3		117	C 6 ×C 12	72	12	2, 17
22	C 10	10	10	7		54	C 18	18	18	5		86	C 42	42	42	3		118	C 58	58	58	11
23	C 22	22	22	5		55	C 2 ×C 20	40	20	2, 21		87	C 2 ×C 28	56	28	2, 86		119	C 2 ×C 48	96	48	3, 118
24	C 2 ×C 2 ×C 2	8	2	5, 7, 13		56	C 2 ×C 2 ×C 6	24	6	3, 13, 29		88	C 2 ×C 2 ×C 10	40	10	3, 5, 7		120	C 2 ×C 2 ×C 2 ×C 4	32	4	7, 11, 19, 29
25	C 20	20	20	2		57	C 2 ×C 18	36	18	2, 20		89	C 88	88	88	3		121	C 110	110	110	2
26	C 12	12	12	7		58	C 28	28	28	3		90	C 2 ×C 12	24	12	7, 11		122	C 60	60	60	7
27	C 18	18	18	2		59	C 58	58	58	2		91	C 6 ×C 12	72	12	2, 3		123	C 2 ×C 40	80	40	7, 83
28	C 2 ×C 6	12	6	3, 13		60	C 2 ×C 2 ×C 4	16	4	7, 11, 19		92	C 2 ×C 22	44	22	3, 91		124	C 2 ×C 30	60	30	3, 61
29	C 28	28	28	2		61	C 60	60	60	2		93	C 2 ×C 30	60	30	11, 61		125	C 100	100	100	2
30	C 2 ×C 4	8	4	7, 11		62	C 30	30	30	3		94	C 46	46	46	5		126	C 6 ×C 6	36	6	5, 13
31	C 30	30	30	3		63	C 6 ×C 6	36	6	2, 5		95	C 2 ×C 36	72	36	2, 94		127	C 126	126	126	3
32	C 2 ×C 8	16	8	3, 31		64	C 2 ×C 16	32	16	3, 63		96	C 2 ×C 2 ×C 8	32	8	5, 17, 31		128	C 2 ×C 32	64	32	3, 127

Применение

На сложности, Ферма, Хули, . Уоринг сформулировал теорему Вильсона, а Лагранж её доказал. Эйлер предположил существование примитивных корней по модулю простого числа. Гаусс это доказал. Артин выдвинул свою гипотезу о существовании и количественной оценке простых чисел, по модулю которых заданное целое число является первообразным корнем. Брауэр внес вклад в исследование проблемы существования наборов последовательных целых чисел, каждое из которых - k-ая степень по модулю p. Билхарц доказал аналог гипотезы Артина. Хули доказал гипотезу Артина с предположением справедливости расширенной гипотезы Римана в полях алгебраических чисел.

Примечания

Литература

• Айерлэнд К., Роузен М. Классическое введение в современную теорию чисел. - М. : Мир, 1987.
• Алферов А.П., Зубов А.Ю., Кузьмин А.С. Черемушкин А.В. Основы криптографии. - Москва: «Гелиос АРВ», 2002.
• Ростовцев А.Г., Маховенко Е.Б. Теоретическая криптография. - Санкт-Петербург: НПО «Профессионал», 2004.

Как показано в §5, отношение сравнимости по модулю т обладает свойствами рефлексивности, симметричности и транзитивности; поэтому оно является отношением эквивалентности Возьмем произвольное целое число а. Обозначим через о множество чисел, сравнимых с а по модулю т: Пусть. Пусть теперь. И так далее. Процесс будет длиться до тех пор, пока построенные множества не будут покрывать все множество целых чисел. При этом возникает разбиение2> множества Z на множества а. Ь, с,..которые называют классами вычетов по модулю m; каждое число, входяшее в какой-нибудь из классов, называется вычетом этого класса. Число классов вычетов по модулю т равно т. Действительно, остаток отделения целого числа на т принимает одно из значений т - 2 или т - 1 и поэтому каждое из чисел попадает в один из классов 01, количество которых равно т. Взяв по одному числу из каждого класса вычетов получим систему представителей классов вычетов, или полную систему вычетов по модулю т. Системы вычетов Пример 1. Различные полные системы вычетов по модулю 7: Лемма 3. Числа, хт образуют полную систему вычетов по модулю т тогда и только тогда, когда они попарно не сравнимы по модулю т. Необходимость очевидна. Докажем достаточность. Если два числа не сравнимы по модулю ту то они попадают в разные классы вычетов. Так как всего классов вычетов m и рассматриваемых чисел гп, то они составляют полную систему вычетов. Лемма 4. Пусть,хт - полная система вычетов по модулю т, целое число а взаимно просто с т, b - произвольное целое число. Тогда числа ахi + 6, ах2 + Ь, ..ахт -f b также образуют полную систему вычетов. Согласно лемме 3 достаточно убедиться в том, чт Предположим (для приведения к противоречию), ч OG общем определении отношения и его свойствах речь пойдет ниже - в главе LXVIII; заметим, что теория чисел является источником многих важных примеров для обшей алгебры. Разбиение множества - это представление его в виде объединения попарно не пересекающихся подмножеств. Тогда a{xi-xj) \my и, поскольку (о, m) = 1, имеем (Xi-Xj) m, что противоречит лемме 3. Лемма 5. Пусть х = a(modm). Тогда (Системы вычетов м Действительно, пусть г - остаток от деления о на т. Тогда по лемме 2 Но так как х = a(mod т), при делении на m ««ело г"тамке имеет остаток г, и, следовательно, (я,т) = (г,т), откуда и вытекает требуемое. Итак, числа из одного класса вычетов по модулю т имеют один и тот же наибольший обший делитель с т. Поэтому становится корректным следующее определени е. Вычет по модулю т называют приведенным, если он взаимно прост с т. Совокупность приведенных вычетов из разных классов вычетов называют приведенной системой вычетов. Пример 2. При m = 7 приведенная система вычетов может выглядеть так: Системы вычетов Функцией Эйлера (р(т) называют число натуральных чисел, не превосходящих т и взаимно простьк с т. Например, . Легко видеть, что если р - простое число, Очевидно, что приведенная система вычетов по модулю т содержит чисел. Лемма 6. Пусть а взаимно просто приведенная система вычетов по модулю т. Тогда числа ах\, ах к также образуют приведенную систему вычетов по модулю т. 4 Так как числа о и Х{ взаимно просты с т, таким же свойством обладает и их произведение ах*. В силу леммы 4 числа ах\,ах2,... принадлежат к разным классам вычетов, и, следовательно, в силу предыдущего, образуют приведенную систему вычетов.

Полная система вычетов. Приведённая система вычетов. Наиболее употребительные системы вычетов: наименьшая положительная, наименьшая неотрицательная, абсолютно наименьшая и т.д.

Теорема 1 . Свойства полной и приведённой система вычетов.

1°.Критерий полной системы вычетов. Любая совокупность из m целых чисел, попарно не сравнимых по модулю m , образует полную систему вычетов по модулю m .

2°. Если числа x 1 , x 2 , ..., x m – полная система вычетов по модулю m , (a , m ) = 1, b – произвольное целое число, то числа ax 1 +b , ax 2 +b , ..., ax m +b также составляют полную систему вычетов по модулю m .

3°. Критерий Приведённой системы вычетов. Любая совокупность, состоящая из j(m ) целых чисел, попарно не сравнимых по модулю m и взаимно простых с модулем, образует приведённую систему вычетов по модулю m .

4°. Если числа x 1 , x 2 , ..., x j ( m ) – приведённая система вычетов по модулю m , (a , m ) = 1, то числа ax 1 , ax 2 , ..., a x j ( m ) также составляют приведённую систему вычетов по модулю m .

Теорема 2. Теорема Эйлера.

Если числа a и m взаимно простые, то a j ( m ) º 1(mod m ).

Cледствие .

1°. Теорема Ферма. Если p – простое число и a не делится на p , то a p –1 º 1(mod p ).

2°. Обобщенная теорема Ферма. Если p – простое число, то a p º a (mod p ) для любых a ÎZ .

§ 4. Решение сравнений с переменной

Решение сравнений. Равносильность. Степень сравнения.

Теорема . Свойства решений сравнений.

1°.Решениями сравнений являются целые классы вычетов.

2°. ("k )(a k º b k (mod m ))Ùk = Þ сравнения º 0 (mod m ) и º 0 (mod m ) равносильны.

3°. Если обе части сравнения умножить на число, взаимно простое с модулем, то получится сравнение, равносильное исходному.

4°. Всякое сравнение по простому модулю p равносильно сравнению, степень которого не превосходит p –1.

5°. Сравнение º 0 (mod p ), где p – простое число, имеет не более n различных решений.

6°. Теорема Вильсона. (n –1)! º –1 (mod n ) Û n простое число.

§ 5. Решение сравнений первой степени

ax º b (mod m ).

Теорема . 1°. Если (a , m ) = 1, то сравнение имеет решение, причем единственное.

2°. Если (a , m ) = d и b не делится на d , то сравнение не имеет решений.

3°. Если (a , m ) = d и b делится на d , то сравнение имеет d различных решений, которые составляют один класс вычетов по модулю .

Способы решения сравнений ax º b (mod m ) в случае, когда (a , m ) = 1:

1) подбор (перебор элементов полной системы вычетов);

2) использование теоремы Эйлера;

3) использование алгоритма Евклида;

4) вариация коэффициентов (использование свойства 2° полной системы вычетов из Теоремы 2.2);

§ 6. Неопределенные уравнения первой степени

ax +by = c .

Теорема . Уравнение ax +by = c разрешимо тогда и только тогда, когда c (a , b ).

В случае (a , b ) = 1 все решения уравнения задаются формулами

t ÎZ , где x 0 является каким-либо решением сравнения

ax º c (mod b ), y 0 = .

Диофантовы уравнения.

ГЛАВА 10. Комплексные числа

Определение системы комплексных чисел. Существование системы комплексных чисел

Определение системы комплексных чисел.

Теорема . Система комплексных чисел существует.

Модель: R 2 с операциями

(a , b )+(c , d ) = (a +c , b +d ), (a , b )×(c , d ) = (ac –bd , bc +ad ),

i = (0, 1) и отождествлением а = (а , 0).

Алгебраическая форма комплексного числа

Представление комплексного числа в виде z = a +bi , где a , b ÎR , i 2 = –1. Единственность такого представления. Re z , Im z .

Правила выполнения арифметических действий над комплексными числами в алгебраической форме.

Арифметическое n -мерное векторное пространство C n . Системы линейных уравнений, матрицы и определители над C .

Извлечение квадратных корней из комплексных чисел в алгебраической форме.