Сравнение по модулю

Говорят, что два целых числа a и b сравнимы по модулю натурального числа n, если при делении на n они дают одинаковые остатки. Другими словами, a и b сравнимы по модулю n, если их разность a – b делится на n.

Пример: 32 и 39 сравнимы по модулю 7, так как 32 = 7∙4 + 4, 39 = 7∙5 + 4.

Утверждение a и b сравнимы по модулю n записывается в виде:

a\equiv b\pmod n.

Отношение сравнения обладают многими свойствами обычных равенств, например если

a_1 \equiv b_1 \pmod n и
a_2 \equiv b_2 \pmod n,

то

a_1a_2 \equiv b_1b_2 \pmod n и
a_1+a_2 \equiv b_1+b_2 \pmod n.

Классы вычетов

Множество всех чисел сравнимых с a по модулю n называется классом вычетов a по модулю n , и обычно обозначается [a]n или \bar a_n. Таким образом, сравнение a\equiv b\pmod n равносильно равенству классов вычетов [a]n = [b]n.

Сравнение по модулю n является отношением эквивалентности на множестве целых чисел \mathbb{Z}, и классы вычетов по модулю n представляют собой классы эквивалентности. Множество всех классов вычетов по модулю n обозначается \mathbb{Z}_n или \mathbb{Z}/n\mathbb{Z}.

Операции сложения и умножения на \mathbb{Z} индуцируют соответствующие операции на множестве \mathbb{Z}_n:

[a]n + [b]n = [a + b]n
[a]_n\cdot [b]_n=[a\cdot b]_n

Относительно этих операций множество \mathbb{Z}_n является кольцом, а если n простоеполем.

Ссылки

 
Начальная страница  » 
А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ы Э Ю Я
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
0 1 2 3 4 5 6 7 8 9 Home