Полная система вычетов

Полная система вычетов — это в теории чисел конечное множество целых чисел, которое содержит ровно по одному представителю из каждого класса вычетов по заданному модулю. Иными словами, для натурального числа \(m\) полная система вычетов по модулю \(m\) — это любое множество из \(m\) целых чисел, попарно не сравнимых по модулю \(m\) (то есть дающих разные остатки при делении на \(m\)). Понятие является фундаментальным для модульной арифметики, теории сравнений и криптографии.

Определение и основные свойства

Пусть \(m\) — натуральное число (модуль). Отношение сравнения по модулю \(m\) разбивает множество всех целых чисел \(\mathbb{Z}\) на \(m\) непересекающихся классов эквивалентности — классов вычетов по модулю \(m\). Каждый класс состоит из всех чисел, дающих один и тот же остаток при делении на \(m\). Например, по модулю 3 существуют три класса: \(\{..., -6, -3, 0, 3, 6, ...\}\), \(\{..., -5, -2, 1, 4, 7, ...\}\) и \(\{..., -4, -1, 2, 5, 8, ...\}\).

Полная система вычетов (ПСВ) по модулю \(m\) — это любое множество из \(m\) целых чисел, взятых по одному из каждого класса вычетов. Формально: множество \(A = \{a_1, a_2, ..., a_m\}\) является полной системой вычетов по модулю \(m\), если:

1. Для любых \(i \neq j\) выполняется \(a_i \not\equiv a_j \pmod{m}\) (числа попарно не сравнимы по модулю \(m\)).
2. Для любого целого числа \(x\) найдётся такой элемент \(a_i \in A\), что \(x \equiv a_i \pmod{m}\).

Из определения следует, что любая полная система вычетов содержит ровно \(m\) элементов, и все они различны по модулю \(m\).

Канонические системы вычетов

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

Наименьшие неотрицательные вычеты

Это множество \(\{0, 1, 2, ..., m-1\}\). Каждое число в этой системе равно остатку от деления на \(m\). Это наиболее интуитивная и часто применяемая система, особенно в программировании и алгоритмах.

Наименьшие по абсолютной величине вычеты

Для нечётного \(m\) это множество \(\{-\frac{m-1}{2}, ..., -1, 0, 1, ..., \frac{m-1}{2}\}\). Для чётного \(m\) возможны два варианта: \(\{-\frac{m}{2}+1, ..., -1, 0, 1, ..., \frac{m}{2}\}\) или \(\{-\frac{m}{2}, ..., -1, 0, 1, ..., \frac{m}{2}-1\}\). Эта система удобна в симметричных задачах, например, при работе с целыми числами с плавающей запятой или в криптографии.

Примеры

• По модулю 5: полной системой вычетов является \(\{0, 1, 2, 3, 4\}\). Другие примеры: \(\{5, 6, 7, 8, 9\}\), \(\{-2, -1, 0, 1, 2\}\), \(\{10, 16, 22, 28, 34\}\).
• По модулю 1: существует только один класс вычетов, поэтому полная система вычетов состоит из одного числа, например \(\{0\}\).

Свойства полных систем вычетов

1. Единственность представителей: Если \(A\) — полная система вычетов по модулю \(m\), то для любого целого \(x\) существует единственный \(a \in A\) такой, что \(x \equiv a \pmod{m}\).
2. Арифметические операции: Если \(A\) — полная система вычетов по модулю \(m\), то:

• Множество \(\{a + c \mid a \in A\}\) также является полной системой вычетов по модулю \(m\) для любого целого \(c\).
• Множество \(\{c \cdot a \mid a \in A\}\) является полной системой вычетов по модулю \(m\) тогда и только тогда, когда \(\gcd(c, m) = 1\) (то есть \(c\) взаимно просто с \(m\)).

1. Связь с приведённой системой вычетов: Из полной системы вычетов можно выделить приведённую систему вычетов — подмножество, состоящее из чисел, взаимно простых с модулем \(m\). Количество таких чисел равно функции Эйлера \(\varphi(m)\). Например, по модулю 10 полная система вычетов \(\{0,1,2,3,4,5,6,7,8,9\}\) даёт приведённую систему \(\{1,3,7,9\}\) (так как \(\varphi(10)=4\)).

Применение

Теория сравнений

Полная система вычетов является основой для решения линейных сравнений вида \(ax \equiv b \pmod{m}\). Если \(a\) и \(m\) взаимно просты, то решение существует и единственно в любой полной системе вычетов.

Китайская теорема об остатках

Эта теорема утверждает, что для попарно взаимно простых модулей \(m_1, m_2, ..., m_k\) система сравнений имеет единственное решение по модулю \(M = m_1 m_2 ... m_k\), которое можно найти, используя полные системы вычетов по каждому модулю.

Криптография

В криптографических алгоритмах, таких как RSA и Эль-Гамаля, все операции выполняются по модулю \(n\), где \(n\) — произведение двух больших простых чисел. Полная система вычетов по модулю \(n\) используется для представления сообщений и ключей.

Вычислительная математика

В алгоритмах быстрого преобразования Фурье (БПФ) и в модулярной арифметике (например, в системе остаточных классов — СОК) числа представляются в виде набора остатков по нескольким модулям, что требует работы с полными системами вычетов.

Интересные факты

• Понятие полной системы вычетов ввёл Карл Фридрих Гаусс в своей работе «Арифметические исследования» (1801 год).
• В криптографии часто используется полная система вычетов по модулю \(2^k\) (например, \(2^{32}\) или \(2^{64}\)), что позволяет эффективно реализовывать арифметические операции на компьютерах.
• Для больших модулей полная система вычетов может быть построена не только из последовательных чисел, но и из произвольных чисел, удовлетворяющих условию попарной несравнимости.

Источники

1. Гаусс К. Ф. «Арифметические исследования» (Disquisitiones Arithmeticae), 1801.
2. Виноградов И. М. «Основы теории чисел», 9-е издание, 1981.
3. Бухштаб А. А. «Теория чисел», 2-е издание, 1966.
4. Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. «Алгоритмы: построение и анализ», 3-е издание, 2013 (глава 31 «Модульная арифметика»).
5. Шнайер Б. «Прикладная криптография», 2-е издание, 2002.