Сравнение по модулю натурального числа

Сравнение по модулю натурального числа

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

Определения

Два целых числа a и b сравнимы по модулю натурального числа 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.$

Свойства равенства по модулю

Отношение сравнения по модулю обладает свойствами

• рефлексивности: для любого целого 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.$

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

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

Если числа $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.

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

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

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

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

$a \equiv b \pmod {p_i^{\alpha_i}},\quad i = 1, 2, \dots, 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 по модулю 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, называется приведённой системой вычетов, см. Мультипликативная группа кольца вычетов.

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

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

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

$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. — 180 с.