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

Два целых числа a и b сравнимы по модулю натурального числа n (или равноостаточны при делении на n), если при делении на n они дают одинаковые остатки. Число nназывается модулем сравнения.Свойства: Отношение сравнимости по модулю натурального числа   обладает следующими свойствами:

- рефлексивности: для любого целого   справедливо 

- симметричности: если   то 

- транзитивности: если и то

В силу того, что отношение сравнимости по модулю обладает этими тремя свойствами, оно является отношением эквивалентности на множестве целых чисел. Любые два целых числа сравнимы по модулю 1.Если числа a и b

 сравнимы по модулю n, и n делится на m, то a и b сравнимы по модулю m.

Для того, чтобы числа a и b были сравнимы по модулю n, каноническое разложение на простые сомножители которого: необходимо и достаточно, чтобы Если 

 и  , то  , где .

Множество всех чисел сравнимых с a по модулю n называется классом вычетов a по модулю n, и обычно обозначается   или  . Таким образом, сравнение   равносильно равенству классов вычетов  .

Поскольку сравнение по модулю n является отношением эквивалентности на множестве целых чисел  , то классы вычетов по модулю n представляют собой классы эквивалентности; их количество равно n. Множество всех классов вычетов по модулю n обозначается   или .

Операции сложения и умножения на   индуцируют соответствующие операции на множестве  :