Класс вычетов - NiNa.Az

Запрос «Модульная арифметика»^[d] перенаправляется сюда. На эту тему нужно создать отдельную статью.

Сравне́ние двух целых чисел по мо́дулю натурального числа ${\displaystyle m}$ — математическая операция, позволяющая ответить на вопрос о том, дают ли два выбранных целых числа при делении на ${\displaystyle m}$ один и тот же остаток. Любое целое число при делении на ${\displaystyle m}$ даёт один из ${\displaystyle m}$ возможных остатков: число от 0 до ${\displaystyle m-1}$; это значит, что все целые числа можно разделить на ${\displaystyle m}$ групп, каждая из которых отвечает определённому остатку от деления на ${\displaystyle m}$. Эти группы называются классами вычетов по модулю ${\displaystyle m}$, а содержащиеся в них целые числа — вычетами по модулю ${\displaystyle m}$➤.

Арифметические операции с остатками чисел по фиксированному модулю образуют мо́дульную арифме́тику или модуля́рную арифметику, которая широко применяется в математике, информатике и криптографии.

История

Предпосылкой к созданию теории сравнений стало восстановление сочинений Диофанта, которые были выпущены в подлиннике и с латинским переводом, благодаря Баше де Мезириаку, в 1621 году. Их изучение привело Ферма́ к открытиям, которые по значению существенно опередили своё время. Например, в письме к Френиклю де Бесси 18 октября 1640 года он сообщил без доказательства теорему, впоследствии получившую название малой теоремы Ферма. В современной формулировке теорема утверждает, что если ${\displaystyle p}$ — простое число и ${\displaystyle a}$ — целое число, не делящееся на ${\displaystyle p}$, то

${\displaystyle a^{p-1}\equiv 1{\pmod {p}}}$ .

Первое доказательство этой теоремы принадлежит Лейбницу, причём он открыл указанную теорему независимо от Ферма́ не позднее 1683 года и сообщил об этом с приведением точного доказательства Бернулли. Кроме этого, Лейбницем был предложен прообраз формулировки теоремы Вильсона.

Позже изучение вопросов, посвященных теории чисел и теории сравнений, было продолжено Эйлером, который ввел квадратичный закон взаимности и обобщил теорему Ферма, установив, что

${\displaystyle a^{\varphi (n)}\equiv 1{\pmod {n}},}$

где ${\displaystyle \varphi (n)}$ — функция Эйлера.

Понятие и символьное обозначение сравнений было введено Гауссом, как важный инструмент для обоснования его арифметической теории, работа над которой была начата им в 1797 году. В начале этого периода Гауссу ещё не были известны труды его предшественников, поэтому результаты его работы, изложенные в первых трёх главах его книги «Арифметические исследования» (1801 год), были в основном уже известны, однако методы, которые он использовал для доказательств, оказались абсолютно новыми, имеющими высшую важность для развития теории чисел. Используя эти методы, Гаусс преобразовал все накопленные до него сведения, связанные с операциями сравнения по модулю, в стройную теорию, которая впервые была изложена в этой же книге. Кроме этого, он исследовал сравнения первой и второй степени, теорию квадратичных вычетов и связанный с ней квадратичный закон взаимности.

Определения

Если два целых числа ${\displaystyle a}$ и ${\displaystyle b}$ при делении на ${\displaystyle m}$ дают одинаковые остатки, то они называются сравнимыми (или равноостаточными) по модулю числа ${\displaystyle m}$.

Сравнимость чисел ${\displaystyle a}$ и ${\displaystyle b}$ записывается в виде формулы (сравнения):

${\displaystyle a\equiv b{\pmod {m}}.}$

Число ${\displaystyle m}$ называется модулем сравнения.

Определение сравнимости чисел ${\displaystyle a}$ и ${\displaystyle b}$ по модулю ${\displaystyle m}$ равносильно любому из следующих утверждений:

• разность чисел ${\displaystyle a}$ и ${\displaystyle b}$ делится на ${\displaystyle m}$ без остатка;
• число ${\displaystyle a}$ может быть представлено в виде ${\displaystyle a=b+k\cdot m}$, где ${\displaystyle k}$ — некоторое целое число.

Доказательство

• Необходимость условий 1 и 2 доказывается следующим образом:

${\displaystyle a\equiv b{\pmod {m}}.}$

Тогда в предположении, что

${\displaystyle a=n_{1}m+r,\;0\leqslant r<m,}$

${\displaystyle b=n_{2}m+r,\;0\leqslant r<m,}$

выполняются 1 и 2:

${\displaystyle a-b=(n_{1}m+r)-(n_{2}m+r)=(n_{1}-n_{2})m}$ (то есть, разность ${\displaystyle a}$ и ${\displaystyle b}$ делится на ${\displaystyle m}$ без остатка);

${\displaystyle a=n_{1}m+r=n_{1}m+r+(n_{2}m-n_{2}m)=b+(n_{1}-n_{2})m=b+km,}$ где ${\displaystyle k=n_{1}-n_{2}}$ (то есть, ${\displaystyle a}$ может быть представлено в виде ${\displaystyle a=b+km}$).

• Достаточность условий 1 и 2:

${\displaystyle a=b+km.}$

Из доказательства необходимого условия число ${\displaystyle b}$ представимо в виде:

${\displaystyle b=n_{2}m+r,\;0\leqslant r<m.}$

Тогда

${\displaystyle a=b+km=(n_{2}m+r)+km=nm+r,\;0\leqslant r<m,}$ где ${\displaystyle n=k+n_{2}.}$

Таким образом

${\displaystyle a\equiv b{\pmod {m}}.}$

Доказана равносильность определения условию 2, которое эквивалентно условию 1.

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

${\displaystyle 32=7\cdot 4+4;}$

${\displaystyle -10=7\cdot (-2)+4.}$

Также числа 32 и -10 сравнимы по модулю 7, так как их разность ${\displaystyle 32-(-10)=42}$ делится на 7 и к тому же имеет место представление

${\displaystyle 32=6\cdot 7+(-10).}$

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

Для фиксированного натурального числа ${\displaystyle m}$ отношение сравнимости по модулю ${\displaystyle m}$ обладает следующими свойствами:

• свойством рефлексивности: для любого целого ${\displaystyle a}$ справедливо ${\displaystyle a\equiv a{\pmod {m}};}$
• свойством симметричности: если ${\displaystyle a\equiv b{\pmod {m}},}$ то ${\displaystyle b\equiv a{\pmod {m}};}$
• свойством транзитивности: если ${\displaystyle a\equiv b{\pmod {m}}}$ и ${\displaystyle b\equiv c{\pmod {m}},}$ то ${\displaystyle a\equiv c{\pmod {m}}.}$

Таким образом, отношение сравнимости по модулю ${\displaystyle m}$ является отношением эквивалентности на множестве целых чисел.

Кроме вышеперечисленных свойств, для сравнений справедливы следующие утверждения:

• любые два целых числа сравнимы по модулю 1;
• если числа ${\displaystyle a}$ и ${\displaystyle b}$ сравнимы по модулю ${\displaystyle m}$, и число ${\displaystyle d}$ является делителем ${\displaystyle m}$, то ${\displaystyle a}$ и ${\displaystyle b}$ сравнимы по модулю ${\displaystyle d}$;

Доказательство

Пусть

${\displaystyle a\equiv b{\pmod {m}}.}$

Следовательно

${\displaystyle a-b=mt,}$ где ${\displaystyle t}$ — некое целое число.

Так как ${\displaystyle d}$ является делителем числа ${\displaystyle m}$, то

${\displaystyle m=cd,}$ где ${\displaystyle c}$ — некое целое число.

Следовательно

${\displaystyle a-b=mt=(cd)t=qd,}$ где ${\displaystyle q=ct,}$

и

${\displaystyle a\equiv b{\pmod {d}}}$

по определению.

• если числа ${\displaystyle a}$ и ${\displaystyle b}$ сравнимы по ${\displaystyle k}$ модулям ${\displaystyle {m_{1},m_{2},...,m_{k}},}$ то они сравнимы по модулю, равному наименьшему общему кратному модулей ${\displaystyle {m_{1},m_{2},...,m_{k}}}$.

Доказательство

Пусть

${\displaystyle a\equiv b{\pmod {m_{i}}},}$ где ${\displaystyle i=1,2,...,k.}$

Следовательно

${\displaystyle a-b=m_{i}t_{i}.}$

Так как разность ${\displaystyle a-b}$ кратна каждому ${\displaystyle m_{i}}$, то она кратна и их наименьшему общему кратному.

Следствие:

Для того, чтобы числа ${\displaystyle a}$ и ${\displaystyle b}$ были сравнимы по модулю ${\displaystyle m}$, каноническое разложение на простые сомножители которого имеет вид

${\displaystyle m=\prod _{i=1}^{d}p_{i}^{\alpha _{i}},}$

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

${\displaystyle a\equiv b{\pmod {p_{i}^{\alpha _{i}}}},}$ где ${\displaystyle i=1,2,\ldots ,d}$.

Операции со сравнениями

Сравнения по одному и тому же модулю обладают многими свойствами обычных равенств. Например, их можно складывать, вычитать и перемножать: если числа ${\displaystyle a_{1},a_{2},\ldots ,a_{n}}$ и ${\displaystyle b_{1},b_{2},\ldots ,b_{n}}$ попарно сравнимы по модулю ${\displaystyle m}$, то их суммы ${\displaystyle a_{1}+a_{2}+\ldots +a_{n}}$ и ${\displaystyle b_{1}+b_{2}+\ldots +b_{n}}$, а также произведения ${\displaystyle a_{1}\cdot a_{2}\cdot ...\cdot a_{n}}$ и ${\displaystyle b_{1}\cdot b_{2}\cdot ...\cdot b_{n}}$ тоже сравнимы по модулю ${\displaystyle m}$:

${\displaystyle (a_{1}+a_{2}+\ldots +a_{n})\equiv (b_{1}+b_{2}+\ldots +b_{n}){\pmod {m}};}$

${\displaystyle (a_{1}\cdot a_{2}\cdot \ldots \cdot a_{n})\equiv (b_{1}\cdot b_{2}\cdot \ldots \cdot b_{n}){\pmod {m}}.}$

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

К обеим частям сравнения можно прибавить одно и то же число ${\displaystyle c}$:

${\displaystyle (a+c)\equiv (b+c){\pmod {m}}.}$

Также можно перенести число из одной части сравнения в другую со сменой знака:

${\displaystyle a\equiv (b+c){\pmod {m}};}$

${\displaystyle (a-c)\equiv b{\pmod {m}}.}$

Если числа ${\displaystyle a}$ и ${\displaystyle b}$ сравнимы по модулю ${\displaystyle m}$, то их степени ${\displaystyle a^{k}}$ и ${\displaystyle b^{k}}$ тоже сравнимы по модулю ${\displaystyle m}$ при любом натуральном ${\displaystyle k}$:

${\displaystyle a^{k}\equiv b^{k}{\pmod {m}}.}$

K любой из частей сравнения можно прибавить целое число, кратное модулю, то есть, если числа ${\displaystyle a}$ и ${\displaystyle b}$ сравнимы по модулю некоторого числа ${\displaystyle m}$, то и ${\displaystyle a+t_{1}}$ сравнимо с ${\displaystyle b+t_{2}}$ по модулю ${\displaystyle m}$, где ${\displaystyle t_{1}}$ и ${\displaystyle t_{2}}$ — произвольные целые числа, кратные ${\displaystyle m}$:

${\displaystyle (a+t_{1})\equiv (b+t_{2}){\pmod {m}}.}$

Также обе части сравнения и модуль можно умножить на одно и то же число, то есть, если числа ${\displaystyle a}$ и ${\displaystyle b}$ сравнимы по модулю некоторого целого числа ${\displaystyle m}$, то и числа ${\displaystyle aq}$ и ${\displaystyle bq}$ сравнимы по модулю числа ${\displaystyle mq}$, где ${\displaystyle q}$ — целое:

${\displaystyle aq\equiv bq{\pmod {mq}}.}$

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

• Можно делить обе части сравнения на число, но только взаимно простое с модулем: если

${\displaystyle {ad}\equiv {bd}{\pmod {m}}}$ и НОД${\displaystyle {(d,m)=1},}$ то

${\displaystyle a\equiv b{\pmod {m}}}$.

Если, число ${\displaystyle d}$ не взаимно просто с модулем, как было в примере, указанном выше, то сокращать на ${\displaystyle d}$ нельзя.

• Можно одновременно разделить обе части сравнения и модуль на их общий делитель:

если ${\displaystyle {ac}\equiv {bc}{\pmod {mc}}}$, то ${\displaystyle a\equiv b{\pmod {m}}}$.

Пример

Применение сравнений позволяет легко получать разнообразные признаки делимости. Например, выведем признак делимости натурального числа N на 7. Запишем ${\displaystyle N}$ в виде ${\displaystyle 10a+b}$ (то есть отделим цифру единиц). Условие, что ${\displaystyle N}$ делится нацело на 7, можно записать в виде: ${\displaystyle 10a+b\equiv 0{\pmod {7}}.}$ Умножим это сравнение на ${\displaystyle -2:}$

${\displaystyle -20a-2b\equiv 0{\pmod {7}}.}$

Или, прибавив слева число ${\displaystyle 21a,}$ кратное модулю:

${\displaystyle a-2b\equiv 0{\pmod {7}}.}$

Отсюда вытекает следующий признак делимости на 7: надо вычесть из числа десятков удвоенное число единиц, затем повторять эту операцию до тех пор, пока не получится двузначное или однозначное число; если оно делится на 7, то и исходное число делится. Например, пусть ${\displaystyle N=22624.}$ Алгоритм проверки:

${\displaystyle N_{1}=2262-2\cdot 4=2254;\ N_{2}=225-2\cdot 4=217;N_{3}=21-2\cdot 7=7}$

Вывод: 22624 делится на 7.

Связанные определения

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

Множество всех чисел, сравнимых с ${\displaystyle a}$ по модулю ${\displaystyle m}$, называется классом вычетов ${\displaystyle a}$ по модулю ${\displaystyle m}$, и обычно обозначается ${\displaystyle [a]_{m}}$ или ${\displaystyle {\bar {a}}_{m}}$. Таким образом, сравнение ${\displaystyle a\equiv b{\pmod {m}}}$ равносильно равенству классов вычетов ${\displaystyle [a]_{m}=[b]_{m}}$.

Любое число класса вычетов называется вычетом по модулю ${\displaystyle m}$. Пусть для определённости ${\displaystyle r}$ ― остаток от деления любого из представителей выбранного класса на ${\displaystyle m}$, тогда любое число ${\displaystyle q}$ из этого класса вычетов можно представить в виде ${\displaystyle q=mt+r}$, где ${\displaystyle t}$ — целое. Вычет, равный остатку ${\displaystyle r}$ (${\displaystyle q=r}$ при ${\displaystyle t=0}$) называется наименьшим неотрицательным вычетом, а вычет ${\displaystyle \rho }$ (${\displaystyle q=\rho }$), самый малый по абсолютной величине, называется абсолютно наименьшим вычетом. При ${\displaystyle r<{\frac {m}{2}}}$ получаем, что ${\displaystyle \rho =r}$, в противном случае ${\displaystyle \rho =r-m}$. Если ${\displaystyle m}$ — чётное и ${\displaystyle r={\frac {m}{2}}}$, то ${\displaystyle \rho =-{\frac {m}{2}}}$.

Поскольку сравнимость по модулю ${\displaystyle m}$ является отношением эквивалентности на множестве целых чисел ${\displaystyle \mathbb {Z} }$, то классы вычетов по модулю ${\displaystyle m}$ представляют собой классы эквивалентности; их количество равно ${\displaystyle m}$.

Множество всех классов вычетов по модулю ${\displaystyle m}$ обозначается ${\displaystyle \mathbb {Z} _{m}}$ или ${\displaystyle \mathbb {Z} /m\mathbb {Z} }$ или ${\displaystyle \mathbb {Z} /(m)}$.

Операции сложения и умножения на ${\displaystyle \mathbb {Z} }$ соответствующие операции на множестве ${\displaystyle \mathbb {Z} _{m}}$:

${\displaystyle [a]_{m}+[b]_{m}=[a+b]_{m};}$

${\displaystyle [a]_{m}\cdot [b]_{m}=[a\cdot b]_{m}.}$

Относительно этих операций множество ${\displaystyle \mathbb {Z} _{m}}$ является конечным кольцом, а для простого ${\displaystyle m}$ — конечным полем.

См. также: Мультипликативная группа кольца вычетов

Системы вычетов

Система вычетов позволяет осуществлять арифметические операции над конечным набором чисел, не выходя за его пределы. Полная система вычетов по модулю ${\displaystyle m}$ ― любой набор из ${\displaystyle m}$ попарно несравнимых по модулю ${\displaystyle m}$ целых чисел. Обычно в качестве полной системы вычетов по модулю ${\displaystyle m}$ берётся одно из двух множеств:

• наименьшие неотрицательные вычеты, то есть числа:

${\displaystyle 0,1,\ldots ,m-1}$

• или абсолютно наименьшие вычеты, состоящие в случае нечётного ${\displaystyle m}$ из чисел

${\displaystyle 0,\pm 1,\pm 2,\ldots ,\pm {\frac {m-1}{2}}}$,

и в случае чётного ${\displaystyle m}$ из чисел

${\displaystyle 0,\pm 1,\pm 2,\ldots ,\pm \left({\frac {m}{2}}-1\right),-{\frac {m}{2}}}$

Максимальный набор попарно несравнимых по модулю ${\displaystyle m}$ чисел, взаимно простых с ${\displaystyle m}$, называется приведённой системой вычетов по модулю ${\displaystyle m}$. Всякая приведённая система вычетов по модулю ${\displaystyle m}$ содержит ${\displaystyle \varphi (m)}$ элементов, где ${\displaystyle \varphi (\cdot )}$ — функция Эйлера.

Например, для числа ${\displaystyle m=42}$ полная система вычетов может быть представлена числами 0, 1, 2, 3, …, 21, 22, 23, …, 39, 40, 41, а приведённая — 1, 5, 11, 13, 17, 19, 23, 25, 29, 31, 37, 41.

Сравнения в кольце многочленов над полем

Рассматривается кольцо многочленов ${\displaystyle K[x]}$ над полем ${\displaystyle K}$. Два многочлена ${\displaystyle g_{1}}$ и ${\displaystyle g_{2}}$, принадлежащие выбранному кольцу, называются сравнимыми по модулю многочлена ${\displaystyle f}$, если их разность ${\displaystyle g_{1}-g_{2}}$ делится на ${\displaystyle f}$ без остатка. Сравнение обозначается следующим образом:

${\displaystyle g_{1}\equiv g_{2}{\pmod {f}}.}$

Так же, как и в кольце целых чисел, такие сравнения можно складывать, вычитать и перемножать.

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

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

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

${\displaystyle a\cdot x\equiv b{\pmod {m}}.}$

Решение такого сравнения начинается с вычисления ${\displaystyle d=}$ НОД${\displaystyle (a,m)}$. При этом возможны два случая:

• если ${\displaystyle b}$ не кратно ${\displaystyle d}$, то у сравнения нет решений;
• если ${\displaystyle b}$ кратно ${\displaystyle d}$, то у сравнения существует единственное решение по модулю ${\displaystyle {\frac {m}{d}}}$, или, что то же самое, ${\displaystyle d}$ решений по модулю ${\displaystyle m}$. В этом случае в результате сокращения исходного сравнения на ${\displaystyle d}$ получается сравнение:

${\displaystyle a_{1}x\equiv b_{1}{\pmod {m_{1}}},}$

где ${\displaystyle a_{1}={\frac {a}{d}},}$ ${\displaystyle b_{1}={\frac {b}{d}}}$ и ${\displaystyle m_{1}={\frac {m}{d}}}$ являются целыми числами, причём ${\displaystyle a_{1}}$ и ${\displaystyle m_{1}}$ взаимно просты. Поэтому число ${\displaystyle a_{1}}$ можно обратить по модулю ${\displaystyle m_{1}}$, то есть найти такое число ${\displaystyle c}$, что ${\displaystyle c\cdot a_{1}\equiv 1{\pmod {m_{1}}}}$ (другими словами, ${\displaystyle c\equiv a_{1}^{-1}{\pmod {m_{1}}}}$). Теперь решение находится умножением полученного сравнения на ${\displaystyle c}$:

${\displaystyle x\equiv ca_{1}x\equiv cb_{1}\equiv a_{1}^{-1}b_{1}{\pmod {m_{1}}}.}$

Практическое вычисление значения ${\displaystyle c}$ можно осуществить разными способами: с помощью теоремы Эйлера, алгоритма Евклида, теории цепных дробей (см. алгоритм) и др. В частности, теорема Эйлера позволяет записать значение ${\displaystyle c}$ в виде:

${\displaystyle c\equiv a_{1}^{-1}\equiv a_{1}^{\varphi (m_{1})-1}{\pmod {m_{1}}}}$.

Примеры

Пример 1. Для сравнения

${\displaystyle 6x\equiv 26{\pmod {22}}}$

имеем ${\displaystyle d=2}$, поэтому по модулю 22 сравнение имеет два решения. Заменим 26 на 4, сравнимое с ним по модулю 22, и затем сократим все три числа на 2:

${\displaystyle 3x\equiv 2{\pmod {11}}}$

Поскольку 3 взаимно просто с модулем 11, то его можно обратить по модулю 11 и найти

${\displaystyle 3^{-1}\equiv 4{\pmod {11}}}$.

Умножая сравнение на 4, получаем решение по модулю 11:

${\displaystyle x\equiv 8{\pmod {11}}}$,

эквивалентное совокупности двух решений по модулю 22:

${\displaystyle x\equiv 8{\pmod {22}}}$ и ${\displaystyle x\equiv 19{\pmod {22}}}$.

Пример 2. Дано сравнение:

${\displaystyle 100x\equiv 41{\pmod {65537}}.}$ Отметим, что модуль ${\displaystyle 65537}$ — простое число.

Первый способ решения — воспользоваться соотношением Безу. С помощью алгоритма Евклида или программы, приведенной в статье о соотношении Безу, находим, что это соотношение для чисел ${\displaystyle 100}$ и ${\displaystyle 65537}$ имеет вид:

${\displaystyle 17695\cdot 100+(-27)\cdot 65537=1,}$ или ${\displaystyle 17695\cdot 100\equiv 1{\pmod {65537}}}$

Умножив обе части этого сравнения на 41, получим:

${\displaystyle 100\cdot 725495\equiv 41{\pmod {65537}}}$

Отсюда следует, что ${\displaystyle 725495}$ есть решение исходного сравнения. Удобнее заменить его на сравнимое с ним ${\displaystyle 4588}$ (остаток от деления ${\displaystyle 725495}$ на ${\displaystyle 65537}$). Ответ: ${\displaystyle x\equiv 4588{\pmod {65537}}.}$

Второй способ решения, более простой и быстрый, не требует построения соотношения Безу, но также эквивалентен алгоритму Евклида.

Шаг 1. Делим модуль на коэффициент при x с остатком: ${\displaystyle 65537=100\cdot 655+37}$. Умножим обе части исходного сравнения на частное ${\displaystyle 655}$ и прибавим ${\displaystyle 37x}$; получим: ${\displaystyle 65537x\equiv 26855+37x{\pmod {65537}}}$, но левая часть кратна ${\displaystyle 65537}$, то есть сравнима с нулём, откуда:

${\displaystyle 37x\equiv -26855{\pmod {65537}}}$

Мы получили при ${\displaystyle x}$ коэффициент 37 вместо 100. На каждом следующем шаге уменьшаем аналогично, пока не получим единицу.

Шаг 2. Аналогично делим на новый коэффициент при x: ${\displaystyle 65537=37\cdot 1771+10}$. Умножим обе части сравнения, полученного в предыдущем шаге, на частное ${\displaystyle 1771}$ и прибавим ${\displaystyle 10x}$; снова заменив левую часть на ноль, получим:

${\displaystyle 10x\equiv 47560205{\pmod {65537}}}$

${\displaystyle 47560205}$ заменяем на его остаток при делении на ${\displaystyle 65537,}$ равный ${\displaystyle 45880}$:

${\displaystyle 10x\equiv 45880{\pmod {65537}}}$

Далее можно было бы сделать аналогично ещё 5 шагов, но проще разделить обе части сравнения на 10 и сразу получить результат: ${\displaystyle x\equiv 4588{\pmod {65537}}.}$

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

Сравнения второй степени по простому модулю m имеет следующий общий вид:

${\displaystyle c_{0}x^{2}+c_{1}x+c\equiv 0{\pmod {m}}.}$

Это выражение можно привести к виду

${\displaystyle (x+b)^{2}\equiv a{\pmod {m}},}$

а при замене ${\displaystyle z=x+b}$ упрощается до

${\displaystyle z^{2}\equiv a{\pmod {m}}.}$

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

Системы сравнений

Основная статья: Китайская теорема об остатках

Китайская теорема об остатках утверждает, что система сравнений с попарно взаимно простыми модулями ${\displaystyle m_{1},m_{2},\ldots ,m_{n}}$:

${\displaystyle {\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}}}$

всегда разрешима, и её решение единственно по модулю ${\displaystyle m_{1}\cdot m_{2}\cdot \ldots \cdot m_{n}}$.

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

Применение

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

Например, сравнения часто применяются для вычисления контрольных сумм, используемых в идентификаторах. Так, для определения ошибок при вводе международного номера банковского счета используется сравнение по модулю 97.

В криптографии сравнения можно встретить в системах с открытым ключом, использующих, например, алгоритм RSA или протокол Диффи — Хеллмана. Также, модульная арифметика обеспечивает конечные поля, над которыми затем строятся эллиптические кривые, и используется в различных протоколах с симметричным ключом (AES, IDEA).

В химии последняя цифра в регистрационном номере CAS является значением контрольной суммы, которая вычисляется путём сложения последней цифры номера, умноженной на 1, второй справа цифры, умноженной на 2, третьей, умноженной на три и так далее до первой слева цифры, завершаясь вычислением остатка от деления на 10

См. также

• Сложение по модулю 2
• Возведение в степень по модулю
• Показатель числа по модулю
• Алгоритмы быстрого возведения в степень по модулю

Примечания

1. Вельшенбах М. Глава 5. Модульная математика: вычисление в классах вычетов. // Криптография на Си и C++ в действии. — М.: «Триумф», 2004. — С. 81—95. — 464 с. — ISBN 5-89392-083-X.
2. Материалы международной научной конференции “Модулярная арифметика”  (неопр.). Виртуальный компьютерный музей (2005). Дата обращения: 31 июля 2010. Архивировано 5 октября 2007 года.
3. Егоров А. А. Сравнения по модулю и арифметика остатков // Квант. — 1970. — № 5. — С. 28—33. Архивировано 4 марта 2016 года.
4. Французский математик, член французской академии наук с 1666.
5. Вилейтнер Г. Глава III. Теория чисел // История математики от Декарта до середины XIX / пер. с нем. под. ред. А. П. Юшкевича. — М.: Государственное издательство физико-математической литературы, 1960. — С. 69—84. — 467 с. Архивировано 24 сентября 2015 года.
6. Степанов С. А. Глава 1. Основные понятия // Сравнения. — М.: «Знание», 1975. — С. 3—9. — 64 с. Архивировано 24 августа 2015 года.
7. Виноградов И. М. Основы теории чисел. — М.—Л.: Гос. изд. технико-теоретической литературы, 1952. — С. 41—45. — 180 с. Архивировано 1 июля 2020 года.
8. Сизый, 2008, с. 88.
9. Сагалович, 2010, с. 25—29.
10. Нестеренко, 2008, с. 86—87.
11. Бухштаб А. А. Глава 8. Классы // Теория чисел. — М.: «Просвещение», 1966. — С. 77—78. — 384 с. Архивировано 20 ноября 2015 года.
12. Сагалович, 2010, с. 29—32.
13. Сизый, 2008, с. 87—88,91.
14. Лидл Р., Нидеррайтер Г. Конечные поля. В 2-х тт. — М.: Мир, 1998. — С. 27 (Пример 1.37). — 430 с. — ISBN 5-03-000065-8.
15. Фадеев Д. К. Глава VII. Сравнение в кольце полиномов и расширения полей // Лекции по алгебре. — М.: «Наука», 1984. — С. 197—198. — 416 с.
16. Сизый, 2008, с. 105—109.
17. Бухштаб А. А. Глава 21. Сравнения 2-й степени по простому модулю, Глава 22. Сравнения второй степени по составному модулю // Теория чисел. — М.: «Просвещение», 1966. — С. 172—201. — 384 с. Архивировано 20 ноября 2015 года.
18. Harald Niederreiter, Arne Winterhof. Applied Number Theory. — «Springer», 2015. — С. 369. — 442 с. — ISBN 978-3-319-22321-6.
19. Коблиц Н. Курс теории чисел и криптографии / пер. с англ. М. А. Михайловой и В. Е. Тараканова под ред. А. М. Зубкова. — М.: Научное изд-во ТВП, 2001. — С. 96, 105—109, 200—209. — 262 с. — ISBN 5-85484-012-X.
20. Check Digit Verification of CAS Registry Numbers (англ.). Архивировано 8 декабря 2015 года.

Литература

• Бухштаб А. А. Теория чисел. — М.: «Просвещение», 1966. — 384 с.
• Вейль А. Основы теории чисел. — М.: Мир, 1972.
• Виленкин Н. Я. Сравнения и классы вычетов // Квант. — 1978. — № 10. — С. 4—8.
• Виноградов И. М. Основы теории чисел. — М.—Л.: Гос. изд. технико-теоретической литературы, 1952. — 180 с.
• Коблиц Н. Курс теории чисел и криптографии / пер. с англ. М. А. Михайловой и В. Е. Тараканова,под ред. А. М. Зубкова. — М.: Научное изд-во ТВП, 2001. — 254 с. — ISBN 5-85484-012-X.
• Материалы международной научной конференции “Модулярная арифметика”  (неопр.). Виртуальный компьютерный музей (2005). Дата обращения: 31 июля 2010.
• Нестеренко Ю. В. Теория чисел. — М.: Издательский центр «Академия», 2008. — С. 132—133. — 272 с. — ISBN 9785769546464.
• Сагалович Ю. Л. Введение в алгебраические коды — 2-е изд. — М.: ИППИ РАН, 2010. — 320 с. — ISBN 978-5-901158-14-2
• Сизый С. В. §4. Теория сравнений // Лекции по теории чисел. — М.: Физматлит, 2008. — 192 с. — ISBN 978-5-9221-0741-9.