Дипломная работа: Математические основы системы остаточных классов
6. Если 
и k – произвольное натуральное число, то 
.
7. Если , где k и р – произвольные натуральные числа, то .
8. Если , 
, то 
и 
.
9. Если , , то 
.
10. Если , то при любом целом n > 0, .
11. Если и 
- произвольный многочлен с целыми коэффициентами, то 
.
12. Любое слагаемое левой или правой части сравнения можно перенести с противоположным знаком в другую часть.
13. Если и 
, то 
.
14. Если , то множество общих делителей а и р совпадает с множеством общих делителей b и р . В частности, 
15. Если 
, 
, …, 
, то 
, где 
.
При делении целого числа на модуль р в остатке получается 0, 1, 2, 3,…, р – 1 чисел.
Отнесём все целые числа, дающие при делении на р один и тот же остаток в один класс, поэтому получится р – различных классов по модулю р .
В один класс попадут равноостаточные числа, они называются вычетами друг друга .
Обозначим через А 0 – класс вычетов, которые при делении на р дают остаток 0.
Например, числа вида 
.
Через А 1 – числа, дающие при делении остаток 1.
Например, числа вида 
.
Через А 2 – числа, дающие при делении остаток 2.
Например, числа вида 
.
Через А р-1 – числа, дающие при делении остаток р – 1.
Например, числа вида 
.
Полной системой вычетов по модулю р называется совокупность р -целых чисел, содержащая точно по одному представителю из каждого класса вычетов по модулю р . Каждый класс вычетов по модулю р содержит в точности одно из чисел совокупности всех возможных остатков от деления на р : 0, 1, …, р – 1. Множество {0, 1, …, р – 1} называется полной системой наименьших неотрицательных вычетов по модулю р . Можно легко доказать, что любая совокупность р чисел (р >1), попарно несравнимых по модулю р , есть полная система вычетов по модулю р . Часто рассматривают полную систему наименьших положительных вычетов: 1, 2, …, р ; полную систему наименьших по абсолютной величине вычетов:
при чётном р и
при р нечётном.
Можно ввести в рассмотрение приведённую систему вычетов по модулю р , т. е. систему чисел, взятых по одному и только по одному из каждого класса, взаимно простого с модулем.
Число классов, взаимно простых с модулем р , равно значению функции Эйлера φ (р ).
§ 2. Теорема о делении с остатком. Алгоритм Евклида
Рассмотрим пример. Пусть р = 6.
Тогда имеем шесть классов разбиения множества целых чисел по модулю 6:
r = 0;