Алгебра. Лекция 6. Классы вычетов

1. Лекция 6 Классы вычетов

2. Класс чисел

Целые числа, сравнимые с a по модулю m
(m ϵ N, m>1) образуют класс чисел по модулю m
и он обозначается
a x Z | x a(mod m)
Любое число класса называется вычетом этого
класса по модулю m
Например
Z 6 0,1, 2, 3, 4, 5
0 x Z | x 0(mod 6) 6k | k Z ;
1 x Z | x 1(mod 6) 1 6k | k Z

3. Свойства классов вычетов

1) a a (a a(mod m))
2) a b a b(mod b)
3) Если два класса имеют хотя бы один общий
элемент, то они совпадают
4) По модулю m существует ровно m классов
вычетов 0, 1, 2, ... , m 1

4. Полные и приведённые системы вычетов Определение 1 Полной системой вычетов по модулю m называется совокупность чисел, взятых по одному из к

Полные и приведённые системы вычетов
Определение 1
Полной системой вычетов по модулю m
называется совокупность чисел, взятых по
одному из каждого класса вычетов по модулю m
Пример
• m=6. Так как остатки при делении на 6 могут
быть 0, 1, 2, 3, 4, 5, то по модулю 6 имеется
шесть классов вычетов:
0,1, 2, 3, 4, 5
• 12, 7, 8, -3, 10, 17 – полная система вычетов по
модулю шесть, т.к.
12 0, 7 1, 8 2, 3 3, 10 4, 17 5

5. Теорема 1 (признак полной системы вычетов) Любая система m чисел, попарно не сравнимых по модулю m, является полной системой вычетов по модул

Теорема 1 (признак полной системы вычетов)
Любая система m чисел, попарно не сравнимых
по модулю m, является полной системой
вычетов по модулю m
Доказательство
•По условию числа попарно не сравнимы по
модулю m, т.е. взяты из разных классов
•Т.к. чисел m, то вычет каждого класса
присутствует в системе
•Значит, это система – полная система вычетов по
модулю m

6.

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

7.

Определение 2
Пусть m N
Функцией Эйлера называется функция
натурального аргумента (m), которая
определена как количество натуральных чисел,
не превосходящих m и взаимно простых с m
Примеры
(2) 1, (3) 2, (6) 2
Заметим, что в полной системе вычетов по модулю
m: 1, 2, 3, 4, …, m ровно (m) вычетов, взаимно
простых с m (согласно определению (m) )

8. Определение 3 Приведённой системой вычетов по модулю m называется совокупность вычетов, взятых по одному из каждого класса, взаимно просто

Определение 3
Приведённой системой вычетов по модулю m
называется совокупность вычетов, взятых по
одному из каждого класса, взаимно простого с
модулем
Заметим, что если (a, m)=1, то ( а, m)=1
Примеры
1) 1, 2, 3, 4 – приведенная система вычетов по
модулю 5
2) 1, 3, -3, -1 – приведенная система вычетов по
модулю 10

9. Теорема 3 (признак приведённой системы вычетов) Совокупность чисел, попарно не сравнимых по модулю m и взаимно простых с m, образует приведён

Теорема 3 (признак приведённой системы вычетов)
Совокупность (m) чисел, попарно не сравнимых по
модулю m и взаимно простых с m, образует
приведённую систему вычетов по модулю m
Доказательство
• Поскольку числа попарно не сравнимы, то они взяты из
различных классов
• Т.к. они взаимно просты с модулем, то взяты из классов,
взаимно простых с модулем
• Поскольку их (m) штук, т.е. столько же, сколько
классов вычетов взаимно простых с модулем, то вычет
каждого такого класса присутствует в системе
• Значит, это приведенная система вычетов по модулю m

10. Теорема 4 Пусть . Если и в выражении ax, переменная x пробегает приведённую систему вычетов по модулю m, то и само выражение ax пробегает привед

Теорема 4
Пусть a Z , m N . Если (a, m) 1 и в выражении
ax, переменная x пробегает приведённую
систему вычетов по модулю m, то и само
выражение ax пробегает приведённую систему
вычетов по модулю m

11. Понятие кольца

Не пустое множество К называют кольцом, если на
нём определены две бинарные алгебраические операции
сложения и умножения, т.е. если a, b ϵ K, то (a+b) ϵ K,
a ∙ b ϵ K и выполняются свойства:
1. a, b, c ϵ K a+b=b+a; (a+b)+c=a+(b+c)
2. a ϵ K существует относительно сложения
нейтральный элемент – 0, т.е. a+0=a
3. a ϵ K существует противоположный
(симметричный) элемент – a', т.е. a+a' =0
4. a, b, c ϵ K (a∙b)∙c=a∙(b∙c)
5. a, b,c ϵ K a∙(b+c)=a∙b+b∙c, (a+b)∙c=a∙c+b∙c
Примеры:
N – не кольцо; Z – кольцо; Q – кольцо; R – кольцо

12. Кольцо классов вычетов

Zm - множество классов вычетов по модулю m
Z 6 0,1, 2, 3, 4, 5
В Zm определим операции сложения и умножения:
а b a b
а b a b
Примеры
По модулю 5
• 3 4 2 , т.к. 3 4 7 2 7 2 mod 5
• 2 4 3, т.к. 2·4 = 8 3

13. Теорема 5 Множество классов вычетов по модулю m, относительно сложения и умножения образует коммутативное кольцо с 1

14. Доказательство теоремы 5

1. Сложение классов ассоциативно и коммутативно
а (b c) a (b c) a (b c) (a b) c (a b) c (a b) c
а b a b b a b a
2. Роль нейтрального элемента выполняет класс 0
3. Для каждого класса а противоположным классом
является a , т.е. класс, содержащий a ; a ( a) 0
4. Умножение коммутативно и ассоциативно
a b ab ba b a
a(bc) a(bc) a(bc) (ab)c (ab) c (ab)c
5. Умножение и сложение связаны дистрибутивно
(a b)c (a b)c (a b)c ac bc ac bc ac bc
6. Роль единицы играет класс 1

15. Cвойства функции Эйлера

1. Если р – простое, то ( p) p 1
2. ( p n ) p n 1 ( p 1)
3. Функция Эйлера мультипликативна, т.е.
если (a, b) 1 ,то (ab) (a) (b)
Определение
Функция , определенная на множестве натуральных
чисел, называется мультипликативной, если для любых
взаимно простых натуральных чисел a и b
f (a b) f (a) f (b)

16. Cвойства функции Эйлера

n p1 p2 ... pk
4. Пусть
каноническое разложение
натурального числа, тогда
1
2
k
(n) ( p1 p2 ... pk ) ( p1 ) ( p2 ) ... ( pk )
1
1 1
p1
2
2 1
( p1 1) p2
k
1
k 1
( p2 1) ... pk
2
k
1
1
1
( pk 1) n(1 ) (1 )...(1 )
p1
p2
pk

17. Теорема Эйлера Если , то

Теорема Эйлера
Если m 1 и (a, m) 1 , то
( m)
a
1(mod m)
Леона́рд Э́йлер (нем. Leonhard Euler; 15 апреля 1707, Базель, Швейцария — 7 (18)
сентября 1783, Санкт-Петербург, Российская империя) — швейцарский, немецкий
и российский математик и механик

18. Пьер де Ферма (1601-1665) – французкий математик, один из создателей аналитической геометрии, математического анализа, теории вероятностей и т

Пьер де Ферма (1601-1665) – французкий математик,
один из создателей аналитической геометрии,
математического анализа, теории вероятностей и
теории чисел. По профессии юрист, советник
парламента в Тулузе
Теорема Ферма
Пусть a Z , р – простое.
Если (a, p) 1 ,то a p 1 1(mod p)
Следствие
Для любого целого a и простого p
a p a(mod p)