Сравнение по модулю

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

Определение и обозначения

Пусть \( m \) — натуральное число, большее единицы. Два целых числа \( a \) и \( b \) называются сравнимыми по модулю \( m \), если разность \( a - b \) делится на \( m \) без остатка. Формально это записывается как:

\[ a \equiv b \pmod{m} \]

Это означает, что существует такое целое число \( k \), что \( a = b + k \cdot m \). Эквивалентное определение: \( a \) и \( b \) дают одинаковые остатки при делении на \( m \). Например, \( 17 \equiv 5 \pmod{12} \), так как \( 17 - 5 = 12 \), что делится на 12, и оба числа дают остаток 5 при делении на 12.

В математической литературе также используются обозначения \( a \equiv b \ (\text{mod} \ m) \) или \( a \equiv b \ (m) \). Модуль \( m \) может быть любым натуральным числом, включая единицу (в этом случае все целые числа сравнимы друг с другом, так как разность всегда делится на 1).

Основные свойства

Отношение сравнения по модулю является отношением эквивалентности, то есть оно удовлетворяет трём аксиомам:

• Рефлексивность: \( a \equiv a \pmod{m} \) для любого \( a \).
• Симметричность: если \( a \equiv b \pmod{m} \), то \( b \equiv a \pmod{m} \).
• Транзитивность: если \( a \equiv b \pmod{m} \) и \( b \equiv c \pmod{m} \), то \( a \equiv c \pmod{m} \).

Кроме того, сравнения обладают свойствами, аналогичными свойствам равенств:

• Сложение и вычитание: если \( a \equiv b \pmod{m} \) и \( c \equiv d \pmod{m} \), то \( a \pm c \equiv b \pm d \pmod{m} \).
• Умножение: если \( a \equiv b \pmod{m} \) и \( c \equiv d \pmod{m} \), то \( a \cdot c \equiv b \cdot d \pmod{m} \).
• Возведение в степень: если \( a \equiv b \pmod{m} \), то \( a^n \equiv b^n \pmod{m} \) для любого натурального \( n \).

Однако деление в сравнениях не всегда возможно: если \( a \cdot c \equiv b \cdot c \pmod{m} \), то из этого не следует \( a \equiv b \pmod{m} \), если \( c \) и \( m \) не взаимно просты. В общем случае, если \( \gcd(c, m) = d \), то \( a \equiv b \pmod{m/d} \).

Классы вычетов и кольцо вычетов

Отношение сравнения разбивает множество целых чисел \( \mathbb{Z} \) на непересекающиеся классы эквивалентности, называемые классами вычетов по модулю \( m \). Каждый класс содержит все числа, дающие одинаковый остаток при делении на \( m \). Всего существует ровно \( m \) различных классов вычетов: \( 0, 1, 2, \dots, m-1 \). Множество этих классов обозначается \( \mathbb{Z}_m \) или \( \mathbb{Z}/m\mathbb{Z} \) и образует кольцо вычетов по модулю \( m \).

В кольце \( \mathbb{Z}_m \) определены операции сложения и умножения, которые являются корректными (не зависят от выбора представителей класса). Например, по модулю 5: \( 3 + 4 \equiv 2 \pmod{5} \), так как \( 3 + 4 = 7 \), а \( 7 \mod 5 = 2 \). Если модуль \( m \) является простым числом, то кольцо \( \mathbb{Z}_m \) превращается в поле, где для каждого ненулевого элемента существует обратный по умножению.

История

Понятие сравнения по модулю в явном виде ввёл немецкий математик Карл Фридрих Гаусс в своём труде «Арифметические исследования» (лат. Disquisitiones Arithmeticae), опубликованном в 1801 году. Гаусс систематизировал и развил идеи, восходящие к древнегреческим и китайским математикам. В частности, китайская теорема об остатках, известная ещё в III веке н. э. (в трактате Сунь Цзы «Сунь Цзы суань цзин»), описывает систему сравнений с попарно взаимно простыми модулями. Гаусс ввёл современное обозначение \( \equiv \) и доказал многие фундаментальные свойства, включая квадратичный закон взаимности.

Применение

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

Сравнения по модулю лежат в основе многих криптографических алгоритмов. Например, RSA (Rivest–Shamir–Adleman) использует модульную арифметику для шифрования и дешифрования: сообщение \( M \) преобразуется в шифротекст \( C \) по формуле \( C \equiv M^e \pmod{n} \), где \( n \) — произведение двух больших простых чисел, а \( e \) — открытая экспонента. Обратное преобразование выполняется с помощью секретного ключа \( d \): \( M \equiv C^d \pmod{n} \). Безопасность RSA основана на сложности разложения \( n \) на множители.

Информатика и программирование

В языках программирования операция взятия остатка от деления (обычно обозначаемая % или mod) реализует сравнение по модулю. Она используется для циклического перебора (например, в хеш-таблицах), проверки чётности чисел, генерации псевдослучайных чисел (линейный конгруэнтный метод) и в алгоритмах контрольных сумм (например, CRC).

Календари и время

Системы счисления времени, такие как 12-часовой или 24-часовой циферблат, основаны на сравнении по модулю 12 или 24. Например, 23:00 и 11:00 вечера — это одно и то же время по модулю 12, так как \( 23 \equiv 11 \pmod{12} \). Аналогично, дни недели повторяются по модулю 7.

Теория чисел

Сравнения по модулю используются для решения диофантовых уравнений, доказательства теорем (например, малой теоремы Ферма: \( a^p \equiv a \pmod{p} \) для простого \( p \)), а также в алгоритмах проверки простоты чисел (тест Миллера — Рабина).

Классификация по модулю

В зависимости от свойств модуля различают:

• Сравнения по простому модулю: модуль \( p \) — простое число. В этом случае кольцо вычетов является полем, что упрощает многие операции (например, деление возможно для всех ненулевых элементов).
• Сравнения по составному модулю: модуль \( m \) — составное число. Здесь кольцо вычетов содержит делители нуля, что накладывает ограничения на деление.
• Сравнения по модулю степени простого числа: модуль \( p^k \), где \( p \) — простое. Такие модули важны в теории p-адических чисел и в криптографии (например, в схеме Пайе).

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

• Китайская теорема об остатках утверждает, что система сравнений \( x \equiv a_i \pmod{m_i} \) с попарно взаимно простыми модулями имеет единственное решение по модулю \( M = m_1 \cdot m_2 \cdot \dots \cdot m_k \). Эта теорема используется в криптографии для ускорения вычислений (например, в алгоритме RSA с помощью китайской теоремы можно дешифровать сообщение быстрее).
• Тест Ферма на простоту основан на сравнении: если \( a^{n-1} \not\equiv 1 \pmod{n} \) для некоторого \( a \), то \( n \) — составное число. Однако существуют числа Кармайкла, которые проходят тест Ферма для всех \( a \), взаимно простых с \( n \), оставаясь составными.
• В русской математической школе термин «сравнение по модулю» часто используется в контексте теории чисел, в то время как в западной литературе более распространён термин «модульная арифметика».

Критика и ограничения

Основное ограничение модульной арифметики — невозможность деления без дополнительных условий. Если модуль не является простым, то не для каждого элемента существует обратный по умножению. Кроме того, операции сравнения не сохраняют порядок: из \( a \equiv b \pmod{m} \) не следует, что \( a > b \) или \( a < b \). В криптографии модульная арифметика уязвима для атак, основанных на квантовых вычислениях (например, алгоритм Шора позволяет эффективно разлагать числа на множители, что подрывает безопасность RSA).

Источники

1. Гаусс К. Ф. «Арифметические исследования» (Disquisitiones Arithmeticae), 1801.
2. Виноградов И. М. «Основы теории чисел», 1952.
3. Кнут Д. Э. «Искусство программирования», том 2 (Получисленные алгоритмы), 1997.
4. Шнайер Б. «Прикладная криптография», 1996.
5. Сунь Цзы. «Сунь Цзы суань цзин» (III век н. э.) — описание китайской теоремы об остатках.