Лекции по алгебре - Фаддеев Д.К.
Скачать (прямая ссылка):
18
ЦЕЛЫЕ ЧИСЛА
[ГЛ. I
Пример. Приведем «таблицы умножения» для классов по модулю 7 и 8.
Таблица 1
Ш=7
О Ї 2 3 4 6 6
О T 2 3 4 5 в
0 0 0 0 0 0 0
O Ї 2 3 4 5 6
O 2 4 6 Ї 3 5
O 3 6 2 5 Ї 4
5 4 T В 2 6 3
6 5 3 T 6 4 2 O 6 5 4 3 2 1
Таблица 2
т=8
0Ї234567
00000000 ОЇ234567 02460246 036Ї4725 040404()4 05274І63 O642O642 0765432Ї
Символы 0, 1, 2, 3, 4, 5, 6 в табл. 1 обозначают классы по модулю 7, которым принадлежат числа 0, 1, 2, 3, 4, 5, 6. Значение символов в табл. 2 — аналогично. Такими обозначениями мы будем пользоваться и впредь — символ a будет обозначать класс по модулю (который предполагается заданным), содержащий число а.
Рассмотрение классов по модулю как объектов, над которыми совершаются действия, часто вызывает у начинающих некоторое затруднение. Иногда оно вызывается тем, что класс это не число, а бесконечное множество чисел, и сама мысль о том, что действие над классами суть действия сразу над бесконечными множествами чисел, кажется противоестественной. Для преодоления этого психологического барьера следует мыслить вместо класса одно из чисел этого класса, но безразлично какое, как бы отказываясь различать их одно от другого, как бы «склеивая» их в один объект. Собственно говоря, это обычный и привычный в обыденной жизни путь формирования абстрактного понятия. Говоря слово «яблоко», мы отвлекаемся от особенностей конкретных представителей этого класса предметов и подразумеваем некоторое яблоко, все равно какое. Нам привычно, говоря «яблоко», не вызывать в воображении множество всех имеющихся на земле в данный момент яблок. Так же надо относиться к понятию «класс по модулю т».
Отметим некоторые очевидные свойства действий над классами по модулю.
1. (а + 5) + с = а + (5 + с) (ассоциативность сложения). Действительно, (а + В) + с есть класс, содержащий (a +ft)+с,
a a + (5 -f-с) есть класс, содержащий a+(fc + c). Но (a-f-ft) + + с = a + (ft + с), откуда и следует требуемое.
2. a + /5 = 5 + a (коммутативность сложения).
«21
ТЕОРИЯ СРАВНЕНИИ
19
3. Класс 0 играет роль нуля при сложении: а +0—а при любом а. _
4. Класс —? играет роль класса, противоположного классу а,
именно, а + ( — a)_=O-_
5. a(b + с) = ab -+- ас;
5'. (В -f- c)a == ba -4- ca (дистрибутивность).
6. a(5c) = (ao)c (ассоциативность умножения).
7. ab = Бй (коммутативность умножения).
Свойства 3 и 4 очевидны. Свойства 2, 5, 6, 7 доказываются точно так же, как свойство 1, посредством перехода от классов к любым числам из этих классов, для которых соответствующие свойства действий имеют место.
8. Класс Ї играет роль единицы при умножении классов, именно, а • Т = а при любом а.
3. Приведенная система вычетов и примитивные классы.
Предложение б. Пусть d = н. о. д. (а, пг) и ai = a(modm). Тогда н. о. д. (ai, tri) = d.
Доказательство. Имеем a\ — a-\-mq при некотором ^eZ, так что d есть общий делитель для а\ и пг, и потому d ^ du где di = н. о. д.(?i, m). С другой стороны, а = ах — mq, откуда следует, что d{ является общим делителем для а и т, так что d\ 5?; d. Отсюда заключаем, что d\ = d.
В частности, если одно из чисел класса по модулю m взаимно просто с т, то и все числа этого класса взаимно просты с т.
Классы, состоящие из чисел, взаимно простых с модулем, называются примитивными классами. Для любого модуля примитив-ные классы существуют; такими будут, в частности, классы 1 и m — 1.
Предложение 7. Для того чтобы сравнение ах = 1 (mod пг) имело решение, необходимо и достаточно, чтобы а было взаимно просто с пг.
Доказательство. Необходимость. Пусть существует целое число Xo такое, что ахо = l(modm). Число 1 взаимно просто с пг, значит (предложение 6), число ах0 взаимно просто с т, откуда а взаимно просто с т, что и требовалось доказать.
Достаточность. Пусть а взаимно просто с т. Тогда, согласно предложению 5 § 1, существуют целые числа и и v такие, что аи -f- mv = 1. Ясно, что аи == 1 (mod пг), так что и есть решение сравнения ах = l(modm).
Предложение 7 можно в терминах классов сформулировать так: для того чтобы класс a имел обратный й-1, т. е. такой, что йа~х = 1, необходимо и достаточно, чтобы класс a был примитивным.
Ясно, что если X0 — решение сравнения ах = l(modm), то все сравнимые с Xo числа тоже доставляют решения, так что решение «приводит за собой» весь класс, его содержащий. В этом смысле
20
ЦЕЛЫЕ ЧИСЛА
ІГЛ. I
решений бесконечно много. Однако класс решений существует только один. Действительно, если ах0 = 1 (mod т) и ах\ = = l(modm), то ах0 = ах, (mod т), и в силу взаимной простоты а и т, X0 = х\ (mod т). В терминах классов: обратный класс а-1 к примитивному классу а существует только один.
Число примитивных классов по модулю т обозначается <f(m). Так определенная функция называется функцией Эйлера. Ясно, что ф(1)= 1. Для т> 1 (р(т) равно, очевидно, числу взаимно простых с т чисел ряда 0, І, .... т—1. Так, ф(2) = 1, ф(3) = 2, Ф(4) = 2, ф(5) = 4, ф(6) = 2, ф(7) = 6, ф(8) = 4 и т. д.
