Полная и приведённая системы вычетов. Системы вычетов Основные сведения из теории

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

Теорема 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 .

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

Совокупность чисел, сравнимых с a по модулю m называется классом чисел по модулю m (или классом эквивалентности). Все числа одного класса имеют вид mt + r при фиксированном r .

При заданном m , r может принимать значения от 0 до m -1, т.е. всего существует m классов чисел по модулю m , и любое целое число попадет в один из классов по модулю m . Таким образом,

Z = m m … [m -1] m , где [r ] m ={x Z: x ≡r (mod m )}

Любое число класса [r ] m называется вычетом по модулю m по отношению ко всем числам того же класса. Число, равное остатку r , называется наименьшим неотрицательным вычетом .

Вычет, наименьший по абсолютной величине, называется абсолютно наименьшим вычетом .

Пример

Возьмем модуль m =5. И пусть a =8. Разделим a на m с остатком:

Остаток r =3. Значит 8 5 , и наименьший неотрицательный вычет числа 8 по модулю 5 есть 3.

Абсолютно наименьший вычет можно отыскать, вычислив r-m=3-5=-2, и сравнив абсолютные величины |-2| и |3|. |-2|<|3|, значит -2 – абсолютно наименьший вычет числа 8 по модулю 5.

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

{0; 1;…; m -1} = Z m – полная система наименьших неотрицательных вычетов.

{– ;…; 0;…; } (если m –нечетное число) ;

{ - ,…,-1, 0, 1,…, } или {- ,…, -1, 0, 1,…, } (если m четное число) – полная система абсолютно наименьших вычетов.

Пример

Если m =11, то полная система наименьших неотрицательных вычетов есть {0; 1; 2; 3; 4; 5; 6; 7; 8; 9; 10}, а полная система абсолютно наименьших вычетов – {–5; –4; –3; –2; –1; 0; 1; 2; 3; 4; 5}.

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

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

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

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

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

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

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

Чисел ax +b будет ровно m штук. Остается доказать, что любые 2 числа ax 1 +b и ax 2 +b несравнимы по модулю m , если x 1 x 2 (mod m )

Доказательство от противного. Предположим, что ax 1 +b ≡ ax 2 +b (mod m ) в силу 4-го св-ва сравнений, ax 1 ≡ ax 2 (mod m ) в силу св-ва сравнений №9 и того, что (a , m ) = 1, имеем x 1 ≡ x 2 (mod m ). Получили противоречие с тем, что x 1 x 2 (mod m ). Следовательно, предположение неверно, а значит верно обратное. То есть ax 1 +b и ax 2 +b несравнимы по модулю m , если x 1 x 2 (mod m ), что и требовалось доказать.

Кольцо вычетов по модулю 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.

Пункт 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 . Докажите, что: , где р пробегает все простые делители числа а .

Классы вычетов. Системы вычетов

Краткие сведения из теории

Применяя теорему о делении с остатком можно множество целых чисел разбить на ряд классов. Рассмотрим пример. Пусть m = 6. Тогда имеем шесть классов разбиения множества целых чисел по модулю 6:

r = 1;

r = 2;

r = 3;

r = 4;

r = 5;

где через r обозначен остаток от деления целого числа на 6.

Напомним теорему о делении с остатком:

Теорема : Разделить число на число , , с остатком, значит, найти пару целых чисел q и r , таких, что выполняются следующие условия: .

Легко доказывается, что для любых целых чисел а и деление с остатком возможно и числа q и r определяются однозначно. В нашем примере полная система наименьших неотрицательных вычетов есть множество {0, 1, 2, 3, 4, 5}; полная система наименьших положительных вычетов – множество {0, 1, 2, 3, 4, 5}; полная система наименьших по абсолютной величине вычетов – множество {-2,-1, 0, 1, 2, 3}; приведённая система вычетов – множество {1,5}, так как ; фактор-множество

Один из методов выполнения арифметических операций над данными целыми числами основан на простых положениях теории чисел. Идея этого метода состоит в том, что целые числа представляются в одной из непозиционных систем – в системе остаточных классов. А именно: вместо операций над целыми числами оперируют с остатками от деления этих чисел на заранее выбранные простые числа – модули .

Чаще всего числа выбирают из множества простых чисел.

Пусть …, .

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

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

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

Делении целых чисел a и m получается частное q и остаток r , такие что

a = m q + r, 0 r m-1. Остаток r называют ВЫЧЕТ ом по модулю m .

Например, для m = 3 и для m =5 получим:

a = m q + r, m = 3	a = m q + r, m = 5
0 = 3 + 0	0 = 5 + 0
1 = 3 + 1	1 = 5 + 1
2 = 3 + 2	2 = 5 + 2
3 = 3 + 0	3 = 5 + 3
4 = 3 + 1	4 = 5 + 4
5 = 3 + 2	5 = 5 + 0
6 = 3 + 0	6 = 5 + 1
7 = 3 + 1	7 = 5 + 2

Если остаток равен нулю (r =0 ), то говорят, что m делит a нацело (или m кратно a ), что обозначают m a , а числа q и m называют делителями a . Очевидно 1 a и a a . Если a не имеет других делителей, кроме 1 и а , то а – простое число, иначе а называют составным числом. Самый большой положительный делитель d двух чисел a и m называют наибольшим общим делителем (НОД) и обозначают d = (a,m). Если НОД (a,m)= 1 , то a и m не имеют общих делителей, кроме 1 , и называются взаимно простыми относительно друг друга.

Каждому ВЫЧЕТ у r = 0, 1, 2,…, m-1 соответствует множество целых чисел a, b, … Говорят, что числа с одинаковым ВЫЧЕТ ом сравнимы по модулю и обозначают a b(mod m) или (a b) m .

Например, при m = 3 :

Например, при m = 5 :

Числа а , которые сравнимы по модулю m , образуют класс своего ВЫЧЕТа r и определяются как a = m q + r.

Числа а тоже называют ВЫЧЕТами по модулю m . НеотрицательныеВЫЧЕТы а = r (при q=0 ), принимающие значения из интервала , образуют полную систему наименьших вычетов по модулю m.

ВЫЧЕТы а , принимающие значения из интервала [-( ,…,( ] , при нечетном m или из интервала [- при четном m образуют полную систему абсолютно наименьших ВЫЧЕТ ов по модулю m.

Например, при m = 5 классы наименьших вычетов образуют

r = 0, 1, 2, 3, 4, a = -2, -1, 0, 1, 2. Обе приведенные совокупности чисел образуют полные системы вычет ов по модулю 5 .

Класс ВЫЧЕТов , элементы которого взаимно просты с модулем m

называют приведенным. Функция Эйлера определяет сколько ВЫЧЕТов из полной системы наименьших вычетов по модулю m взаимно просты с m . При простом m=p имеем = p-1.

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

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

Пример . Проверить, образуют ли числа 13, 8, - 3, 10, 35, 60 полную систему вычетов по модулю m=6.

Решение : По определению числа образуют полную систему вычетов по модулю m , если их ровно m и они попарно несравнимы по модулюm .

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

Применим теорему о делении с остатком: a = m q + r.

13 = 6 2 + 1 13 1(mod 6); 8 = 6 1 + 2 8 2(mod 6);

3 = 6 (-1) + 3 -3 3(mod 6); 10 = 6 1 + 4 10 4(mod 6);

35 = 6 5 + 5 35 5(mod 6); 60 = 6 10 + 0 60 0(mod 6).

Получили последовательность чисел: 1, 2, 3, 4, 5, 0, их ровно 6, повторений нет и они попарно несравнимы. То есть, они образуют полную систему вычетов по модулю m = 6.

Пример . Заменить наименьшим по абсолютной величине, а также наименьшим положительным вычетом 185 по модулю 16.

Решение. Применим теорему о делении с остатком:

185 = 16 11 + 9 185 9(mod 16).

Пример. Проверить, образуют ли числа (13, -13, 29, -9) приведенную систему вычетов по модулю m=10.

Решение: Всякая приведённая система вычетов по модулю m содержит элементов, где - функция Эйлера. В нашем случае =4, ибо среди натуральных чисел только 1, 3, 7, 9 взаимно просты с 10 и не превосходят его. То есть, возможно, что эти четыре числа составляют искомую систему. Проверим эти числа на их попарную несравнимость: =4, ибо среди натуральных чисел только 1, 3, 7, 9 взаимно просты с 10 и не превосходят его. То есть, возможно, что эти четыре числа составляют искомую систему. Проверим эти числа на их попарную несравнимость:m .

Вариант 1. a = 185, m = 12; Вариант 2. a = 84, m = 9;

Вариант 3. a = 180, m = 10; Вариант 4. a = 82, m = 9;

Вариант 5. a = 85, m = 11; Вариант 6. a = 84, m = 8;

Вариант 7. a = 103, m = 87; Вариант 8. a = 84, m = 16;

Вариант 9. a = 15, m = 10; Вариант 10. a = 81, m = 9;

Вариант 11. a = 85, m = 15; Вариант 12. a = 74, m = 13;

Вариант 13. a = 185, m = 16; Вариант 14. a = 14, m = 9;

Вариант 15. a = 100, m = 11; Вариант 16. a = 484, m = 15;

Вариант 17. a = 153, m = 61; Вариант 18. a = 217, m = 19;

Вариант 19. a = 625, m = 25; Вариант 20. a = 624, m = 25;

Задание 3. Записать полную и приведенную систему наименьших