Система остаточных классов - введение

Теоретико-числовая база построения системы остаточных классов

Напомним определение деления с остатком.

Определение. Говорят, что целое число $n$ делится на натуральное число $m$ с остатком, если имеется пара целых чисел $q$ и $r$, таких, что $n = m \cdot q+r$ и $0\le r<m$. $n$ называется делимым, $m$ - делителем, $q$ - неполным частным, $r$ - остатком.

Для целых чисел:

Определение. Говорят, что целое число $n \in Z$ делится на натуральное число $m \in Z$ с остатком, если имеется пара целых чисел $q$ и $r$, таких, что $n = m \cdot q+r$ и $0\le r<|m|$.

Пример: 48 при делении на 5 даёт остаток 3, т.к. $48=5\cdot 9+3$, $0\le 3<5$, -48 при делении на 5 даёт остаток 2, т.к. $-48=5\cdot (-10)+2$, $0\le 2<5$.

Сравнения и их основные свойства

Возьмём произвольное фиксированное натуральное число $m$ и будем рассматривать остатки при делении на $m$ различных целых чисел.

При рассмотрении свойств этих остатков и проведении операций над ними удобно ввести понятие сравнения по модулю.

Определение. Два целых числа $a$и $b$называются сравнимыми по модулю m, если их разность

делится без остатка на $m$.

Символически сравнимость записывается в виде формулы (сравнения):

$a \equiv b \pmod{m}$

Число $m$ называется модулем сравнения.

Эквивалентная формулировка:

Определение. Целые числа $a$и $b$называются сравнимыми по модулю m, если остатки от деления этих чисел на$m$ равны.

Отношение сравнимости по модулю $m$ обладает свойствами рефлексивности, симметричности и транзитивности, т.е. является отношением эквивалентности.

Отнесём все целые числа, дающие при делении на $m$ один и тот же остаток в один класс, поэтому получится $m$ различных классов по модулю $m$. Множество всех чисел сравнимых с $a$по модулю $m$называется классом вычетов $a$по модулю $m$.

Подробнее о свойствах сравнений и классах вычетов смотри Сравнения и их основные свойства

Теорема о делении с остатком. Алгоритм Евклида

Теорема. для любых целых n и m, $m \not= 0$, существует единственный набор целых чисел q и r, что n = mq + r и $0 \le r < |m|$, где |m| — модуль числа m.

На этой операции основан алгоритм Евклида нахождения наибольшего общего делителя двух целых чисел.