13. Система вычетов. Полная система вычетов. Приведенная система вычетов. Функция Эйлера. Привести конкретные примеры.
Рассмотрим
множество целых чисел а € Z,
тогда натуральное число m
€ Z
разбивает множество Z
на m
непересекающихся подмножеств следующим
образом. Множество чисел, сравнимых по
модулю числа m,
Аi
= {a
€ Z|a
≡ i
(mod
m)},
i=0,…,m-1,
будем называть классами эквивалентности
по модулю m.
Любое число из класса эквивалентности
по модулю m
будем называть вычетом
по модулю m.
Совокупность вычетов, взятых по одному
из каждого класса эквивалентности,
называется полной
системой вычетов
по модулю m
( в полной системе вычетов, таким образом,
всего m
чисел). Непосредственно сами остатки
при делении на m
называется наименьшими
неотрицательными вычетами и
образуют полную систему вычетов по
модулю m.
Вычет ρ называется абсолютным
наименьшим,
если |ρ| наименьший среди модулей вычетов
данного класса эквивалентности. (Пример:
Пусть m=5.
Тогда 0,1,2,3,4 – наименьшие неотрицательные
вычеты, -2,-1,0,1,2 – абсолютно наименьшие
вычеты. Обе приведенные совокупности
чисел образуют полные системы вычетов
по модулю 5). Приведенной
системой вычетов
по модулю m
называется совокупность всех вычетов
из полной системы, взаимно простых с
модулем m.
Приведенную систему обычно выбирают
из наименьших неотрицательных вычетов.
Приведенная система вычетов по модулю
m
содержит ф(m)
штук вычетов, где ф(m)
– функция Эйлера, по определению равная
количеству чисел, меньших m
и взаимно простых с m.
(Пример:
пусть m
= 42. Тогда приведенная система вычетов
есть: {1,5,11,13,17,19,23,25,29,31,37,41}). Функция
Эйлера ф(а) есть количество чисел из
ряда 0,1,2,…,а-1, взаимно простых с a.
Пусть дано натуральное число ,
представленное в виде его канонического
разложения на простые сомножители
Тогда функция
называется
функцией Эйлера. При этом полагается,
что
Функцию
Эйлера можно также представить в виде
так называемого произведения Эйлера:
где
p — простое число и пробегает все
значения, участвующие в разложении n
на простые сомножители.
15.Таблица Кэли для заданий конечной группы.
Существует удобный способ задания конечной группы в виде таблицы. Она обычно называется таблицей Кели. Все строки таблицы и столбцы помечаются элементами группы, а на пересечении строки, помеченной элементом a, и столбца, помеченного b, ставится ab(либо a+b). Например, для Z5, таблица Кели имеет такой вид(над числами рисуем”_”):
-
1
0
1
2
3
4
0
0
1
2
3
4
1
1
2
3
4
0
2
2
3
4
0
1
3
3
4
0
1
2
4
4
0
1
2
3