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

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

История

Возникновение теории сравнений относится к концу XVIII — началу XIX веков и связано с изучением диофантовых уравнений. Например, одно из первых её применений можно обнаружить в трудах Лежандра, а именно в теореме о разрешимости диофантовых уравнений определенного вида. Также сравнения применялись Эйлером и Лагранжем. Впоследствии Гаусс преобразовал все накопленные сведения в стройную теорию,которая впервые была изложена в его книге «Арифметические исследования», 1801 год. Он же предложил утвердившуюся в математике символику для сравнений.

Определения

Если два целых числа a и b при делении на n дают одинаковые остатки, то они называются сравнимыми (или равноостаточными) по модулю числа n. Шаблон:/рамка Сравнимость чисел a и b записывается в виде формулы (сравнения): $a\equiv b{\pmod {n}}.$ Число n называется модулем сравнения. Определение сравнимости чисел a и b по модулю n равносильно любому из следующих утверждений: Разность чисел a и b делится на n без остатка; Число a может быть представлено в виде a = b + kn, где k — некоторое целое число. Доказательство Докажем необходимость условий 1 и 2. Допустим, что $a\equiv b{\pmod {n}}.$ Пусть, $a=m_{1}n+r,0\leqslant r<m$, $b=m_{2}n+r,0\leqslant r<m$ Тогда $a-b=(m_{1}-m_{2})n,$ $a=m_{1}n+r=m_{1}n+r+m_{2}n-m_{2}n=b+m_{1}-m_{2})n=b+kn$, где $k=m_{1}-m_{2}$. Теперь докажем достаточность условий 1 и 2. Пусть, $a=b+kn,$ И b представимо в виде: $b=m_{1}n+r,0\leqslant r<m$. Тогда $a=mn+r,0\leqslant r<m,$, где $m=k+m_{1}$. Таким образом $a\equiv b{\pmod {n}}.$. Доказана равносильность определения условию 2, которое эквивалентно условию 1. Например, 32 и −10 сравнимы по модулю 7, так как оба числа при делении на 7 дают остаток 4: $32=7\cdot 4+4;\quad -10=7\cdot (-2)+4.$ Также, 32 и −10 сравнимы по модулю 7, так как их разность 42 делится на 7, и к тому же имеет место представление: $32=-10+6\cdot 7.$ Свойства Для фиксированного натурального числа 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}}.$ Таким образом, отношение сравнимости по модулю n является отношением эквивалентности на множестве целых чисел. Кроме вышеперечисленных свойств, для сравнений справедливы следующие утверждения: любые два целых числа сравнимы по модулю 1. если числа a и b сравнимы по модулю n, и m является делителем n, то a и b сравнимы по модулю m. Доказательство Пусть, $a\equiv b{\pmod {n}}.$ Следовательно, $a-b=nt.$ Так как m является делителем числа n, то $n=md$. Следовательно, $a-b=nt=mdt=qm,(q=mt)$ и $a\equiv b{\pmod {m}}$ по определению. если числа a и b сравнимы по нескольким модулям n1,n2,...,nk то они сравнимы по модулю,равному наименьшему общему кратному модулей :[n1,n2,...,nk]. Доказательство Пусть, $a\equiv b{\pmod {n}}_{i},i=1,2,...,k.$ Следовательно, $a-b=n_{i}t.$ Так как разность a-b кратна каждому ni, то она кратна и их наименьшему общему кратному Следствие: Для того, чтобы числа 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$. Операции со сравнениями Сравнения по одному и тому же модулю обладают многими свойствами обычных равенств. Например, их можно складывать, вычитать и перемножать: если числа a1, a2, …, an и b1, b2, …, bn попарно сравнимы по модулю n, то их суммы a1 + a2 + … + an и b1 + b2 + … + bn, а также произведения a1a2 … an и b1b2 … bn тоже сравнимы по модулю n. При этом нельзя выполнять эти операции со сравнениями, если их модули не совпадают. Отдельно, следует отметить, что к обеим частям сравнения можно прибавить одно и то же число, также можно перенести число из одно части сравнения в другую со сменой знака. Если числа a и b сравнимы по модулю n, то их степени ak и bk тоже сравнимы по модулю n при любом натуральном k. K любой из частей сравнения можно прибавить целое число, кратное модуля, то есть, если числа a и b сравнимы по модулю некоторого числа n, то и a+t1n сравнимо с b+t2n по модулю n (t1 и t2 — произвольных целые числа) .Также обе части сравнения и модуль можно умножить на одно и то же число, то есть, если числа a и b сравнимы по модулю некоторого целого числа n, то и числа aq и bq сравнимы по модулю числа nq,где q — целое. Сравнения, однако, нельзя, вообще говоря, делить друг на друга или на другие числа. Пример: $14\equiv 20{\pmod {6}}$, однако, сократив на 2, мы получаем ошибочное сравнение: $7\equiv 10{\pmod {6}}$. Правила сокращения для сравнений следующие. Можно делить обе части сравнения на число, но только взаимно простое с модулем: если $ac\equiv bc{\pmod {n}}$ и НОД $(c,n)=1,$ то $a\equiv b{\pmod {n}}$. Если число c не взаимно просто с модулем, то сокращать на c нельзя. Например, $2\equiv 8{\pmod {6}}$, но $1\not \equiv 4{\pmod {6}}$. Можно одновременно разделить обе части сравнения и модуль на их общий делитель: если $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. Пусть для определенности r―остаток от деления любого из представителей выбранного класса на n, тогда любое число m из этого класса можно представить в виде m=nt+r, где t—целое. Вычет равный остатку ri называется наименьшим неотрицательным вычетом, а вычет $\rho$, самый малый по абсолютной величине, называется абсолютно наименьшим вычетом.При r<n/2 $\rho$=r,в противном случае $\rho$=r-n.Если n-чётное и r=n/2, то $\rho$=-r/2. Поскольку сравнимость по модулю 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,\pm 1,\pm 2,...,\pm {\tfrac {n-1}{2}}$, в случае нечётного $n$, и чисел $0,\pm 1,\pm 2,...,\pm ({\tfrac {n}{2}}-1),{\tfrac {n}{2}}$ в случае чётного $n$. Максимальный набор попарно несравнимых по модулю n чисел, взаимно простых с n, называется приведённой системой вычетов по модулю n. Всякая приведённая система вычетов по модулю n содержит $\varphi (n)$ элементов, где $\varphi (\cdot )$ — функция Эйлера. Например, для числа n=42. Полная система вычетов может быть представлена числами: 0,1,2,3,...,21,22,23,...,39,40,41, а приведенная—1,5,11,13,17,19,23,25,29,31,37,41. Решение сравнений Сравнения первой степени В теории чисел, криптографии и других областях науки часто возникает задача поиска решений сравнения первой степени вида: $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 и m1 взаимно просты. Поэтому число a1 можно обратить по модулю m1, то есть найти такое число c, что $c\cdot a_{1}\equiv 1{\pmod {m_{1}}}$ (другими словами, $c\equiv a_{1}^{-1}{\pmod {m_{1}}}$). Теперь решение находится умножением полученного сравнения на c: $x\equiv ca_{1}x\equiv cb_{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}}$. Сравнения второй степени Сравнения второй степени по простому модулю n имеет следующий общий вид: $c_{0}x^{2}+c_{1}x+c\equiv 0{\pmod {n}}.$ Это выражение можно привести к виду: $(x+b)^{2}\equiv a{\pmod {n}}.$, а при замене z=x+b упрощается максимально: $(z)^{2}\equiv a{\pmod {n}}.$. Решение этого сравнения сводится к выяснению, является ли данное число квадратичным вычетом (с помощью квадратичного закона взаимности) и последующему вычислению квадратного корня по данному модулю. Для вычисления квадратного корня из квадратичного вычета существует вероятностный метод Берлекэмпа. Системы сравнений Основная статья: Китайская теорема об остатках Китайская теорема об остатках утверждает, что система сравнений с попарно взаимно простыми модулями $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}$. Другими словами, китайская теорема об остатках утверждает, что кольцо вычетов по модулю произведения нескольких взаимно простых чисел является прямым произведением соответствующих множителям колец вычетов. Применение Методы теории сравнений используются в теории чисел, теории групп, теории колец, теории узлов, общей алгебре, криптографии, информатике, химии и других областях. Например,сравнения часто применяются для вычисления контрольных сумм, используемых в идентификаторах. Так для определения ошибок при вводе международного номера банковского счета используется сравнение по модулю 97. В криптографии сравнения можно встретить в системах с открытым ключом, использующих, например, алгоритм RSA или протокол Диффи — Хеллмана.Также, модульная арифметика обеспечивает конечные поля,над которыми затем строятся эллиптические кривые, и используется в различных протоколах с симметричным ключем (AES, IDEA). В химии последняя цифра в регистрационном номере CAS является значением контрольной суммы, которая вычисляется путём сложения последней цифры номера, умноженной на 1, второй справа цифры, умноженной на 2, третьей, умноженной на три и так далее до первой слева цифры, завершаясь вычислением остатка от деления на 10. См. также Сложение по модулю 2 Возведение в степень по модулю Показатель числа по модулю Алгоритмы быстрого возведения в степень по модулю Примечания Литература Вейль А. Основы теории чисел. — М.: Мир, 1972. Виленкин Н. Я. Сравнения и классы вычетов // Квант. — 1978. — № 10. — С. 4—8. Виноградов И. М. Основы теории чисел. — М.—Л.: Гос. изд. технико-теоретической литературы, 1952. — 180 с. С. В. Сизый. §4. Теория сравнений // Лекции по теории чисел. — Екатеринбург: Уральский государственный университет им. А. М. Горького, 1999. А. А. Бухштаб. Теория чисел. — М.: «Просвещение», 1966. — 384 с. Ю. Л. Сагалович. Введение в алгебраические коды. — 2-е изд. — М.: ИППИ РАН, 2010. — 320 с. Н. Коблиц. Курс теории чисел и криптографии / пер. с англ. М. А. Михайловой и В. Е. Тараканова,под ред. А. М. Зубкова. — М.: Научное изд-во ТВП, 2001. — 254 с. Материалы международной научной конференции “Модулярная арифметика”  (неопр.). Виртуальный компьютерный музей (2005). Дата обращения: 31 июля 2010.