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

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

Сравнение[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 обладает следующими свойствами:

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

Любые два целых числа сравнимы по модулю 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 год. Он же предложил утвердившуюся в математике символику для сравнений.

См. также

Источники

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

Ссылки


Wikimedia Foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Полезное


Смотреть что такое "Сравнение по модулю" в других словарях:

  • Сравнение по модулю натурального числа — В теории чисел сравнение[уточнить] по модулю натурального числа n задаваемое означенным числом отношение эквивалентности на множестве целых чисел, связанное с делимостью на него. Факторпространство по этому отношению называется «кольцом… …   Википедия

  • Сравнение — Сравнение  многозначный термин. Сравнение  процесс количественного или качественного сопоставления разных свойств (сходств, отличий, преимуществ и недостатков) двух объектов. Сравнение  выяснение, какой из двух объектов лучше в… …   Википедия

  • СРАВНЕНИЕ ПО ПРОСТОМУ МОДУЛЮ — сравнение, в к ром модуль является простым числом. Отличительной чертой теории С. по п. м. является то, что классы вычетов по модулю . образуют конечное поле из рэлементов. Поэтому С. по п. м. можно трактовать как уравнения над простыми конечными …   Математическая энциклопедия

  • СРАВНЕНИЕ —         познават. операция, лежащая в основе суждений о сходстве или различии объектов; с помощью С. выявляются количеств. и качеств. характеристики предметов, классифицируется, упорядочивается и оценивается содержание бытия и познания. Сравнить… …   Философская энциклопедия

  • Сравнение (матем.) — Сравнение (математическое), соотношение между двумя целыми числами а и b, означающее, что разность а ‒ b этих чисел делится на заданное целое число т, называемое модулем С.; пишется а º b (mod т). Например, 2 º 8 (mod 3), т. к. 2‒8… …   Большая советская энциклопедия

  • СРАВНЕНИЕ ОТ НЕСКОЛЬКИХ ПЕРЕМЕННЫХ — сравнение вида где f(x1,, . . ., х п) многочлен от переменных с целыми рациональными коэффициентами, не все из к рых делятся на т. Разрешимость такого сравнения для составного модуля где р 1, . . .,ps различные простые числа, равносильна… …   Математическая энциклопедия

  • СРАВНЕНИЕ — соотношение между целыми числами а и и вида a=b+mk, означающее, что их разность а b делится на заданное целое положительное число т, наз. модулем сравнения; при этом аназ. вычетом целого числа bпо модулю т. Для выражения сравнимости чисел аи bпо… …   Математическая энциклопедия

  • Сравнение — I Сравнение (математическое)         соотношение между двумя целыми числами а и b, означающее, что разность а b этих чисел делится на заданное целое число т, называемое модулем С.; пишется а ≡ b (mod т). Например, 2 ≡ 8 (mod 3), т. к. 2 8 делится …   Большая советская энциклопедия

  • Сравнение в математике — Говорят, что a сравнимо с b по модулю n, если a b делится на n. Это обозначают так: a ≡ b (mod n). С. имеют много сходства с равенствами. Если f(x) целая функция с целыми коэффициентами и а ≡ b (mod n), то f(a) ≡ f(b) (mod n). Решить С. f(x) ≡ 0… …   Энциклопедический словарь Ф.А. Брокгауза и И.А. Ефрона

  • Сравнение, в математике — Говорят, что a сравнимо с b по модулю n, если a b делится на n. Это обозначают так: a ≡ b (mod n). С. имеют много сходства с равенствами. Если f(x) целая функция с целыми коэффициентами и а ≡ b (mod n), то f(a) ≡ f(b) (mod n). Решить С. f(x) ≡ 0… …   Энциклопедический словарь Ф.А. Брокгауза и И.А. Ефрона


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»