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

Материал из Википедии — свободной энциклопедии

Говорят, что два целых числа 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}$ .