Page 47 - 4570

46

Доведення. За теоремою це відношення збігається з відношенням «а і b
мають однакові остачі при діленні на n», рефлексивність, симетричність і
транзитивність якого очевидні.
Кожне відношення еквівалентності на множині визначає розбиття цієї
множини на класи еквівалентності. Для відношення а  b (mod n) на множині Z
класи еквівалентності називаються класами лишків за модулем n. Клас лишків,
який містить число а, будемо позначати через a або a mod n. якщо треба
вказати і число n.
Приклад 1.59. Розбити множину чисел 13, 41, 9, 88, 117, 36, 95, 1999, 146,
207 на класи попарно конгруентних за модулем 5.
Розв’язання. Остачі від ділення на 5 дорівнюють відповідно 3, 1, 4, 3, 2, 1,
0, 4, 1, 2. Тому дана множина розпадається на такі класи попарно конгруентних
чисел: {13, 88}, {41, 36, 146}, {9, 1999}, {117, 207}, {95}.
Неважко підрахувати кількість класів лишків за модулем n. Справді, з
теореми випливає, іцо різні остачі від ділення на n потрапляють у різні класи, а
з наслідку 1 – що кожен клас містить якусь остачу. Отже, клас лишків
однозначно характеризується тією єдиною остачею від ділення на n, яку він
містить. Тому класів буде стільки ж, скільки остач, тобто n. Множину 0, 1, 2, ...,
n - 1 всіх класів лишків за модулем n звичайно позначають Z n.
Наприклад, за модулем 3 маємо 3 класи лишків: 0 = {..., -6, -3, 0, 3, 6, ...}
(всі числа, які при діленні на 3 дають в остачі 0), 1 = {..., -5, -2, 1, 4, 7, ...}
(остача 1) і 2 = {..., -4, -1, 2, 5, 8, ...} (остача 2).