Лекции по алгебре - Фаддеев Д.К.
Скачать (прямая ссылка):
ЦЕЛЫЕ ЧИСЛА
ІГЛ. I
классы четных и нечетных чисел. Если т = 3, классы в этом смысле составляют числа вида 3k, 3k + 1, 3k + 2 при целых k и т. д. Числа, относящиеся к одному классу, называются сравнимыми, и изучение свойств классов носит название теории сравнений. Переходим к точным определениям относящихся сюда понятий.
1. Определение и простейшие свойства. Пусть т — натуральное число. Два целых числа а и Ь называются сравнимыми по модулю т, если их разность а—-Ь делится на т. Высказывание «а и Ь сравнимы по модулю т» записывается в виде а=6 (mod т).
Предложение 1. а = а (mod т); далее, если a == ft(modm), то 6 = u(modm); если а == 6 (mod т) и b = с (mod т), то a S= с (mod tri).
Действительно, а — а = 0 делится на любое число; если а — Ь делится на пг, то и Ь — а делится на т; если а — Ь и Ь — с делятся на т, то а — с = (а — Ь)-\-(Ь— с) тоже делится на т.
Именно эти свойства сравнений позволяют заключить, что каждое целое число попадает в один и только один класс попарно сравнимых между собой целых чисел. Эти классы называются классами вычетов по модулю m или просто классами по модулю т.
Предложение 2. Каждое целое число сравнимо по модулю т с одним и только одним из чисел ряда 0, 1, ..., m — 1.
Действительно, пусть а — некоторое целое число. Поделим его на пг с остатком: a = mq + г, 0 /• =?: m— 1. Ясно, что а = sr(modm), ибо а — г = mq делится на пг. Итак, каждое целое число а сравнимо со своим остатком при делении на т. Остается показать, что среди чисел 0, 1, пг—1 нет сравнимых по модулю т. Но это ясно — если взять два различных целых числа этого ряда и вычесть из большего меньшее, мы получим в качестве разности положительное число, меньшее чем т, и, следовательно, эта разность не делится на т. Предложение доказано.
В процессе доказательства мы убедились,, что каждый класс по модулю пг действительно состоит из чисел, дающих один и тот же остаток при делении на т.
Любая совокупность чисел, взятых по одному из каждого класса по модулю т, называется полной системой вычетов по модулю т. Например, числа 0, 1, т—1 образуют полную систему вычетов. Полной же системой вычетов будет 1, 2, т; при нечетном m = 2k-\-l полной системой вычетов будет —k, —1, О, 1, k, и т. д.
Предложение 3. Если а% = a2(mod т) m^s 62(modт), то а\ ± bi H= а2 ± &2(mod m).
Доказательство. Если a1sa2(modm) и 6i = 62(modm), то а\ — а2 и bi — b2 делятся на ш, а следовательно, и Oi dhi>i — — (а2 ± b2) = (ai — а2)± (oi—-b2) тоже делится на ш, т. е. -а\ ± ±6. = а2 ± b2 (mod пі).
Предложение 4. Если а\ = a2(modm) " oi = Mmodm), то axbx == a262(modm).
ТЕОРИЯ СРАВНЕНИЙ
17
Доказательство. а\Ь\ — аф2 = а\Ъ\ — аф2 + а\Ь2 — — O2O2 = Oi(^i — 62) + (^1 — а2)й2. Если oi = a2 и &i = b2(mod от), то оба слагаемых делятся на т, а с ними и их сумма а\Ь\ — а2Ь2. Следовательно, <x\b\ = a2ft2(modm), что и требовалось доказать.
В частности, если ai = a2(modm) и с — любое целое число, то а\с = a2c(mod т).
Предложение 5. Если са\ з= ca2(modtri) и число с взаимно просто с m, то ai = a2(mod т).
Действительно, если cai = ca2(modm), то сах — са2 = = с(а{—а2) делится на т, с взаимно просто с т и согласно предложению 8 а\ — а2 делится на т, что и требовалось доказать.
Таким образом, обе части сравнения можно сократить на множитель, взаимно простой с модулем. Без предположения о взаимной простоте это, вообще говоря, делать нельзя. Так, 2 === 6 (mod 4), но 1 Ф 3(mod4).
2. Действия над классами. Пусть т = 6. Представим себе, что числа, сравнимые с нулем, мы записываем черными цифрами, сравнимые с единицей — красными, сравнимые с 2 — желтыми, сравнимые с 3 — фиолетовыми, сравнимые с 4 — зелеными и сравнимые с 5 — синими. Тогда предложения 3 и 4 можно переформулировать так: цвет суммы двух чисел зависит только от цветов слагаемых, но не от того, как выбраны эти слагаемые внутри своих классов. То же относится к разности и к произведению. Например, складывая «желтое» число с «синим», мы всегда получим «красное». Умножая «синее» на «фиолетовое», мы всегда получим «фиолетовое», и т. д. Сокращенно это можно записать: ж + с = к; с-ф = ф и т. д. Для шести символов: ч, к, ж, ф, з, с мы можем записать «суммы», «разности» и «произведения», руководствуясь сложением, вычитанием и умножением чисел (все равно каких), взятых из соответствующих классов.
То же самое имеет место при любом т. Для того чтобы указать класс, к которому принадлежит сумма, разность или произведение двух чисел, нам достаточно знать классы, к которым эти числа принадлежат, а как они выбраны внутри классов — на результате не сказывается. Это обстоятельство делает естественными следующие определения.
Суммой двух классов по модулю т называется класс по модулю т, к которому принадлежит сумма каких-либо чисел из слагаемых классов.
Произведением двух классов по модулю т называется класс по модулю т, к которому принадлежит произведение каких-либо чисел из перемножаемых классов.
В силу предложений 3, 4 эти определения корректны — какие бы числа из двух данных классов мы ни выбрали, их сумма и их произведение будут принадлежать вполне определенным классам, не зависящим от выбора чисел внутри данных классов.
