Учебник по теории чисел Ильиных АП

ПРЕДЛОЖЕНИЕ 1 Пусть a и b —произвольные целые числа. Тогда равносильны следующие три утверждения :

1)a ≡ b (mod m),

2)a − b ... m,

3)существует число q Z с условием a = b + mq.

Доказательство. Проверим, что 1) 2). Дано a ≡ b (mod m). Нужно доказать, что a − b ... m. По условию числа a и b при делении на m имеют один и тот же остаток r. Тогда

a = mq1 + r, b = mq2 + r.

Вычтем из первого равенства второе. Получим a −b = m(q1 −q2), где q1 −q2 Z. Поэтому a − b ... m.

Проверим 2) 3). Дано (a − b) ... m, т.е. a − b = mq, где q Z. Отсюда a = b + mq.

Проверим 3) → 1). Дано a = b + mq, где q Z. Разделим число b на m, получим частное q1 и остаток r1. Тогда b = mq1 + r1 и 0 6 r1 < m.

Поэтому a = b+mq = mq1+r1+mq = m(q+q1)+r1. Запись a = m(q+q1)+r1

и неравенство 0 6 r1 < m означают, что q + q1 — частное, r1 — остаток

След Пред Стр Начало Оглавление Обратно Меню Экран Выход

отделения a на m. Получили, что a и b имеют имеют один и тот же остаток r1 при делении на m, т.е. a ≡ b (mod m).

Теорема доказана.

В силу доказанной теоремы, определение сравнимости чисел можно выразить в одном трех видах 1)–3). Мы будем использовать все эти три вида.

Свойства сравнений. Отношение сравнимости целых чисел по модулю m обладает свойствами во многом аналогичными свойствам отношения равенства чисел.

СВОЙСТВО 1 Отношение сравнимости является отношением эквивалентности.

Доказательство. Нужно проверить, что отношение сравнимости рефлективно, симметрично и транзитивно.

Рефлективность означает a ≡ a (mod ) для всех a Z. Это верно, т.к. a и a имеют одинаковый остаток при делении на m.

Симметричность. Дано a ≡ b (mod m). Нужно доказать, что b ≡ a (mod ). Если a и b имеют одинаковый остаток при делении на m, то, очевидно, b и a имеют одинаковый остаток при делении на m.

Транзитивность. Из a ≡ b (mod m) и b ≡ c (mod m) следует a ≡ c (mod m). Дано, что a и b имеют одинаковый остаток при делении на m,

След Пред Стр Начало Оглавление Обратно Меню Экран Выход

а также b и c имеют одинаковый остаток при делении на m. Тогда a и c имеют одинаковый остаток при делении на m. Получили a ≡ c (mod m).

СВОЙСТВО 2 Сравнения можно почленно складывать, вычитать и

умножать: если a ≡ b (mod m) и	c ≡ d (mod m), то
a + c ≡ b + d	(mod m),	(1)
a − c ≡ b − d	(mod m),	(2)
ac ≡ bd (mod m).		(3)

Доказательство. Проверим (1). Так как a ≡ b (mod m) и c ≡ d (mod m), то a − b ... m и c − d ... m. Тогда (a − b) + (c − d) ... m, т.е. (a + c) − (b + d) ... m и a + c ≡ b + d (mod m). Аналогично получаем (2), (3), а также и последующие свойства.

СВОЙСТВО 3 Обе части сравнения можно умножать на произвольное число:

a ≡ b (mod m) ak ≡ bk (mod m).

Обе части сравнения можно разделить на число взаимно простое с модулем: если (k, m) = 1, то

ak ≡ bk (mod m) a ≡ b (mod m).

След Пред Стр Начало Оглавление Обратно Меню Экран Выход

СВОЙСТВО 4 Обе части сравнения можно возводить в степень с показателем k N:

a ≡ b (mod m) ak ≡ bk (mod m).

СВОЙСТВО 5 Обе части сравнения и модуль можно умножать на произвольное число:

a ≡ b (mod m) ak ≡ bk (mod mk).

Обе части сравнения и модуль можно разделить на их общий делитель k

ak ≡ bk	(mod mk) a ≡ b	(mod m).
СВОЙСТВО 6 Если a	≡ b (mod m1) и a	≡ b (mod m2), то

a≡ b (mod m), где m = [m1, m2] —НОК модулей m1 и m2.

СВОЙСТВО 7 Если в выражении

s = a0xα1 1 xα2 2 . . . xαnn + a1xβ11 xβ22 . . . xβnn + . . .

заменим каждое число x1, x2, . . . , xn на сравнимые с ними числа x01, x02, . . . , x0n по модулю m, то получим выражение s0, для которого s0 ≡ s (mod m).

Классы вычетов. По свойству 1 отношение сравнимости является отношением эквивалентности. Поэтому можно рассматривать классы эквивалентных элементов для отношения сравнимости ≡.

След Пред Стр Начало Оглавление Обратно Меню Экран Выход

Напомним необходимые определения из курса алгебры.

Пусть R отношение эквивалентности на множестве M и a M.

ОПРЕДЕЛЕНИЕ 2 Классом элементов, эквивалентных элементу a называется множество

Ma = {x M | xRa}.

(4)

Перебирая элементы x из M, получим все классы Mx для отношения R. Пусть даны два класса Ma и Mb для отношения R. Справедлив следующий признак равенства классов.

ТЕОРЕМА 1 Два класса Ma и Mb равны тогда и только тогда, когда элементы a и b эквивалентны, т.е.

Ma = Mb aRb.

(5)

Если говорим, что Ma, Mb, Mc, . . . — множество классов для отношения R, то считаем, что выписаны все классы и они выписаны без повторений. В курсе алгебры доказана

ТЕОРЕМА 2 Классы эквивалентных элементов {Ma, Mb, Mc, . . . } образуют разбиение множествa M.

Тем самым:

След Пред Стр Начало Оглавление Обратно Меню Экран Выход

1)подмножества из Ma, Mb, Mc, . . . не пусты;

2)их объединение равно M;

3)пересечение двух разных подмножеств из Ma, Mb, Mc, . . . пусто.

Применим данные результаты к отношению сравнимости ≡.

ОПРЕДЕЛЕНИЕ 3 Классом вычетов по модулю m называется класс эквивалентных элементов для отношения сравнимости по модулю m.

Если класс вычетов по модулю m состоит из элементов сравнимых с a по модулю m, то этот класс обозначается через a¯.

В определении класса в (4) заменим R на ≡. Получим, что класс вычетов a¯ имеет вид

a¯ = {x Z | x ≡ a (mod m)}.

(6)

Получаем другую формулировку определения класса вычетов по модулю m.

ОПРЕДЕЛЕНИЕ 4 Классом вычетов a¯ по модулю m называется множество всех чисел, сравнимых с числом a по модулю m.

По признаку равенства классов (1) получаем

	¯	равны тогда и только тогда, когда числа
ТЕОРЕМА 3 Два класса a¯ и b
a и b сравнимы по модулю m
¯	a ≡ b (mod m).		(7)
a¯ = b

След Пред Стр Начало Оглавление Обратно Меню Экран Выход

Рассмотрим все возможные остатки при делении на m
0, 1, 2, . . . , m − 1
и классы их содержащие
¯ ¯ ¯			(8)
0, 1, 2, . . . , m − 1.

ТЕОРЕМА 4 Классы, указанные в (8) попарно различны и исчерпывают все классы по модулю m.

Доказательство. Пусть a¯ — произвольный класс по модулю m и r — остаток от деления a на m. Тогда a ≡ r (mod m). По признаку равенства класс вычетов получаем a¯ = r¯. Итак,

класс a¯ по модулю m совпадает с классом r¯, где r — остаток от деления числа a на m.

Итак, произвольный класс по модулю m совпадает с одним из классов в списке (8). Осталось проверить, что все элементы из этого списка попарно различны. Это следует из того, что остатки 0, 1, 2, . . . , m − 1 попарно не сравнимы по модулю m. Теорема доказана.

След Пред Стр Начало Оглавление Обратно Меню Экран Выход

Лекция 8. Полная система и приведенная системы вычетов.

ОПРЕДЕЛЕНИЕ 1 Полной системой вычетов по модулю m называется совокупность чисел, взятых по одному из каждого класса вычетов по модулю m.

ПРИМЕР. Совокупность чисел 5, 11, 4, 6 является полной системой вычетов по модулю 4. Действительно, по модулю m = 4 имеется ровно четыре клас-

¯ ¯ ¯ ¯
са 0, 1, 2, 3. При этом числа взяты 5, 11, 4, 6 по одному из каждого класса, а
именно
¯	¯	¯	¯
4 0,	5 1,	6 2,	11 3.

Числа 5, 1, 4, 6 не образуют полную систему вычетов по модулю 4, т.к. 5 и 1

взяты из одного класса ¯.

1

Справедлив следующий признак полной системой вычетов.

ТЕОРЕМА 1 Совокупность чисел x1, x2, . . . , xk образует полную систему вычетов по модулю m тогда и только тогда, когда выполнены следующие два условия :

1)k = m,

2)xi ≡/ xj (mod m) при i 6= j.

След Пред Стр Начало Оглавление Обратно Меню Экран Выход

Доказательство необходимости. Пусть x1, x2, . . . , xk — полная система вычетов по модулю m. Тогда x1, x2, . . . , xk совокупность чисел, взятых по одному

¯ ¯ ¯
элементу из каждого класса 0, 1, 2, . . . , m − 1. Количество классов равно m.
¯			¯	различны. Поэтому
Поэтому получим k = m чисел. Если i 6= j, то классы i			и j

xi ≡/ xj (mod m).

Достаточность. Пусть выполнены условия 1) и 2). Применим известное правило комбинаторики — «принцип ящиков».

Пусть есть m ящиков и m предметов x1, x2, . . . , xm, взятых из этих ящиков. Предположим, что никакие два предмета xi и xj при i 6= j не содержатся в одном ящике. Тогда данные m предметов взяты по одному из каждого ящика.

В нашем случае в качестве данных предметов выступают числа x1, x2, . . . , xk. При этом k = m по условию 1). В качестве данных ящиков выступают m клас-

сов вычетов ¯ ¯ ¯ − .

0, 1, 2, . . . , m 1

Так как выполнено условие 2), то xi ≡/ xj (mod m) при i 6= j. Это означает, что числа xi и xj при i 6= j попадают в разные классы. По принципу ящи-

ков числа взяты по одному из каждого класса ¯ ¯ ¯ − . x1, x2, . . . , xk 0, 1, 2, . . . , m 1

Поэтому x1, x2, . . . , xk полная система вычетов по модулю m. Теорема доказана.

ТЕОРЕМА 2 Пусть a, b Z и (a, m) = 1. Если числа x1, x2, . . . , xk обра-

След Пред Стр Начало Оглавление Обратно Меню Экран Выход

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

ax1 + b, ax2 + b, . . . , axk + b

(1)

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

Доказательство. Применим признак полной системой вычетов. Проверим его посылки 1) и 2). В списке (1) содержится k = m чисел, т.е. выполнена посылка 1).

Установим 2) методом от противного. Пусть axi + b ≡ axj + b (mod m) при i 6= j. Тогда a(xi − xj) ≡ 0 (mod m), т.е. a(xi − xj) ... m. С учетом (a, m) = 1 получим xi −xj ... m. Тогда xi ≡ xj (mod m) при i 6= j, противоречие, с тем, что числа x1, x2, . . . xk образуют полную систему вычетов.

Теорема доказана.

Приведенная система вычетов. Ведем понятие класса, взаимно простого с модулем. Пусть a и b два произвольных числа из некоторого класса x по модулю m. Тогда a = mq + b для некоторого q Z. Обозначим d = (a, m). Из a = mq + b следует d = (b, m). Поэтому (a, b) = 1 (b, m) = 1. Получили, что НОД (a, m) один и тот же у все чисел a из фиксированного класса вычетов. Поэтому либо

1) все числа из класса x взаимно просты с модулем m, либо

След Пред Стр Начало Оглавление Обратно Меню Экран Выход