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

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

В дискретной математике, для сравнений по модулю используется также термин модульная (или модулярная) арифметика.

Определения

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

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

• Пример: 32 и −10 сравнимы по модулю 7, так как 32 = 7∙4 + 4, −10 = 7∙(-2) + 4.

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

$a\equiv b\pmod n.$

Свойства

Отношение сравнения является отношением эквивалентности и обладает многими свойствами обычных равенств. Например, их можно складывать и перемножать: если

$a_1 \equiv b_1 \pmod n; \qquad a_2 \equiv b_2 \pmod n,$

то

$a_1a_2 \equiv b_1b_2 \pmod n; \qquad a_1+a_2 \equiv b_1+b_2 \pmod n.$

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

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

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

Другие свойства:

• Если $a \equiv b\pmod {m_1}$ и $a \equiv b\pmod {m_2}$, то $a \equiv b \pmod m$, где m = [m₁,m₂].
• Если $a \equiv b \pmod m$, то a, b сравнимы по любому модулю — делителю m.

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

Множество всех чисел, сравнимых с 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 простое — конечным полем.

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

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

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

$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₁ = a / d, b₁ = b / d и m₁ = m / d являются целыми числами, причем a₁ и m₁ взаимно просты. Поэтому число a₁ можно обратить по модулю m₁, то есть найти такое число 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, можно сократить левую и правую части на 2. В итоге получаем одно решение по модулю 11: $x\equiv 1\pmod {11}$, эквивалентное двум решениям по модулю 22: $x\equiv 1\pmod {22};\ x\equiv 12\pmod {22}$.

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

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

История

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

Ссылки

• Вейль А., Основы теории чисел, М.:Мир, 1972.
• Виленкин Н. Я., Сравнения и классы вычетов, Квант, № 10, 1978.
• Виноградов И. М., Основы теории чисел, М.: ГИТТЛ, 1952.