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

Сентябрь 16, 2022

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

Содержание

2. Класс чисел Целые числа, сравнимые с a по модулю m (m ϵ N, m>1) образуют класс
3. Свойства классов вычетов Если два класса имеют хотя бы один общий элемент, то они совпадают По
4. Полные и приведённые системы вычетов Определение 1 Полной системой вычетов по модулю m называется совокупность чисел,
5. Теорема 1 (признак полной системы вычетов) Любая система m чисел, попарно не сравнимых по модулю m,
6. Теорема 2 Если и x пробегает полную систему вычетов по модулю m, то , где ,
7. Определение 2 Пусть Функцией Эйлера называется функция натурального аргумента , которая определена как количество натуральных чисел,
8. Определение 3 Приведённой системой вычетов по модулю m называется совокупность вычетов, взятых по одному из каждого
9. Теорема 3 (признак приведённой системы вычетов) Совокупность чисел, попарно не сравнимых по модулю m и взаимно
10. Теорема 4 Пусть . Если и в выражении ax, переменная x пробегает приведённую систему вычетов по
11. Понятие кольца Не пустое множество К называют кольцом, если на нём определены две бинарные алгебраические операции
12. Кольцо классов вычетов Zm - множество классов вычетов по модулю m В Zm определим операции сложения
13. Теорема 5 Множество классов вычетов по модулю m, относительно сложения и умножения образует коммутативное кольцо с
14. Доказательство теоремы 5 Сложение классов ассоциативно и коммутативно 2. Роль нейтрального элемента выполняет класс 3. Для
15. Cвойства функции Эйлера Если р – простое, то Функция Эйлера мультипликативна, т.е. если ,то Определение Функция
16. 4. Пусть каноническое разложение натурального числа, тогда Cвойства функции Эйлера
17. Теорема Эйлера Если , то Леона́рд Э́йлер (нем. Leonhard Euler; 15 апреля 1707, Базель, Швейцария —
19. Скачать презентацию

Слайд 2

Класс чисел
Целые числа, сравнимые с a по модулю m
(m ϵ

N, m>1) образуют класс чисел по модулю m и он обозначается
Любое число класса называется вычетом этого класса по модулю m
Например

Слайд 3

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

Если два класса имеют хотя бы один общий

элемент, то они совпадают
По модулю m существует ровно m классов вычетов

Слайд 4

Полные и приведённые системы вычетов Определение 1 Полной системой вычетов по модулю

m называется совокупность чисел, взятых по одному из каждого класса вычетов по модулю m

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

Слайд 5

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

сравнимых по модулю m, является полной системой вычетов по модулю m

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

Слайд 6

Теорема 2
Если и x пробегает полную систему вычетов по модулю m,

то , где , тоже пробегает полную систему вычетов по модулю m

Слайд 7

Определение 2
Пусть
Функцией Эйлера называется функция натурального аргумента ,

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

Слайд 8

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

взятых по одному из каждого класса, взаимно простого с модулем

Заметим, что если (a, m)=1, то ( , m)=1
Примеры
1) 1, 2, 3, 4 – приведенная система вычетов по модулю 5
2) 1, 3, -3, -1 – приведенная система вычетов по модулю 10

Слайд 9

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

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

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

Слайд 10

Теорема 4 Пусть . Если и в выражении ax, переменная x

пробегает приведённую систему вычетов по модулю m, то и само выражение ax пробегает приведённую систему вычетов по модулю m

Слайд 11

Понятие кольца
Не пустое множество К называют кольцом, если на нём определены

две бинарные алгебраические операции сложения и умножения, т.е. если a, b ϵ K, то (a+b) ϵ K, a ∙ b ϵ K и выполняются свойства:
∀ a, b, c ϵ K a+b=b+a; (a+b)+c=a+(b+c)
∀ a ϵ K существует относительно сложения нейтральный элемент – 0, т.е. a+0=a
∀ a ϵ K существует противоположный (симметричный) элемент – a', т.е. a+a' =0
∀ a, b, c ϵ K (a∙b)∙c=a∙(b∙c)
∀ 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
В Zm

определим операции сложения и умножения:
Примеры
По модулю 5
, т.к.
, т.к.

Слайд 13

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

образует коммутативное кольцо с 1

Слайд 14

Доказательство теоремы 5
Сложение классов ассоциативно и коммутативно
2. Роль нейтрального элемента выполняет

класс
3. Для каждого класса противоположным классом является , т.е. класс, содержащий ;
4. Умножение коммутативно и ассоциативно
5. Умножение и сложение связаны дистрибутивно
6. Роль единицы играет класс

Слайд 15

Cвойства функции Эйлера
Если р – простое, то
Функция Эйлера мультипликативна, т.е.
если

,то
Определение
Функция , определенная на множестве натуральных чисел, называется мультипликативной, если для любых взаимно простых натуральных чисел a и b

Слайд 16

4. Пусть каноническое разложение натурального числа, тогда
Cвойства функции Эйлера

Слайд 17

Теорема Эйлера Если , то
Леона́рд Э́йлер (нем. Leonhard Euler; 15 апреля

1707, Базель, Швейцария — 7 (18) сентября 1783, Санкт-Петербург, Российская империя) — швейцарский, немецкий и российский математик и механик

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

Содержание

Класс чиселЦелые числа, сравнимые с a по модулю m (m ϵ

Свойства классов вычетов Если два класса имеют хотя бы один общий

Полные и приведённые системы вычетов Определение 1 Полной системой вычетов по модулю

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

Теорема 2Если и x пробегает полную систему вычетов по модулю m,

Определение 2 Пусть Функцией Эйлера называется функция натурального аргумента ,

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

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

Теорема 4 Пусть . Если и в выражении ax, переменная x

Понятие кольцаНе пустое множество К называют кольцом, если на нём определены

Кольцо классов вычетовZm - множество классов вычетов по модулю mВ Zm

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

Доказательство теоремы 5 Сложение классов ассоциативно и коммутативно2. Роль нейтрального элемента выполняет

Cвойства функции ЭйлераЕсли р – простое, тоФункция Эйлера мультипликативна, т.е. если

4. Пусть каноническое разложение натурального числа, тогдаCвойства функции Эйлера

Теорема Эйлера Если , тоЛеона́рд Э́йлер (нем. Leonhard Euler; 15 апреля

Похожие презентации