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

Сравнение^[1] по модулю натурального числа n — в теории чисел отношение эквивалентности на кольце целых чисел, связанное с делимостью на n. Факторкольцо по этому отношению называется кольцом вычетов. Совокупность соответствующих тождеств и алгоритмов образует модульную^[2] (или модулярную) арифметику.

Определения

Два целых числа a и b сравнимы по модулю натурального числа n (или равноостаточны при делении на n), если при делении на n они дают одинаковые остатки. Число n называется модулем сравнения.

Эквивалентные формулировки: a и b сравнимы по модулю n, если их разность $a-b$ делится на n без остатка, или если a может быть представлено в виде $a=b+kn$, где $k$ — некоторое целое число. Например: 32 и −10 сравнимы по модулю 7, так как

$32 = 7 \cdot 4 + 4$

и

$-10 = 7 \cdot (-2) + 4.$

Утверждение «a и b сравнимы по модулю n» записывается в виде:

$a\equiv b\pmod n.$

Свойства

Отношение сравнимости по модулю натурального числа $n$ обладает следующими свойствами:

• рефлексивности: для любого целого $a$ справедливо $a \equiv a \pmod n.$
• симметричности: если $a \equiv b \pmod n,$ то $b \equiv a \pmod n.$
• транзитивности: если $a \equiv b \pmod n$ и $b \equiv c \pmod n,$ то $a \equiv c \pmod n.$

В силу того, что отношение сравнимости по модулю обладает этими тремя свойствами, оно является отношением эквивалентности на множестве целых чисел.

Любые два целых числа сравнимы по модулю $1.$

Если числа a и b сравнимы по модулю n, и n делится на m, то a и b сравнимы по модулю m.

Для того, чтобы числа a и b были сравнимы по модулю n, каноническое разложение на простые сомножители которого:

$n = \prod_{i=1}^d p_i^{\alpha_i},$

необходимо и достаточно, чтобы

$a \equiv b \pmod {p_i^{\alpha_i}},\quad i = 1, 2, \dots, d.$

Если $a \equiv b\pmod {m_1}$ и $a \equiv b\pmod {m_2}$, то $a \equiv b \pmod m$, где $m=[m_1,m_2]$.

Операции со сравнениями

Сравнения по одному и тому же модулю обладают многими свойствами обычных равенств. Например, их можно складывать, вычитать и перемножать: если числа $a_1,\,a_2,\,\dots,\,a_n$ и $b_1,\,b_2,\,\dots,\,b_n$ попарно сравнимы по модулю $n,$ то их суммы $a_1 + a_2 + \dots + a_n$ и $b_1 + b_2 + \dots + b_n$, а также произведения $a_1\,a_2\,\dots\,a_n$ и $b_1\,b_2\,\dots\,b_n$ тоже сравнимы по модулю $n.$ Если числа $a$ и $b$ сравнимы по модулю $n,$ то их степени $a^k$ и $b^k$ тоже сравнимы по модулю $n$ при любом натуральном $k.$

Сравнения, однако, нельзя, вообще говоря, делить друг на друга или на другие числа. Пример: $14 \equiv 20 \pmod 6$, однако, сократив на 2, мы получаем ошибочное сравнение: $7 \equiv 10 \pmod 6$. Правила сокращения для сравнений следующие.

• Можно делить обе части сравнения на число, взаимно простое с модулем: если $ac \equiv bc \pmod n$ и $\gcd(c,n)=1$, то $a \equiv b \pmod n$.
• Можно одновременно разделить обе части сравнения и модуль на их общий делитель: если $ac \equiv bc \pmod {nc}$, то $a \equiv b \pmod n$.

Нельзя также выполнять операции со сравнениями, если их модули не совпадают.

Связанные определения

Классы вычетов

Множество всех чисел сравнимых с a по модулю n называется классом вычетов a по модулю n, и обычно обозначается $[a]_n$ или $\bar a_n$. Таким образом, сравнение $a\equiv b\pmod{n}$ равносильно равенству классов вычетов $[a]_n=[b]_n$.

Поскольку сравнение по модулю n является отношением эквивалентности на множестве целых чисел $\mathbb{Z}$, то классы вычетов по модулю n представляют собой классы эквивалентности; их количество равно n. Множество всех классов вычетов по модулю n обозначается $\mathbb{Z}_n$ или $\mathbb{Z}/n\mathbb{Z}$.

Операции сложения и умножения на $\mathbb{Z}$ индуцируют соответствующие операции на множестве $\mathbb{Z}_n$:

$[a]_n+[b]_n=[a+b]_n$

$[a]_n\cdot [b]_n=[a\cdot b]_n$

Относительно этих операций множество $\mathbb{Z}_n$ является конечным кольцом, а для простого n — конечным полем.

Системы вычетов

Система вычетов позволяет осуществлять арифметические операции над конечным набором чисел, не выходя за его пределы. Полная система вычетов по модулю n ― любой набор из n попарно несравнимых по модулю n целых чисел. Обычно в качестве полной системы вычетов по модулю n берутся наименьшие неотрицательные вычеты

$0, 1, ... , n-1$

или абсолютно наименьшие вычеты, состоящие из чисел

$0,\pm1,\pm2,...,\pm\tfrac{n-1}2$,

в случае нечётного $n$, и чисел

$0,\pm1,\pm2,...,\pm(\tfrac{n}2-1),\tfrac{n}2$

в случае чётного $n$.

Максимальный набор попарно несравнимых по модулю n чисел, взаимно простых с n, называется приведённой системой вычетов по модулю n. Всякая приведённая система вычетов по модулю n содержит $\varphi(n)$ элементов, где $\varphi(\cdot)$ — функция Эйлера.

Решение сравнений

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

В теории чисел, криптографии и других областях науки часто возникает задача отыскания решений сравнения первой степени вида:

$ax \equiv b\pmod {m}.$

Решение такого сравнения начинается с вычисления НОД(a, m)=d. При этом возможны 2 случая:

• Если $b$ не кратно $d$, то у сравнения нет решений.
• Если $b$ кратно $d$, то у сравнения существует единственное решение по модулю $m/d$, или, что то же самое, $d$ решений по модулю $m$. В этом случае в результате сокращения исходного сравнения на d получается сравнение:

$a_1 x \equiv b_1\pmod {m_1}$

где $a_1 = a/d$, $b_1 = b/d$ и $m_1 = m/d$ являются целыми числами, причем $a_1$ и $m_1$ взаимно просты. Поэтому число $a_1$ можно обратить по модулю $m_1$, то есть найти такое число c, что $c\cdot a_1\equiv 1\pmod{m_1}$ (другими словами, $c \equiv a_1^{-1}\pmod{m_1}$). Теперь решение находится умножением полученного сравнения на c:

$x \equiv c a_1 x\equiv c b_1\equiv a_1^{-1} b_1\pmod {m_1}.$

Практическое вычисление значения c можно осуществить разными способами: с помощью теоремы Эйлера, алгоритма Евклида, теории цепных дробей (см. алгоритм) и др. В частности, теорема Эйлера позволяет записать значение c в виде:

$c \equiv a_1^{-1}\equiv a_1^{\varphi(m_1)-1}\pmod {m_1}.$

Пример

Для сравнения $4x\equiv 26\pmod {22}$ имеем $d=2$, поэтому по модулю 22 сравнение имеет два решения. Заменим 26 на 4, сравнимое с ним по модулю 22, и затем сократим все 3 числа на 2:

$2x \equiv 2\pmod {11}$

Поскольку 2 взаимно просто с модулем 11, то его можно обратить по модулю 11 и найти $2^{-1}\equiv 6\pmod{11}$. Умножая сравнение на 6, получаем решение по модулю 11: $x\equiv 1\pmod {11}$, эквивалентное совокупности двух решений по модулю 22: $x\equiv 1\pmod {22}$ и $x\equiv 12\pmod {22}$.

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

Решение сравнений второй степени сводится к выяснению, является ли данное число квадратичным вычетом (с помощью квадратичного закона взаимности) и последующему вычислению квадратного корня по данному модулю.

Системы сравнений

Простейшая система сравнений относительно попарно взаимно простых модулей $m_1, m_2, \ldots, m_n$

$\left\{ \begin{array}{rcl} x & \equiv & a_1 \pmod {m_1}\\ x & \equiv & a_2 \pmod {m_2}\\ & \ldots & \\ x & \equiv & a_n \pmod {m_n} \end{array} \right.$

всегда разрешима, и её решение единственно по модулю $m_1 \cdot m_2 \cdot \ldots \cdot m_n$ (см. китайская теорема об остатках).

История

Китайская теорема об остатках, известная уже много столетий, утверждает (на современном математическом языке), что кольцо вычетов по модулю произведения нескольких взаимно простых чисел является прямым произведением соответственных множителям колец вычетов.

В значительной степени теория делимости и вычетов была создана Эйлером. Сравнения по модулю впервые использовались Гауссом в его книге «Арифметические исследования», 1801 год. Он же предложил утвердившуюся в математике символику для сравнений.

См. также

• Сложение по модулю 2

Источники

1. ↑ Дэвенпорт Г. Высшая арифметика. Введение в теорию чисел. — М.: Наука, 1965. — 176 с.
2. ↑ Вельшенбах М. Криптография на Си и C++ в действии. — М.: Триумф, 2004. — 461 с.

Ссылки

• Вейль А. Основы теории чисел. — М.: Мир, 1972.
• Виленкин Н. Я. Сравнения и классы вычетов // Квант. — 1978. — № 10. — С. 4—8.
• Виноградов И. М. Основы теории чисел. — М.-Л.: Гос. изд. технико-теоретической литературы, 1952. — 180 с.
• С. В. Сизый. §4. Теория сравнений // Лекции по теории чисел. — Екатеринбург: Уральский государственный университет им. А. М. Горького, 1999.
• Материалы международной научной конференции “Модулярная арифметика”. Виртуальный компьютерный музей (2005). Проверено 31 июля 2010.