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

[r]_m- класс всех чисел, которые при делении на m дают в остатке r.

Классы [0]_m, [l]_m, [2]_m, …, [m- 1]_m называются классами вычетов, а их элементы — вычетами по модулю m. Числа из одного класса сравнимы по модулю m, числа же из разных классов несравнимы друг с другом по модулю m: aºb(modm)Û[а]_mº [b]_m.

Полной системой вычетов по модулю m называется совокупность чисел, взятых по одному из каждого класса вычетов по модулю m.

Множество чисел 0, 1,…, m-1 будет являться полной системы вычетов по модулю m. Этим получена так называемая полная система наименьших неотрицательных вычетов.

Для полных систем вычетов имеет место следующее свойство:

Если a₁, a₂, …, a_mесть полная система вычетов по модулю m, число а взаимно простое cm и b — любое целое число, тогда последовательность чиселaa₁ + b, aa₂ + b, …, aa_m + b - также есть полная система вычетов по модулю m. Если в классе вычетов по модулю m есть одно число, взаимно простое с m, то в нем все числа взаимно просты с m.

Сравнимость по модулю целых чисел a и b влечет за собой равенство наибольшего общего делителя чисел a и m c наибольшим общим делителем чисел b и m.

а b(modm) Þ НОД(а, m) = НОД(b, m).

Класс вычетов по модулю m, состоящий из чисел, взаимно простых с m, называется классом, взаимно простым с модулем m.Совокупность чисел, взятых по одному из всех классов, взаимно простых с модулем m, называется приведенной системой вычетов по модулю m.

Функция Эйлера j(m)

Количество чисел в приведенной системе вычетов по модулю m(или количество классов, взаимно простых с модулем m), определяет функцию Эйлера j(m), сопоставляющую числу m число j(m).

Значение этой функции j(m) равно количеству натуральных чисел, не превосходящих m и взаимно простых с m.

j(mn) = j(m)j(n). Это так называемое свойство мультипликативности функции Эйлера.

Из арифметики известен тот факт (основная теорема арифметики), что любое натуральное число единственным образом представимо в виде произведения взаимно простых с ним чисел. Такое представление называется каноническим разложением числа на простые множители. Если число m имеет каноническое разложение , то

Рассмотрим приведенную систему вычетов по модулю m, содержащую  элементов: а₁,a₂,...,а_j(m). Пусть, число а взаимно просто с m.

Справедливо следующее важное утверждение: набор чисел aa_1,,aa₂,...,aa_j(m) , получающихся умножением приведенной системы вычетов по модулю m на число взаимно простое с модулем m также является приведенной системой вычетов по этому модулю.