Кольцо вычетов по модулю n обозначают или . Его мультипликативную группу, как и в общем случае групп обратимых элементов колец, обозначают ∗ × × .
Простейший случай
Чтобы понять структуру группы , можно рассмотреть частный случай , где - простое число, и обобщить его. Рассмотрим простейший случай, когда , то есть .
Теорема: - циклическая группа.
Пример : Рассмотрим группу
= {1,2,4,5,7,8} Генератором группы является число 2. ≡ ≡ ≡ ≡ ≡ ≡ Как видим, любой элемент группы может быть представлен в виде , где ≤ℓφ . То есть группа - циклическая.Общий случай
Для рассмотрения общего случая необходимо определение примитивного корня . Примитивный корень по простому модулю - это число, которое вместе со своим классом вычетов порождает группу .
Примеры: 2 11 ; 8 - примитивный корень по модулю 11 ; 3 не является примитивным корнем по модулю 11 .В случае целого модуля определение такое же.
Структуру группы определяет следующая теорема: Если p - нечётное простое число и l - целое положительное, то существуют примитивные корни по модулю , то есть - циклическая группа.
Пример
Приведённая система вычетов по модулю состоит из классов вычетов: . Относительно определённого для классов вычетов умножения они образуют группу, причём и взаимно обратны (то есть ⋅ ), а и обратны сами себе.
Структура группы
Запись означает «циклическая группа порядка n».
| × | φ | λ | Генератор группы | × | φ | λ | Генератор группы | × | φ | λ | Генератор группы | × | φ | λ | Генератор группы | |||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 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 |
Применение
На сложности, Ферма, Хули, . Уоринг сформулировал теорему Вильсона, а Лагранж её доказал. Эйлер предположил существование примитивных корней по модулю простого числа. Гаусс это доказал. Артин выдвинул свою гипотезу о существовании и количественной оценке простых чисел, по модулю которых заданное целое число является первообразным корнем. Брауэр внес вклад в исследование проблемы существования наборов последовательных целых чисел, каждое из которых - k-ая степень по модулю p. Билхарц доказал аналог гипотезы Артина. Хули доказал гипотезу Артина с предположением справедливости расширенной гипотезы Римана в полях алгебраических чисел.
Примечания
Литература
- Айерлэнд К., Роузен М. Классическое введение в современную теорию чисел. - М. : Мир, 1987.
- Алферов А.П., Зубов А.Ю., Кузьмин А.С. Черемушкин А.В. Основы криптографии. - Москва: «Гелиос АРВ», 2002.
- Ростовцев А.Г., Маховенко Е.Б. Теоретическая криптография. - Санкт-Петербург: НПО «Профессионал», 2004.
Обычно в качестве полной системы вычетов по модулю m берутся наименьшие неотрицательные вычеты
0,1,...,m − 1или абсолютно наименьшие вычеты, состоящие из чисел
,в случае нечётного m и чисел
в случае чётного m .
См. также
Литература
- И. М. Виноградов Основы теории чисел . - М.-Л.: Гос. изд. технико-теоретической литературы, 1952. - 180 с.
Wikimedia Foundation . 2010 .
Смотреть что такое "Полная система вычетов" в других словарях:
По модулю m, любая совокупность целых чисел, содержащая по одному числу из каждого класса чисел по модулю m (два целых числа а и b принадлежат одному классу по модулю m, если а b делится на m; см. Вычет). В качестве П. с. в. чаще всего… …
По модулю т любой набор из тнесравнимых между собой по модулю тцелых чисел. Обычно в качестве П. с. в. по модулю тберутся наименьшие неотрицательные вычеты 0, 1, . . ., т 1 или абсолютно наименьшие вычеты, состоящие из чисел 0, +1, . . ., в… … Математическая энциклопедия
Часть полной системы вычетов (См. Полная система вычетов), состоящая из чисел взаимно простых с модулем m. П. с. в. содержит φ(m) чисел [φ(m) число чисел, взаимно простых с m и меньших m]. Всякие φ(m) чисел, не сравнимые по модулю m и… … Большая советская энциклопедия
Сравнение по модулю натурального числа n в теории чисел отношение эквивалентности на кольце целых чисел, связанное с делимостью на n. Факторкольцо по этому отношению называется кольцом вычетов. Совокупность соответствующих тождеств и… … Википедия
В теории чисел сравнение[уточнить] по модулю натурального числа n задаваемое означенным числом отношение эквивалентности на множестве целых чисел, связанное с делимостью на него. Факторпространство по этому отношению называется «кольцом… … Википедия
Симметрия снежинки связана с группой поворотов на угол, кратный 60° Конечная группа алгебраическая группа, содержащая конечное число элементов (это число называется её порядком). Далее группа предполагается мультипликативной, то есть операция в… … Википедия
Функция, к рая может быть представлена степенным рядом. Исключит, важность класса А. ф. определяется следующим. Во первых, этот класс достаточно ш и р о к: он охватывает большинство функций, встречающихся в основных вопросах математики и ее… … Математическая энциклопедия
I Содержание: I. Начальное народное образование вообще. II. Начальное народное образование за границей: Австро Венгрия, Англия, Бельгия, Болгария, Германия, Голландия, Дания, Испания, Италия, Норвегия, Португалия, Румыния, Сербия,… … Энциклопедический словарь Ф.А. Брокгауза и И.А. Ефрона
- — родился 26 мая 1799 г. в Москве, на Немецкой улице в доме Скворцова; умер 29 января 1837 г. в Петербурге. Со стороны отца Пушкин принадлежал к старинному дворянскому роду, происходившему, по сказанию родословных, от выходца "из… … Большая биографическая энциклопедия
Совокупность замкнутых формул логики предикатов 1 й ступени. Э. т. Th(К) класса К алгебраических систем сигнатуры наз. совокупность всех замкнутых формул логики предикатов 1 й ступени сигнатуры истинных на всех системах из класса К. Если класс… … Математическая энциклопедия
ОСНОВНЫЕ СВЕДЕНИЯ ИЗ ТЕОРИИ
6. 1. Определение 1.
Классом чисел по данному модулю т называется множество всех тех и только тех целых чисел, которые при делении на т имеют один и тот же остаток r, то есть сравнимых по модулю т (т ÎN, т > 1).
Обозначение класса чисел, имеющих остаток r : .
Каждое число из класса называется вычетом по модулю т, а сам класс называется классом вычетов по модулю т.
6. 2. Свойства множества классов вычетов по модулю т :
1) всего по модулю т будет т классоввычетов: Z т = { , , , … , };
2) каждый класс содержит бесконечное множество целых чисел (вычетов) вида: = {a = mq + r / q ÎZ, 0£ r < m }
3) "а Î : а º r (mod m );
4) "а, b Î : а º b (mod m ), то есть любые два вычета, взятые из одного класса, сравнимы по модулю т ;
5) "а Î , "b Î : а b (mod m ), то есть никакие два вычета; взятые из разных классов, несравнимы по модулю т .
6. 3. Определение 3.
Полной системой вычетов по данному модулю т называется любой набор т чисел, взятых по одному и только по одному из каждого класса вычетов по модулю т.
Пример: если m = 5, то {10, 6, – 3, 28, 44} – это полная система вычетов по модулю 5 (причём, не единственная!)
В частности,
множество {0, 1, 2, 3, … , m –1} – это система наименьших неотрицательных вычетов;
множество {1, 2, 3, … , m –1, т }– это система наименьших положительных вычетов.
6. 4. Отметим, что:
если {х
1 , х
2 , … , х т
} – полная система вычетов по модулю т
, то 
.
6. 5. Теорема 1.
Если {х 1 , х 2 , … , х т } – полная система вычетов по модулю т , "а, b Î Z и (а, т ) = 1, – то система чисел {ах 1 + b , ах 2 + b , … , ах т + b }также образует полную систему вычетов по модулю т .
6. 6. Теорема 2.
Все вычеты одного и того же класса вычетов по модулю т имеют с числом т один и тот же наибольший общий делитель: "а, b Î Þ (а; т ) = (b; т ).
6. 7. Определение 4.
Класс вычетов по данному модулю т называется взаимно простым с модулем т , если хотя бы один вычет этого класса – взаимно простой с т.
Заметим, что в этом случае по теореме 2 все числа этого класса будут взаимно простыми с модулем т.
6. 8. Определение 5.
Приведённой системой вычетов по данному модулю т называется система вычетов, взятых по одному и только по одному из каждого класса, взаимно простого с модулем т.
6. 9. Отметим, что:
1) приведённая система вычетов по модулю т содержит j(т ) чисел {х 1 , х 2 ,…, };
2) : 
.
3) " х i : (х i , m ) = 1;
Пример : Пусть по модулю т = 10 имеется 10классоввычетов:
Z 10 = { , , , , , , , , , }– множество классоввычетов по модулю 10. Полная система вычетов по mod 10 будет, например, такая: {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}.
Множество классов вычетов, взаимно простых с модулем m= 10: { , , , }(j(10) = 4).
Приведённая система вычетов по модулю10 будет, например,
{1, 3, 7, 9}, или {11, 43, – 5, 17}, или { – 9, 13, – 5, 77} и т.д. (везде j(10) = 4 числа).
6.10. Практически: чтобы составить одну из возможных приведённых систем вычетов по mod m , нужно из полной системы вычетов по mod m выбрать те вычеты, которые взаимно простые с т. Таких чисел будет j(т ).
6.11. Теорема 3.
Если {х 1 , х 2 ,…, } – приведённая система вычетов по модулю т и
(а , m ) = 1, – то система чисел {ах 1 , ах 2 , … , ах j (т) } также образует
приведённую систему вычетов по модулю т .
6.12. Определение 6.
Суммой ( Å ) классов вычетов и + b, равных сумме любых двух вычетов, взятых по одному из каждого данного класса и : Å = , где "а Î , "b Î .
6.13. Определение 7.
Произведением ( Ä ) классов вычетов и по модулю т называется класс вычетов , то есть класс вычетов, состоящий из чисел а ´ b, равных произведению любых двух вычетов, взятых по одному из каждого данного класса и : Ä = , где "а Î , "b Î .
Таким образом, в множестве классов вычетов по модулю т : Z т = { , , ,…, } определены две алгебраические операции – "сложения" и "умножения".
6.14. Теорема 4.
Множество классов вычетов Z т по модулю т является ассоциативно-коммутативным кольцом с единицей:
< Z т , +, · > = < { , , ,…, }, +, · > – кольцо.
ТИПОВЫЕ ЗАДАЧИ
1. Составить по модулю т = 9:
1) полную систему наименьших положительных вычетов;
2) полную систему наименьших неотрицательных вычетов;
3) произвольную полную систему вычетов;
4) полную систему наименьших по абсолютной величине вычетов.
Ответ :1) {1, 2, 3, 4, 5, 6, 7, 8, 9}; 2) {0, 1, 2, 3, 4, 5, 6, 7, 8};
2. Составить приведённую систему вычетов по модулю т = 12.
Решение.
1) Составим полную систему наименьших положительных вычетов по модулю т = 12:
{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12} (всего т = 12 чисел).
2) Вычеркнем из этой системы числа, не взаимно простые с числом 12:
{1, 2 , 3 , 4 , 5, 6 , 7, 8 , 9 , 10 , 11, 12 }.
3) Оставшиеся числа, взаимно простые с числом 12, образуют искомую приведённую систему вычетов по модулю т = 12 (всего j(т ) = j(12) = 4 числа).
Ответ: {1, 5, 7, 11} – приведённая система вычетов по модулю т = 12.
130. Составьте 1) полную систему наименьших положительных вычетов; 2) полную систему наименьших неотрицательных вычетов; 3) произвольную систему вычетов; 4) полную систему наименьших по абсолютной величине вычетов; 5) приведённую систему вычетов: а) по модулю m = 6; б) по модулю m = 8.
131. Является ли множество {9, 2, 16, 20, 27, 39, 46, 85} полной системой вычетов по модулю 8 ?
132 По какому модулю множество{20, – 4, 22, 18, – 1}является полной системой вычетов?
133. Составьте приведённую систему вычетов по модулю m , если а) m = 9; б) m = 24; в) m = 7. Сколько чисел должна содержать такая система?
134. Сформулируйте основные свойства полной системы вычетов и приведённой системы вычетов по модулю m .
135. Какими элементами отличаются приведённая и полная системы наименьших неотрицательных вычетов по простому модулю?
136. При каком условии числа а и – а принадлежат одному классу вычетов по модулю m ?
137. Каким классам вычетов по модулю 8 принадлежат все простые числа р ³ 3 ?
138. Образует ли множество чисел {0, 2 0 , 2 1 , 2 2 , ... , 2 9 } полную систему вычетов по модулю 11 ?
139. Скольким классам вычетов по модулю 21 принадлежат все вычеты из одного класса вычетов по модулю 7 ?
140. Множество целых чисел Z распределите по классам вычетов по модулю 5. Составьте таблицы сложения и умножения в образовавшемся множестве классов вычетов Z 5 . Является ли множество Z 5: а) группой с операцией сложения классов? б) группой с операцией умножения классов?
§ 7. ТЕОРЕМА ЭЙЛЕРА. МАЛАЯ ТЕОРЕМА ФЕРМА
ОСНОВНЫЕ СВЕДЕНИЯ ИЗ ТЕОРИИ
7. 1. Теорема 1.
Если а
ÎZ
, т
ÎN, т
>1 и
(а
; т
) = 1 , – то в бесконечной последовательности степеней а
1 , а
2 , а
3 , ... , а
s , … , а
t , … найдутся хотя бы две степени с показателями s и t
(s
< t
) такие, что
. (*)
7. 2. Замечание
. Обозначив t
– s
= k
> 0, из (*) получим: 
. Возводя обе части этого сравнения в степень n
ÎN
, получим: 
(**). Это означает, что существует бесконечное множество степеней числа a
, удовлетворяющих сравнению (**). Но как
найти эти показатели? Каков наименьший
показатель, удовлетворяющий сравнению (**) ? На первый вопрос отвечает теорема Эйлера
(1707 – 1783).
7. 3. Теорема Эйлера.
Если а
ÎZ
, т
ÎN, т
>1 и
(а
; т
) = 1, – то
. (13)
Пример.
Пусть а
= 2, т
= 21, (а
; т
) = (2; 21) = 1. Тогда 
. Так как j (21) = 12, то 2 12 º 1(mod 21). В самом деле: 2 12 = 4096 и (4096 – 1) 21. Тогда очевидно, что 2 24 º 1(mod 21), 2 36 º 1(mod 21) и так далее. Но является ли показатель степени 12 – наименьшим
, удовлетворяющим сравнению 2 n
º 1(mod 21) ? Оказывается, нет. Наименьшим показателем
будет п
= 6: 2 6 º 1(mod 21), ибо 2 6 – 1 = 63, а 63 21. Заметим, что наименьший
показатель следует искать только среди делителей числа
j(т
) (в данном примере – среди делителей числа j(21) = 12).
7. 4. Малая теорема Ферма (1601 – 1665).
Для любого простого числа р и любого числа а
ÎZ
, не делящегося на р
, имеет место сравнение
. (14)
Пример.
Пусть а
= 3, р
= 5, где 3 не 5. Тогда 
или 
.
7. 5. Обобщёння теорема Ферма.
Для любого простого числа р и произвольного числа а
ÎZ имеет место сравнение
(15)
ТИПОВЫЕ ЗАДАЧИ
1. Докажите, что 38 73 º 3(mod 35).
Решение.
1) Так как (38; 35) = 1, то по теореме Эйлера 
; j(35) = 24, значит,
(1).
2) Из сравнения (1) по следствию 2 свойства 5 0 числовых сравнений имеем:
3) Из сравнения (2) по следствию 1 свойства 5 0 сравнений: 38 72 ×38 º 1×38 (mod 35) Þ Þ38 73 º38 º 38–35 = 3(mod 35) Þ 38 73 º 3 (mod 35), что и требовалось доказать.
2. Дано: а
= 4, т
= 15. Найти наименьший показатель степени k
, удовлетворяющий сравнению 
(*)
Решение.
1) Так как (a
; m
) = (4; 25) = 1, то по теореме Эйлера 
, j(25) = 20, поэтому 
.
2) Является ли найденный показатель степени – число 20 – наименьшим натуральным числом, удовлетворяющим сравнению (*)? Если существует показатель степени, меньший 20, то он должен быть делителем числа 20. Значит, искомый наименьший показатель k надо искать среди множества чисел n = {1, 2, 4, 5, 10, 20}– делителей числа 20.
3) При п
= 1: 
;
при п
= 2: 
;
при п = 3: (рассматривать не надо);
при п = 4: ;
при п = 5: ;
при п = 6, 7, 8, 9: (рассматривать не надо);
при п = 10: .
Итак, наименьшим показателем степени k , удовлетворяющим сравнению(*), является k = 10.
Ответ:
.
УПРАЖНЕНИЯ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ
141. По теореме Эйлера 
. При а
= 3, т
= 6 имеем: 
.
Так как j(6) = 2, то 3 2 º1(mod 6), или 9º1(mod 6), Тогда, по лемме, (9 – 1) 6 или 8 6 (нацело!?). Где ошибка?
142. Докажите, что: а) 23 100 º1(mod 101); б) 81 40 º 1(mod100); в) 2 73 º 2 (mod 73).
143. Докажите, что а) 1 16 + 3 16 + 7 16 + 9 16 º 4 (mod 10);
б) 5 4п + 1 + 7 4п + 1 делится без остатка на 12..
144. Докажите теорему, обратную теореме Эйлера: если а j ( m ) º 1(mod m ), то (а, m ) =1.
145. Найдите наименьший показатель степени k
ÎN,
удовлетворяющий данному сравнению: а) 
; б) 
; в) 
; г) 
;
д) 
; е) 
; ж) 
; з) 
.
и) 
; к) 
; л) 
; м) 
.
146. Найдите остаток от деления:
а) 7 100 на 11; б) 9 900 на 5; в) 5 176 на 7; г) 2 1999 на 5; д) 8 377 на 5;
е) 26 57 на 35; ж) 35 359 на 22; з) 5 718 на 103; и) 27 260 на 40; к) 25 1998 на 62.
147*. Докажите, что а 561 º а (mod 11).
148*. Если каноническое разложение натурального числа п не содержит множителей 2 и 5, то 12-я степень этого числа оканчивается цифрой 1. Докажите.
149*. Докажите, что 2 64 º 16 (mod 360).
150*. Докажите: если (а, 65) =1 , (b, 65) =1, то a 12 – b 12 делится без остатка на 65.
Глава 3. АРИФМЕТИЧЕСКИЕ ПРИЛОЖЕНИЯ
ТЕОРИИ ЧИСЛОВЫХ СРАВНЕНИЙ
§ 8. СИСТЕМАТИЧЕСКИЕ ЧИСЛА
ОСНОВНЫЕ СВЕДЕНИЯ ИЗ ТЕОРИИ
1. ЦЕЛЫЕ СИСТЕМАТИЧЕСКИЕ ЧИСЛА
8. 1. Определение 1.
Системой счисления называется всякий способ записи чисел. Знаки, с помощью которых записывают эти числа, называют цифрами.
8. 2. Определение 2.
Целым неотрицательным систематическим числом, записанным в t -ичной позиционной системе счисления, называется число n вида
, где a i (i = 0,1, 2,…, k ) – целые неотрицательные числа – цифры , причём 0 £ a i £ t – 1, t – основание системы счисления, t ÎN, t > 1.
Например, запись числа в 7-ричной системе имеет вид: (5603) 7 = 5 ×7 3 + 6×7 2 + 0×7 1 + 3. Здесь a i – это 5, 6, 0, 3 – цифры; все они удовлетворяют условию: 0 £ a i £ 6. При t =10 говорят: число n записано в десятичной системе счисления, причём индекс t= 10не пишут.
8. 3. Теорема 1.
Всякое целое неотрицательное число может быть представлено, причём единственным образом, в виде систематического числа по любому основанию t, где t Î N, t > 1.
Пример: (1 3 9) 10 = (3 5 1) 6 = (1 0 2 4) 5 = …
8. 4. Отметим, что:
1) приписывание к систематическому числу нулей слева не изменяет этого числа:
(3 4) 5 = (0 3 4) 5 .
2) приписывание к систематическому числу s нулей справа равносильно умножению этого числа на t s : (3 4) 5 = 3×5 1 + 4; (3 4 0 0) 5 = 3×5 3 + 4×5 2 + 0×5 1 + 0 = 5 2 ×(3×5 1 + 4).
8. 5. Алгоритм перевода числа, записанного в t -ичной системе, в десятичную:
Пример: (287) 12 = 2×12 2 + 8×12 1 +7×12 0 = 2×144 + 8×12 + 7 = 288 + 96 +7 = (391) 10 .
8. 6. Алгоритм перевода числа, записанного в десятичной системе, в t -ичную:
Пример: (3 9 1) 10 = (х ) 12 . Найти х.
8. 7. Действия над систематическими числами
2. СИСТЕМАТИЧЕСКИЕ ДРОБИ
8. 8. Определение 3.
Конечной t-ичной систематической дробью в системе счисления с основанием t называется число вида
где c
0 ÎZ
, с i – цифры
– целые неотрицательные числа
, причём
0 £ с i
£ t
– 1, t
Î N, t >
1, k
Î N
.
Обозначение: a = (c 0 , с 1 с 2 …с k ) t . При t = 10 дробь называется десятичной .
8. 9. Следствие 1.
Всякая конечная систематическая дробь есть рациональное число, которое можно представить в виде , где а Î Z, b Î N.
Пример.
a = (3 1, 2 4) 6 = 3×6 + 1 + =19 + 
– рациональное число. Обратное утверждение, вообще говоря, неверно. Например, дробь нельзя преобразовать в конечную систематическую (десятичную) дробь.
8.10. Определение 4.
Бесконечной t-ичной положительной систематической дробью в системе счисления с основанием t называется число вида
, где с 0
Î N
, с i
(i
=1, 2, …, к
, …) – цифры
– целые неотрицательные числа
, причём
0 £ с i
£ t
–1, t
ÎN, t >
1, k
ÎN
.
Обозначение: a = (с 0 , с 1 с 2 … с k …) t . При t =10 дробь называется десятичной .
8.11. Определение 5.
Возможны три вида бесконечных систематических дробей:
I a = (с
0 , 
) t
= = 
t
, где = = = … В этом случае число
a называется бесконечной чисто периодической дробью,
(с
1 с
2 … с k
) – периодом
, k– количество цифр в периоде – длиной периода.
II a = 
.
В этом случае число a называется бесконечной смешанной периодической дробью,
– предпериодом
, (
) – периодом
, k – количество цифр в периоде – длиной периода, l – количество цифр между целой частью и первым периодом – длиной предпериода.
III a = (с 0 , с 1 с 2 … с k …) t . В этом случае число a называется бесконечной непериодической дробью.
ТИПОВЫЕ ЗАДАЧИ
1. Число (а ) 5 = (2 1 4 3) 5 , заданное в 5–ричной системе, перевести в 7-ричную систему, то есть найти х , если (2 1 4 3) 5 = (х ) 7 .
Решение.
1) Преобразуем данное число (2 1 4 3) 5 в число (у ) 10 , записанное в десятичной системе:
2. Выполните действия:
1) (7) 8 + (5) 8 ; 2) (7) 8 × (5) 8 ; 3) (3 6 4 2) 6 + (4 3 5 1) 6 ;
4) (5 2 3 4) 7 – (2 3 5 1) 7 ; 5) (4 2 3) 5 × (3 2) 5 ; 6) (3 0 1 4 1) 5: (4 2 3) 5 .
Решение.
1) (7) 8 + (5) 8 = (7) 10 + (5) 10 = (12) 10 = 1×8 + 4 = (1 4) 8 ;
2) (7) 8 × (5) 8 = (7) 10 × (5) 10 = (35) 10 = 4×8 + 3 = (4 3) 8 ;
| 3) (3 6 4 2) 6 + (4 3 5 1) 6 (1 2 4 3 3) 6 | Примечание: | 4+5 = 9 = 1×6+3, 3 пишем, 1 переходит в следующий разряд, 6+3+1=10 =1×6+4, 4 пишем, 1 переходит в следующий разряд, 3+4+1= 8 = 1×6+2, 2 пишем, 1 переходит в следующий разряд. |
| 4) (5 2 3 4) 7 – (2 3 5 1) 7 (2 5 5 3) 7 | Примечание: | "занимаем" единицу высшего разряда, т. е. "1" = 1×7: (3 + 1×7) – 5 = 10 – 5 = 5, (1 + 1×7) – 3 = 8 – 3 = 5, |
| 5) (4 2 3) 5 ´ (3 2) 5 (1 4 0 1) 5 + (2 3 2 4) 5__ (3 0 1 4 1) 5 | Примечание: | При умножении на 2: 3 ×2 = 6 = 1×5 + 1, 1 пишем, 1 переходит в следующий разряд, 2 ×2 +1=5 = 1×5 +0, 0 пишем, 1 переходит в следующий разряд, 2 ×4 +1=9 = 1×5 +4, 4 пишем, 1 переходит в следующий разряд, При умножении на 3: 3 ×3 = 9 = 1×5 + 4, 4 пишем, 1 переходит в следующий разряд, 3 ×2 +1=7 = 1×5 +2, 2 пишем, 1 переходит в следующий разряд, 3 ×4 +1=13=2×5 +3, 3 пишем, 2 переходит в следующий разряд. |
6) (3 0 1 4 1) 5 | (4 2 3) 5
2 3 2 4 (3 2) 5
1 4 0 1 Ответ: 1) (1 4) 8 ; 2) (4 3) 8 ; 3) (1 2 4 3 3) 6 ; 4) (2 5 5 3) 7 ;
(0) 5 5) (3 0 1 4 1) 5 ; 6) (3 2) 5 .
УПРАЖНЕНИЯ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ
151. Числа, заданные в t -ичной системе, переведите в десятичную систему:
а) (2 3 5) 7 ; б) (2 4 3 1) 5 ; в) (1 0 0 1 0 1) 2 ; г) (1 3 ) 15 ;
д) (2 7) 11 ; е) (3 2 5 4) 6 ; ж) (1 5 0 1 3) 8 ; з) (1 1 0 1 1 0 0 1) 2 ;
и) (7 6 2) 8 ; к) (1 1 1 1) 20 .
152. Числа. заданные в десятичной системе, переведите в t -ичную систему. Сделайте проверку.
а) (1 3 2) 10 = (х ) 7 ; б) (2 9 8) 10 = (х ) 5 ; в) (3 7) 10 = (х ) 2 ; г) (3 2 4 5) 10 = (х ) 6 ;
д) (4 4 4 4) 10 = (х ) 3 ; е) (5 6 3) 10 = (х ) 12 ; ж) (5 0 0) 10 = (х ) 8 ; з) (6 0 0) 10 = (х ) 2 ;
и)(1 0 0 1 5) 10 =(х ) 20 ; к) (9 2 5) 10 = (х ) 8 ; л) (6 3 3) 10 = (х ) 15 ; м) (1 4 3) 10 = (х ) 2 .
153. Числа, заданные в t -ичной системе, переведите в q -ичную систему (путём перехода через десятичную систему).
а) (3 7) 8 = (х ) 3 ; б) (1 1 0 1 1 0) 2 = (х ) 5 ; в) ( 6 2) 11 = (х ) 4 ;
г) (4 ) 12 = (х ) 9 . д) (3 3 1 3 1) 5 = (х ) 12 .
154. а) Как изменится число (1 2 3) 5 , если к нему справа приписать нуль?
б) Как изменится число (5 7 6) 8 , если к нему справа приписать два нуля?
155. Выполните действия:
а) (3 0 2 1) 4 + (1 2 3 3) 4 ; б) (2 6 5 4) 8 + (7 5 4 3) 8 ; в) (1 0 1 1 0 1) 2 +(1 1 0 1 10) 2 ;
г) (5 2 4 7) 9 + (1 3 7 6) 9 ; д) (4 7 6) 9 – (2 8 7) 9 ; е) (2 4 5 3) 7 – (1 6 4 5) 7 ;
ж) (8 3) 12 – (5 7 9) 12 ; з) (1 7 5) 11 – ( 6) 11 ; и) (3 6 4 0 1) 7 – (2 6 6 6 3) 7 ;
к) (1 0 0 1 0) 2 × (1 1 0 1) 2 ; л) (7 4 1) 8 × (2 6) 8 ; м) (5 3 7 2) 8 × (2 4 6) 8 ;
н) (3 3 2 1) 4 × (2 3 0) 4 ; о) (1 0 2 2 2 2) 3: (1 2 2) 3 ; п) (2 1 0 3 2) 4: (3 2 3) 4 ;
р) (2 6 1 7 4) 8: (5 4 6) 8 ; с) (4 3 2 0 1) 5: (2 1 4) 5 ; т)(1 1 0 1 0 0 1 0) 2:(1 0 1 0 1) 2
у) (1 1 0 1 1 0) 2: (1 1 1) 2 ; ф) (1 1 1 0) 6: (2 1 5) 6 ; х)(3 2 3 8 2 2 1 7 0) 9:(7 6 4 2) 9 .
ц) (1 6 3 5) 8 + (7 6 4) 8 ; ч) (1 1 1 1) 3 – (2 1 2) 3 ; ш)(1 2 7) 12 +(9 1 3 5 ) 12b" × b 1 Тогда:
I Если знаменатель b = b" (содержит только "2" и / или "5"), – то дробь преобразуется в конечную десятичную дробь. Количество десятичных знаков равно наименьшему натуральному числу l l º 0(mod b ").
II Если знаменатель b = b 1 (не содержит "2" и "5"), – то дробь преобразуется в бесконечную чисто периодическую равна наименьшему натуральному числу k , удовлетворяющему сравнению 10 k º 1(mod b 1).
III Если знаменатель b = b" × b 1 (содержит "2" и / или"5", а также иные простые множители), – то дробь преобразуется в бесконечную смешанную периодическую деся-
тичную дробь.
Длина периода равна наименьшему натуральному числу k , удовлетворяющему сравнению 10 k º 1(mod b 1 ).
Длина предпериода равна наименьшему натуральному числу l , удовлетворяющему сравнению 10 l º 0(mod b ").
9. 2. Выводы.
9. 3. Отметим, что:
рациональным числом является всякая конечная десятичная дробь или бесконечная периодическая десятичная дробь;
иррациональным числом является всякая бесконечная непериодическая десятичная дробь.
ТИПОВЫЕ ЗАДАЧИ
1. Данные обыкновенные дроби, записанные в десятичной системе, преобразовать в
десятичные, предварительно определив вид искомой дроби (конечная или бесконечная; периодическая или непериодическая; если – периодическая, то чисто периодическая или смешанная периодическая); в последних случаях – предварительно найти число k – длину периода и число l – длину предпериода. 1) ; 2) ; 3) .
Решение.
1) У дроби = знаменатель – число b = 80 = 2 4 × 5 содержит только "2" и "5". Поэтому данная дробь преобразуется в конечную десятичную дробь. Количество десятичных знаков l наим определяется из условия: 10 l º0(mod80):
2) У дроби = знаменатель – число b = 27 = 3 3 не содержит "2" и "5". Поэтому данная дробь преобразуется в бесконечную чисто периодическую десятичную дробь. Длина периода k наим определяется из условия: 10 k º1(mod27):
3) У дроби = знаменатель – число b = 24 = 2 3 ×3, то есть имеет вид: b = b" × b 1 (кроме "2" или "5" содержит и иные множители, в данном случае число 3). Поэтому данная дробь преобразуется в бесконечную смешанную периодическую десятичную дробь. Длина периода k наим определяется из условия: 10 k º1(mod3), откуда k наим = 1, то есть длина периода k = 1. Длина предпериода l наим определяется из условия: 10 l º0(mod8), откуда l наим = 3, то есть длина предпериода l = 3.
Проверка: разделим "уголком" 5 на 24 и получим: = 0, 208 (3).
Ответ: 1) 0, 0375; 2) 0, (074); 3) 0, 208 (3).
УПРАЖНЕНИЯ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ
156. Данные обыкновенные дроби, записанные в десятичной системе, преобразуйте в десятичные дроби. Если десятичная дробь - периодическая, то предварительно найдите число k - длину периода и число l - длину предпериода.
157. Данные обыкновенные дроби, записанные в десятичной системе, преобразуйте в t -ичные систематические дроби. Найдите числа k - длину периода и l - длину предпериода.
158*. В какой системе счисления число (4 6) 10 записывается теми же цифрами, но в
обратном порядке?
159*. Что больше: единица 8-го разряда в двоичной системе или единица 4-го разряда в 8-ричной системе?
§ 10. ТЕОРЕМА ПАСКАЛЯ. ПРИЗНАКИ ДЕЛИМОСТИ
ОСНОВНЫЕ СВЕДЕНИЯ ИЗ ТЕОРИИ
10. 1. Теорема Паскаля (1623 – 1662).
Даны натуральные числа: т > 1 и n, записанное в t - ичной системе:
, где a i – – цифры: a i ÎN, 0 £ a i £ t –1 (i = 0,1, 2,…, k ), t ÎN, t > 1.
Пусть n = (a k a k – 1 … a 1 a 0) 10 = a k ×10 k +a k – 1 ×10 k – 1 +…+a 1 ×10 + a 0 , m =3 и m = 9.
1) Найдём b i : по модулю m = 3по модулю m = 9
10 0 º1(mod3), т.е. b 0 =1, 10 0 º1(mod9), т.е. b 0 =1,
10 1 º1(mod3), т.е. b 1 =1, 10 1 º1(mod9), т.е. b 1 =1,
10 2 º1(mod3), т.е. b 2 =1, 10 2 º1(mod9), т.е. b
В предыдущем пункте было отмечено, что отношение m сравнимости по произвольному модулю m есть отношение эквивалентности на множестве целых чисел. Это отношение эквивалентности индуцирует разбиение множества целых чисел на классы эквивалентных между собой элементов, т.е. в один класс объединяются числа, дающие при делении на m одинаковые остатки. Число классов эквивалентности m (знатоки скажут – "индекс эквивалентности m ") в точности равно m .
Определение. Любое число из класса эквивалентности m будем называть вычетом по модулю m . Совокупность вычетов, взятых по одному из каждого класса эквивалентности m , называется полной системой вычетов по модулю m (в полной системе вычетов, таким образом, всего m штук чисел). Непосредственно сами остатки при делении на m называются наименьшими неотрицательными вычетами и, конечно, образуют полную систему вычетов по модулю m . Вычет ρ называется абсолютно наименьшим, если ⎪ρ ⎪ наименьший среди модулей вычетов данного класса.
Пример : Пусть m = 5. Тогда:
0, 1, 2, 3, 4 - наименьшие неотрицательные вычеты;
2, -1, 0, 1, 2 - абсолютно наименьшие вычеты.
Обе приведенные совокупности чисел образуют полные системы вычетов по модулю 5.
Лемма 1 . 1) Любые m штук попарно не сравнимых по модулю m чисел образуют полную систему вычетов по модулю m .
2) Если а и m взаимно просты, а x пробегает полную систему вычетов по модулю m , то значения линейной формы а x + b , где b – любое целое число, тоже пробегают полную систему вычетов по модулю m .
Доказательство. Утверждение 1) – очевидно. Докажем утверждение 2) Чисел а x +b ровно m штук. Покажем, что они между собой не сравнимы по модулю m . Ну пусть для некоторых различных x 1 и x 2 из полной системы вычетов оказалось, что ax 1 + b ≡ ax 2 + b (mod m). Тогда, по свойствам сравнений из предыдущего пункта, получаем:
ax 1 ≡ ax 2 (mod m )
x 1 ≡ x 2 (mod m )
– противоречие с тем, что x 1 и x 2 различны и взяты из полной системы вычетов.
Поскольку все числа из данного класса эквивалентности m получаются из одного числа данного класса прибавлением числа, кратного m , то все числа из данного класса имеют с модулем m один и тот же наибольший общий делитель. По некоторым соображениям, повышенный интерес представляют те вычеты, которые имеют с модулем m наибольший общий делитель, равный единице, т.е. вычеты, которые взаимно просты с модулем.
Определение. Приведенной системой вычетов по модулю m называется совокупность всех вычетов из полной системы, взаимно простых с модулем m .
Приведенную систему обычно выбирают из наименьших неотрицательных вычетов. Ясно, что приведенная система вычетов по модулю m содержит ϕ (m ) штук вычетов, где ϕ (m )– функция Эйлера – число чисел, меньших m и взаимно простых с m .
Функция Эйлера.
Функция Эйлера ϕ (a ) есть количество чисел из ряда 0, 1, 2,..., a –1, взаимно простых с a .
Лемма. Пусть
Т
огда:
в частности, φ(p α) = p α –p α -1 , φ(p ) = p –1.
Пример . Пусть m = 42. Тогда приведенная система вычетов суть:
1, 5, 11, 13, 17, 19, 23, 25, 29, 31, 37, 41.
Лемма 2. 1) Любые ϕ (m ) чисел, попарно не сравнимые по модулю m и взаимно простые с модулем, образуют приведенную систему вычетов по модулю m .
2) Если d (a , m ) = 1 и x пробегает приведенную систему вычетов по модулю m , то а x так же пробегает приведенную систему вычетов по модулю m .
Доказательство . Утверждение 1) – очевидно. Докажем утверждение 2). Числа а x попарно несравнимы (это доказывается так же, как в лемме 1 этого пункта), их ровно ϕ (m ) штук. Ясно также, что все они взаимно просты с модулем, ибо d (a , m )=1, d (x ,m )=1 ⇒ d (ax , m )=1. Значит, числа а x образуют приведенную систему вычетов.
Лемма 3. Пусть m 1 , m 2 , ..., m k – попарно взаимно просты и m 1 m 2 ...m k =M 1 m 1 =M 2 m 2 =...=M k m k , где M j =m 1 ...m j -1 m j +1 ...m k
1) Если x 1 , x 2 , ..., x k пробегают полные системы вычетов по модулям m 1 , m 2 , ..., m k M 1 x 1 +M 2 x 2 + ...+M k x k пробегают полную систему вычетов по модулю m= m 1 m 2 ...m k .
2) Если ξ 1 , ξ 2 , ..., ξ k пробегают приведенные системы вычетов по модулям m 1 , m 2 , ..., m k соответственно, то значения линейной формы M 1 ξ 1 +M 2 ξ 2 + ...+M k ξ k пробегают приведенную систему вычетов по модулю m= m 1 m 2 ...m k .
Лемма 4. Пусть x 1 , x 2 , ..., x k , x пробегают полные, а ξ 1 , ξ 2 ,..., ξ k , ξ – пробегают приведенные системы вычетов по модулям m 1 , m 2 ,...,m k и m=m 1 m 2 ...m k соответственно, где (m i m j )=1 при i ≠ j . Тогда дроби {x 1 /m 1 +x 2 /m 2 +...+x k /m k } совпадают с дробями {x/m} , а дроби { ξ 1 /m 1 + ξ 2 /m 2 +...+ ξ k /m k } совпадают с дробями { ξ/m} .
Обозначим через ε k k -ый корень m- ой степени из единицы:
Здесь k =0,1,...,m -1 – пробегает полную систему вычетов по модулю m .
Напомню, что сумма ε 0 + ε 1 +...+ ε m-1 всех корней m -ой степени из единицы равна нулю для любого m . Действительно, пусть ε 0 + ε 1 +...+ ε m-1 = a . Умножим эту сумму на ненулевое число ε 1 . Такое умножение геометрически в комплексной плоскости означает поворот правильного m -угольника, в вершинах которого расположены корни ε 0 + ε 1 +...+ ε m-1 , на ненулевой угол 2 π/m . Ясно, что при этом корень ε 0 перейдет в корень ε 1 , корень ε 1 перейдет в корень ε 2 , и т.д., а корень ε m-1 перейдет в корень ε 0 , т.е. сумма ε 0 + ε 1 +...+ ε m-1 не изменится. Имеем ε 1 a=a , откуда a=0 .
Теорема 1. Пусть m>0 – целое число, a Z , x пробегает полную систему вычетов по модулю m . Тогда, если а кратно m , то
в противном случае, при а не кратном m ,
Теорема 2. Пусть m>0 – целое число, ξ пробегает приведенную систему вычетов по модулю m . Тогда (сумма первообразных корней степени m ):
где μ(m ) – функция Мебиуса.
или же любые последовательные p числа.
Данная система называется полною системою чисел, не сравнимых по модулю p или же полною системою вычетов по модулю p . Очевидно, что всякие p последовательных чисел образуют такую систему.
Все числа, принадлежащих к одному классу, имеют много общих свойств, следовательно по отношению к модулю их можно рассматривать как одно число. Каждое число, входящее в сравнение как слагаемое или множитель, может быть заменено, без нарушения сравнения, числом, сравнимым с ним, т.е. с числом, принадлежащим к одному и тому же классу.
Другой элемент, который является общим для всех чисел данного класса, является наибольший общий делитель каждого элемента этого класса и модуля p .
Пусть a и b сравнимы по модулю p , тогда
Теорема 1. Если в ax+b вместо x подставим последовательно все p членов полной системы чисел
Поэтому все числа ax+b , где x =1,2,...p -1 не сравнимы по модулю p (в противном случае, числа 1,2,...p -1 были бы сравнимы по модулю p .
Примечания
1) В данной статье под словом число будем понимать целое число.
Литература
- 1. К.Айрленд, М.Роузен. Классическое введение в современную теорию чисел.− М:Мир, 1987.
- 2. Г.Дэвенпорт. Высшая арифметика.− М:Наука, 1965.
- 3. П.Г. Лежен Дирихле. Лекции по теории чисел. − Москва, 1936.