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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

Определения[править | править вики-текст]

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

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

a\equiv b\pmod n.

Число n называется модулем сравнения.

Например, 32 и −10 сравнимы по модулю 7, так как оба числа при делении на 7 дают остаток 4:

32 = 7 \cdot 4 + 4; \quad -10 = 7 \cdot (-2) + 4

Эквивалентные формулировки: числа a, b сравнимы по модулю n, если:

  • их разность ab делится на n без остатка;
  • a может быть представлено в виде a = b + kn, где k — некоторое целое число.

Для вышеприведенного примера: 32 и −10 сравнимы по модулю 7, так как их разность 42 делится на 7, и к тому же имеет место представление:

32 = -10 + 6 \cdot 7.

Свойства[править | править вики-текст]

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

Таким образом, отношение сравнимости по модулю 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].

Операции со сравнениями[править | править вики-текст]

Сравнения по одному и тому же модулю обладают многими свойствами обычных равенств. Например, их можно складывать, вычитать и перемножать: если числа a1, a2, …, an и b1, b2, …, bn попарно сравнимы по модулю n, то их суммы a1 + a2 + … + an и b1 + b2 + … + bn, а также произведения a1a2an и b1b2bn тоже сравнимы по модулю n. Если числа a и b сравнимы по модулю n, то их степени ak и bk тоже сравнимы по модулю 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}
где a1 = a/d, b1 = b/d и m1 = m/d являются целыми числами, причем a1 и b1 взаимно просты. Поэтому число a1 можно обратить по модулю m1, то есть найти такое число 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:

\begin{cases}
x \equiv a_1 \pmod {m_1}\\
x \equiv a_2 \pmod {m_2}\\
  \ldots \\
x \equiv a_n \pmod {m_n}
\end{cases}

всегда разрешима, и её решение единственно по модулю m_1 \cdot m_2 \cdots m_n.

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

История[править | править вики-текст]

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

См. также[править | править вики-текст]

Примечания[править | править вики-текст]

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

Ссылки[править | править вики-текст]