В частности, будем иметь (p a) = p a - p a-1 , (p) = p-1.
Примеры. (60) = 60
(81) = 81-27 = 54
Мультипликативная функция
Функция (а) называется мультипликативной, если она удовлетворяет двум следующим условиям:
Эта функция определена для всех целых положительных a и не равна нулю по меньшей мере при одном таком a.
Для любых положительных взаимно простых a 1 и a 2 имеем:
(а 1 a 2) = (а 1) (а 2) .
Основные понятия теории сравнений
Свойства сравнений
Мы будем рассматривать целые числа в связи с остатками от деления их на данное целое положительное m, которое назовём модулем.
Каждому целому числу отвечает определённый остаток от деления его на m. Если двум целым a и b отвечает один и тот же остаток r, то они называются равноостаточными по модулю m.
Сравнимость чисел a и b по модулю m записывается:
Сравнимость чисел a и b по модулю m равносильна:
Возможности представить a в виде a = b + mt, где t - целое.
Делимости a b на m.
Действительно, из a b (mod m) следует
a = mq + r, b = mq 1 + r, 0<= r откуда a - b = m (q - q 1), a = b + mt, t = q - q 1 . Обратно, из a = b + mt, представляя b в виде b = mq 1 + r , 0 <=r выводим a = mq + r, q = q 1 + t , т.е. a b (mod m). Оба утверждения доказаны. Два числа, сравнимые с третьим, сравнимы между собой. Сравнения можно почленно складывать. Действительно, пусть A 1 b 1 (mod m) , a 2 b 2 (mod m) , …, a k b k (mod m) (1). Тогда a 1 = b 1 + mt 1 , a 2 = b 2 + mt 2 , …, a k = b k + mt k (2), Откуда a 1 + a 2 + … + a k = b 1 + b 2 + … + b k + m (t 1 + t 2 + … + t k), или a 1 + a 2 + … + a k b 1 + b 2 + … + b k (mod m). Сравнения можно почленно перемножать. Рассмотрим (1) и (2). Перемножая почленно равенства (2), получим: a 1 a 2 …a k b 1 b 2 …b k + mN, где N - целое. Отсюда: a 1 a 2 …a k b 1 b 2 …b k (mod m). Обе части сравнения можно возвести в одну и ту же степень. Обе части сравнения можно умножить на одно и то же целое число. Действительно, перемножив сравнение a b (mod m) с очевидным сравнением k k (mod m), получим ak bk (mod m). Обе части сравнения можно разделить на их общий делитель, если последний взаимно прост с модулем. Действительно, из a b (mod m), a = a 1 d , b = b 1 d , (d, m) = 1 следует, что разность a - b, равная (a 1 - b 1)d, делится на m, т. е. a 1 b 1 (mod m) . Числа равноостаточные, или, что то же самое, сравнимые по модулю m, образуют класс чисел по модулю m. Из такого определения следует, что всем числам класса отвечает один и тот же остаток r, и мы получим все числа класса, если в форме mq + r заставим q пробегать все целые числа. Соответственно m различным значениям r имеем m классов чисел по модулю m. Любое число класса называется вычетом по модулю m по отношению ко всем числам того же класса. Вычет, получаемый при q = 0, равный самому остатку r, называется наименьшим неотрицательным вычетом. Взяв от каждого класса по одному вычету, получим полную систему вычетов по модулю m. Чаще всего в качестве полной системы вычетов употребляют наименьшие неотрицательные вычеты 0, 1, ..., m-1 или также абсолютно наименьшие вычеты. Последние, как это следует из вышеизложенного, в случае нечетного m представляются рядом 1, 0, 1, ..., а в случае чётного m каким-либо из двух рядов 1, 0, 1, ..., 1, 0, 1, ..., . Любые m чисел, попарно несравнимые по модулю m, образуют полную систему вычетов по этому модулю. Действительно, будучи несравнимы, эти числа тем самым принадлежат к различным классам, а так как их m, т.е. столько же, сколько и классов, то в каждый класс наверно попадёт по одному числу. Если (a, m) = 1 и x пробегает полную систему вычетов по модулю m, то ax + b, где b - любое целое, тоже пробегает полную систему вычетов по модулю m. Действительно, чисел ax +b будет столько же, сколько и чисел x, т.е. m. Согласно предыдущему утверждению остаётся, следовательно, только показать, что любые два числа ax 1 + b и ax 2 + b, отвечающие несравнимым x 1 и x 2 , будут сами несравнимы по модулю m. Но допустив, что ax 1 + b ax 2 + b (mod m), мы придём к сравнению ax 1 = ax 2 (mod m), откуда, вследствие (a, m) = 1, получим x 1 x 2 (mod m), что противоречит предположению о несравнимости чисел x 1 и x 2 . Числа одного и того же класса по модулю m имеют с модулем один и тот же общий наибольший делитель. Особенно важны классы, для которых этот делитель равен единице, т.е. классы, содержащие числа, взаимно простые с модулем. Взяв от каждого такого класса по одному вычету, получим приведённую систему вычетов по модулю m. Приведённую систему вычетов, следовательно, можно составить из чисел полной системы, взаимно простых с модулем. Обыкновенно приведённую систему вычетов выделяют из системы наименьших неотрицательных вычетов: 0, 1, ..., m-1. Так как среди этих чисел число взаимно простых с m есть (m), то число чисел приведённой системы, равно как и число классов, содержащих числа, взаимно простые с модулем, есть (m). Пример. Приведённая система вычетов по модулю 42 будет 1, 5, 11, 13, 17, 19, 23, 25, 29, 31, 37, 41. Любые (m) чисел, попарно несравнимые по модулю m и взаимно простые с модулем, образуют приведённую систему вычетов по модулю m. Действительно, будучи несравнимыми и взаимно простыми с модулем, эти числа тем самым принадлежат к различным классам, содержащим числа, взаимно простые с модулем, а так как их (m), т.е. столько же, сколько и классов указанного вида, то в каждый класс наверно попадёт по одному числу. Если (a, m) = 1 и x пробегает приведённую систему вычетов по модулю m, то ax тоже пробегает приведённую систему вычетов по модулю m. Действительно, чисел ax будет столько же, сколько и чисел x, т.е. (m). Согласно предыдущему свойству остаётся, следовательно, только показать, что числа ax по модулю m несравнимы и взаимно просты с модулем. Первое следует из свойства сравнений (если сравнение имеет место по модулю m, то оно имеет место и по модулю d, равному любому делителю числа m) для чисел более общего вида ax + b, второе же следует из (a, m) = 1, (x, m) = 1. Теорема Эйлера (2. 5. 3. 1). При m>1 и (a, m) = 1 имеем a (m) 1 (mod m). Доказательство. Действительно, если x пробегает приведённую систему вычетов x = r 1 , r 2 , ..., r c ; c = (m), составленную из наименьших неотрицательных вычетов, то наименьшие неотрицательные вычеты 1 , 2 , ..., с чисел ax будут пробегать ту же систему, но расположенную, вообще говоря, в ином порядке (1). Перемножая почленно сравнения ar 1 1 (mod m), ar 2 2 (mod m), ..., ar c c (mod m), получим а с 1 (mod m). Теорема Ферма (2. 5. 3. 2). При p простом и а, не делящимся на p, имеем a p-1 1 (mod p). (2) Доказательство. Эта теорема является следствием теоремы Эйлера при m = p. Теореме Ферма можно придать более удобную форму, умножая обе части сравнения (2) на а, получим сравнение a p a (mod p), справедливое уже при всех целых а, так как оно верно и при а, кратном p. Теорема доказана. Теорема (2. 5. 3. 3). Если n = pq, (p и q - отличные друг от друга простые числа), то (n) = (p-1)(q-1). Теорема (2. 5. 3. 4). Если n = pq, (p и q отличные друг от друга простые числа) и x простое относительно p и q, то x (n) = 1 (mod n). Как показано в §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
. Извлечение квадратных корней из комплексных чисел в алгебраической форме. Wikimedia Foundation
.
2010
.
Приведённая система вычетов
- часть полной системы вычетов (См. Полная система вычетов), состоящая из чисел взаимно простых с модулем m. П. с. в. содержит φ(m) чисел [φ(m) число чисел, взаимно простых с m и меньших m]. Всякие φ(m) чисел, не сравнимые по модулю m и… … Большая советская энциклопедия
Приведенная система вычетов
- Приведённая система вычетов по модулю m набор, составленный из всех чисел полной системы вычетов по модулю m, взаимно простых с m. Приведённая система вычетов по модулю m состоит из φ(m) чисел, где φ(m) функция Эйлера. В качестве приведённой… … Википедия
Мультипликативная группа кольца вычетов
- Приведённая система вычетов по модулю m множество всех чисел полной системы вычетов по модулю m, взаимно простых с m. Приведённая система вычетов по модулю m состоит из φ(m) чисел, где φ(·) функция Эйлера. В качестве приведённой системы вычетов… … Википедия
Функция Эйлера
- Не следует путать с функцией распределения простых чисел. Первая тысяча значений Функция Эйлера φ(n) мультипликативная … Википедия
Сравнение по модулю
- Сравнение по модулю натурального числа n в теории чисел отношение эквивалентности на кольце целых чисел, связанное с делимостью на n. Факторкольцо по этому отношению называется кольцом вычетов. Совокупность соответствующих тождеств и… … Википедия
Конечная группа
- Симметрия снежинки связана с группой поворотов на угол, кратный 60° Конечная группа алгебраическая группа, содержащая конечное число элементов (это число называется её порядком). Далее группа предполагается мультипликативной, то есть операция в… … Википедия
Четверная группа Клейна
- Четверная группа Клейна группа четвёртого порядка, играет важную роль в высшей алгебре. Содержание 1 Определение 2 Обозначение 3 … Википедия
Кольцо вычетов по модулю
n
обозначают
или
. Его мультипликативную группу, как и в общем случае групп обратимых элементов
колец, обозначают
∗
×
×
. Чтобы понять структуру группы
, можно рассмотреть частный случай
, где
- простое число, и обобщить его. Рассмотрим простейший случай, когда
, то есть
. Теорема:
- циклическая группа.
Пример
: Рассмотрим группу Для рассмотрения общего случая необходимо определение примитивного корня
.
Примитивный корень по простому модулю
- это число, которое вместе со своим классом вычетов порождает группу
. В случае целого модуля
определение такое же. Структуру группы определяет следующая теорема: Если p - нечётное простое число и l - целое положительное, то существуют примитивные корни по модулю
, то есть
- циклическая группа. Приведённая система вычетов по модулю
состоит из
классов вычетов:
.
Относительно определённого для классов вычетов умножения они образуют группу, причём
и
взаимно обратны (то есть
⋅
),
а
и
обратны сами себе. Запись
означает «циклическая группа порядка n». На сложности, Ферма, Хули,
. Уоринг сформулировал теорему Вильсона, а Лагранж её доказал. Эйлер предположил существование примитивных корней по модулю простого числа. Гаусс это доказал. Артин выдвинул свою гипотезу
о существовании и количественной оценке простых чисел, по модулю которых заданное целое число является первообразным корнем. Брауэр внес вклад в исследование проблемы существования наборов последовательных целых чисел, каждое из которых - k-ая степень по модулю p. Билхарц доказал аналог гипотезы Артина. Хули доказал гипотезу Артина с предположением справедливости расширенной гипотезы Римана в полях алгебраических чисел.Вычеты. Полная и приведенная системы вычетов
Теоремы Эйлера и Ферма
Смотреть что такое "Приведённая система вычетов" в других словарях:
Простейший случай
Общий случай
Пример
Структура группы
Структура группы
(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
Применение
Примечания
Литература
