- •Модуль 1. Элементы теории чисел Глава 1.1. Целые числа §1.1.1. Теория делимости
- •Упражнения и задачи
- •§1.1.2 Наибольший общий делитель. Алгоритм Евклида
- •Упражнения и задачи
- •§1.1.3 Теорема о линейном представлении наибольшего общего делителя
- •Упражнения и задачи
- •§1.1.4 Наименьшее общее кратное
- •Упражнения и задачи
- •§1.1.5 Простые числа
- •Упражнения и задачи
- •§1.1.6 Основная теорема арифметики кольца целых чисел
- •Упражнения и задачи
- •§1.1.7 Целая часть числа
- •Упражнения и задачи
- •§1.1.8 Функция Эйлера
- •Упражнения и задачи
- •§1.1.9 Сравнения
- •Упражнения и задачи
- •§1.1.10 Полная система вычетов
- •Упражнения и задачи
- •§1.1.11 Приведенная система вычетов
- •Упражнения и задачи
- •§1.1.12 Теорема Эйлера
- •Упражнения и задачи
- •§1.1.13 Кольцо классов вычетов
- •Упражнения и задачи
- •§1.1.14 Решение сравнений
- •Упражнения и задачи
- •Контрольная работа №1 по теме “Целые числа”
- •I вариант
- •II вариант
- •III вариант
- •IV вариант
- •V вариант
- •VI вариант
- •VII вариант
- •VIII вариант
- •IX вариант
- •X вариант
- •XI вариант
- •XII вариант
- •XIII вариант
- •XIV вариант
- •XV вариант
- •XVI вариант
- •XVII вариант
- •XVIII вариант
- •XIX вариант
- •XX вариант
- •XXI вариант
- •XXII вариант
- •XXIII вариант
- •XXIV вариант
- •XXV вариант
- •XXVI вариант
- •XVII вариант
- •XXVIII вариант
- •XXIX вариант
- •XXX вариант
- •Глава 1.2. Комплексные числа и комплексные функции
- •§1.2.1 Алгебраическая форма комплексного числа
- •Упражнения и задачи
- •§1.2.2 Комплексно сопряженные числа
- •Упражнения и задачи
- •§1.2.3 Геометрическая интерпретация комплексных чисел
- •Упражнения и задачи
- •§1.2.4 Тригонометрическая форма комплексного числа
- •Упражнения и задачи
- •§1.2.5 Формула Муавра
- •Упражнения и задачи
- •§1.2.6 Модуль комплексного числа
- •Упражнения и задачи
- •§1.2.7 Извлечение корня из комплексного числа
- •Упражнения и задачи
- •§1.2.8 Корни из 1
- •Упражнения и задачи
- •§1.2.9 Показательная форма записи комплексного числа
- •Упражнения и задачи
§1.1.10 Полная система вычетов
Множество всех чисел, сравнимых с числом апо модулютбудем обозначать черезт.е.
или
Это множество называетсяклассом вычетовчислаапо модулют. Легко видеть, что два класса вычетов либо не пересекаются, либо совпадают. Всем числам класса по определению соответствует один и тот же остаток при делении нат, следовательно, таких классовтштук. Взяв из каждого класса по одному представителю, получим полную систему представителей классов вычетов по модулют. Любое число класса называетсявычетомпо модулютпо отношению ко всем числам того же класса.
В качестве примера полной системы представителей классов вычетов по модулю т(коротко: полная система вычетов) можно взять наименьшие неотрицательные вычеты 0, 1, 2,...,т-1. Можно взять наименьшие вычеты по абсолютной величине, т.е. в случае нечетноготчисла
в случае четного т- какое-либо из двух множеств:
Теорема.Система вычетов по модулютполна тогда и только тогда, когда в ней ровнотчисел, и числа попарно не сравнимы по модулют. ■
Теорема.Еслиаитвзаимно просты ихпробегает полную систему вычетов по модулют, то ипробегает также полную систему вычетов по модулют;b– любое целое число.
Доказательство:Еслихпробегает полную систему вычетов по модулют, то принимаеттзначений, поэтому и чисел видаполучаетсятштук. Еслито
Отсюда следует, что если то иПолученное множество содержит ровнотчисел, попарно несравнимых, т.е. является полной системой вычетов. ■
Упражнения и задачи
Показать, что числа 25, -20, 16, 46, -21, 18, 37, -17 образуют полную систему вычетов по модулю
Показать, что числа 24, 18, -19, 37, 38, -23, -32, 5, 41, -35, -33 образуют полную систему вычетов по модулю т = 11.
Найти наименьшие неотрицательные, наименьшие по абсолютной величине неположительные и абсолютно наименьшие вычеты чисел 24, 14, 25, 37, -8, -19, -40 по модулю 6. Какие числа из данных принадлежат к одному и тому же классу вычетов?
Доказать, что
Если два класса имеют хотя бы один общий элемент, то они совпадают. Доказать.
Наименьший неотрицательный вычет класса по модулютравен остатку от деленияанат. Доказать.
Числа классапо модулютобразуютkклассов по модулюkm, а именно классыДоказать.
§1.1.11 Приведенная система вычетов
Если т.е.а иbпредставляют один и тот же класс вычетов, тот.е. все числа одного класса либо имеют общий множитель стодновременно, либо одновременно же не имеют.
Класс вычетов по модулю т, все числа которого взаимно просты ст, называетсяпримитивным.
Приведенной системой вычетовпо модулютназывается множество, состоящее из представителей примитивных классов вычетов, взятых по одному из каждого класса.
Среди чисел 0, 1, 2,..., т-1 взаимно простых стчиселпоэтому и примитивных классов
Пример.Приведенную систему вычетов по модулю 12 образуют числа 19, 23, 25, -19 или 1, 5, 7, 11, или -5, -1, 1, 5.
Приведенную систему вычетов по модулю 42 составляют числа 1, 5, 11, 13, 17, 19, 23, 25, 29, 31, 37, 41.
Теорема.Система вычетов по модулютявляется приведенной тогда и только тогда, когда в нейчисел; все числа системы взаимно просты сти все они попарно не сравнимы по модулют. ■
Теорема.Еслиихпробегает приведенную систему вычетов по модулют, тоахтакже пробегает приведенную систему вычетов по модулют.
Доказательство:Пусть– приведенная система вычетов по модулют. Тогда числавсе взаимно просты сти ихсштук. Пустьтогда в силу того, что, получима это неверно. Следовательно,Аналогично можно убедиться, что все пары чиселине сравнимы по модулютдляТаким образом, эти числа образуют приведенную систему вычетов. ■