Обратимые вычеты

[Список тем] [Вступление к этой теме] Страницы темы: [1] [2] [3]

Сравнимость по модулю

Основные понятия

В этом подразделе все числа целые.

Определение

Говорят, что число a сравнимо по модулю n с числом b (обозначение: а b (mod n)), если а и b при делении на n дают один и тот же остаток:
a b (mod n) <=> a mod n = b mod n.

Примеры: 3

18 (mod 5), 8

-7 (mod 5),
3

17 (mod 5), т. к. 3-17 = -14 - не делится на 5.
Отношение сравнимости рефлексивно, симметрично и транзитивно и является отношением эквивалентности.

Определение

Классы эквивалентности по отношению сравнимости (по модулю n) называются вычетами (по модулю n).

Множество вычетов по модулю n обозначается Z_n.

Определение

Полная система вычетов по модулю n - это множество из n чисел Z_n = { a₁,...,a_n}, такое, что любое число сравнимо только с одним из чисел a_i .

Примеры: n=5, {0, 1, 2, 3, 4}, {7, 11, -15, 14, 18}.
(-15

0, 11

1, 7

2, 18

3, 14

4).
Обычно из каждого вычета выбирают одного представителя - неотрицательное число, которое при делении на n дает частное 0. Это позволяет считать, что Z_n = {0, 1, 2, ..., n - 1}, и упростить обозначения.

Определение

Класс вычетов по модулю n - это множество всех чисел, сравнимых с данным a_i по модулю n.

Любой элемент множества - это представитель класса.
Примеры: n=2. Все четные числа составляют класс (эквивалентности) вычетов по модулю 2, представляемый любым числом. Аналогично - нечетные числа.

Свойства сравнений

Сравнения по фиксированному модулю n задают отношение эквивалентности:

a a (mod n) для любого a /рефлексивность/.
Если a b (mod n), то b a (mod n) /симметричность/.
Если a b (mod n) и b c (mod n), то a c (mod n) /транзитивность/.

Отношение эквивалентности задает разбиение исходного множества A на классы эквивалентности:
A_n = A₁

A₂

...

A_n, где множества A_i и A_j не пересекаются для i j. Каждое из подмножеств состоит из всех элементов, эквивалентных данному элементу (представителю класса).
Примеры: n=2. Множество всех целых чисел представляется как объединение двух непересекающихся классов вычетов: четных и нечетных чисел.
Множество студентов колледжа разбивается на классы эквивалентности по годам обучения на первокурсников, второкурсников, третьекурсников и четверокурсников.
Множество студентов колледжа разбивается на классы эквивалентности по учебным группам.

[Список тем] [Вступление к этой теме] Страницы темы: [1] [2] [3]