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

Сравнение двух целых чисел по модулю натуральногочисла m — математическая операция, позволяющая ответить на вопрос отом, дают ли два выбранных целых числа при делении на m один и тот жеостаток. Любое целое число может иметь не больше, чем m остатков; этозначит, что все целые числа можно разделить на m групп относительноm, каждая из которых отвечает определённому остатку от деления на m.
Модульная арифметика, часто называемая модулярнойарифметикой, широко применяется в математике, информатике икриптографии.

История


 Предпосылкой к созданию теории сравнений стало восстановление сочиненийДиофанта, которые были выпущены в подлиннике и с латинским переводом,благодаря Баше де Мезириаку, в 1621 году. Их изучение привело Ферма коткрытиям, которые по значению существенно опередили своё время.Например, в письме к 18 октября 1640 года он сообщил без доказательстватеорему, впоследствии получившую название малой теоремы Ферма. Всовременной формулировке теорема утверждает, что если p — простоечисло и a — целое число, не делящееся на p, то
ap11(modp) .
 Первое доказательство этой теоремы принадлежит Лейбницу, причём оноткрыл указанную теорему независимо от Ферма не позднее 1683 года исообщил об этом с приведением точного доказательства Бернулли. Кромеэтого Лейбницем был предложен прообраз формулировки теоремы Вильсона.
 Позже изучение вопросов, посвященных теории чисел и теории сравнений,было продолжено Эйлером, который ввел квадратичный закон взаимности иобобщил теорему Ферма, установив, что
aφ(n)1(modn),
 где φ(n) — функция Эйлера.
 Понятие и символьное обозначение сравнений было введено Гауссом,как важный инструмент для обоснования его арифметической теории, работанад которой была начата им в 1797 году. В начале этого периода Гауссуещё не были известны труды его предшественников, поэтому результаты егоработы, изложенные в первых трёх главах его книги «Арифметическиеисследования» (1801 год), были в основном уже известны, однако методы,которые он использовал для доказательств, оказались абсолютно новыми,имеющими высшую важность для развития теории чисел. Используя эти методыГаусс преобразовал все накопленные до него сведения, связанные соперациями сравнения по модулю, в стройную теорию, которая впервые былаизложена в этой же книге. Кроме этого, он исследовал сравнения первой ивторой степени, теорию квадратичных вычетов и связанный с нейквадратичный закон взаимности.

Определения


 Если два целых числа a и b при делении на m дают одинаковыеостатки, то они называются сравнимыми (илиравноостаточными) по модулю числа m. Сравнимостьчисел a и b записывается в виде формулы (сравнения):
ab(modm).
 Число m называется модулем сравнения.
 Определение сравнимости чисел a и b по модулю mравносильно любому из следующих утверждений:

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

 Например, числа 32 и -10 сравнимы по модулю 7, так как оба числа приделении на 7 дают остаток 4:
32=74+4; 10=7(2)+4.
 Также числа 32 и -10 сравнимы по модулю 7, так как их разность32(10)=42 делится на 7 и к тому же имеет место представление
32=67+(10).

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


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

  • свойством рефлексивности: для любого целого a справедливо aa(modm);
  • свойством симметричности: если ab(modm), то ba(modm);
  • свойством транзитивности: если ab(modm) и bc(modm), то ac(modm).

 Таким образом, отношение сравнимости по модулю m является отношениемэквивалентности на множестве целых чисел.
 Кроме вышеперечисленных свойств, для сравнений справедливы следующиеутверждения:

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


  • если числа a и b сравнимы по k модулям m1,m2,...,mk, то они сравнимы по модулю, равному наименьшему общему кратному модулей m1,m2,...,mk.

Следствие:
 Для того, чтобы числа a и b были сравнимы по модулю m,каноническое разложение на простые сомножители которого имеет вид
m=i=1dpiαi,
 необходимо и достаточно, чтобы
ab(modpiαi), где i=1,2,,d.

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


 Сравнения по одному и тому же модулю обладают многими свойствами обычныхравенств. Например, их можно складывать, вычитать и перемножать: есличисла a1,a2,,an и b1,b2,,bn попарно сравнимыпо модулю m, то их суммы a1+a2++an иb1+b2++bn, а также произведенияa1a2...an иb1b2...bn тоже сравнимы по модулю m:
(a1+a2++an)(b1+b2++bn)(modm);
(a1a2an)(b1b2bn)(modm).
 При этом нельзя выполнять эти операции со сравнениями, если их модули несовпадают.
 К обеим частям сравнения можно прибавить одно и то же число c:
(a+c)(b+c)(modm).
 Также можно перенести число из одной части сравнения в другую со сменойзнака:
a(b+c)(modm);
(ac)b(modm).
 Если числа a и b сравнимы по модулю m, то их степени ak и bkтоже сравнимы по модулю m при любом натуральном k:
akbk(modm).
 K любой из частей сравнения можно прибавить целое число, кратное модуля,то есть, если числа a и b сравнимы по модулю некоторого числа m,то и a+t1 сравнимо с b+t2 по модулю m, где t1 и t2 —произвольные целые числа, кратные m:
(a+t1)(b+t2)(modm).
 Также обе части сравнения и модуль можно умножить на одно и то же число,то есть, если числа a и b сравнимы по модулю некоторого целого числаm, то и числа aq и bq сравнимы по модулю числа mq, где q —целое:
aqbq(modmq).
 Сравнения, однако, нельзя, вообще говоря, делить друг на друга или надругие числа. Пример: 1420(mod6), однако, сократив на 2, мыполучаем ошибочное сравнение: 710(mod6). Правила сокращениядля сравнений следующие.

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

adbd(modm) и НОД(d,m)=1, то
ab(modm).
 Если, число d не взаимно просто с модулем, как было в примере,указанном выше, то сокращать на d нельзя.

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

 если acbc(modmc), то ab(modm).

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


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


 Множество всех чисел, сравнимых с a по модулю m, называетсяклассом вычетов a по модулю m, и обычно обозначается[a]m или a¯m. Таким образом, сравнение ab(modm)равносильно равенству классов вычетов [a]m=[b]m.
 Любое число класса называется вычетом по модулю m. Пусть дляопределённости r ? остаток от деления любого из представителейвыбранного класса на m, тогда любое число q из этого класса можнопредставить в виде q=mt+r, где t — целое. Вычет, равныйостатку r (q=r при t=0) называется наименьшимнеотрицательным вычетом, а вычет ρ (q=ρ), самый малый поабсолютной величине, называется абсолютно наименьшим вычетом. Приr<m2 получаем, что ρ=r, в противном случаеρ=rm. Если m — чётное и r=m2, тоρ=m2.
 Поскольку сравнимость по модулю m является отношением эквивалентностина множестве целых чисел Z, то классы вычетов по модулю mпредставляют собой классы эквивалентности; их количество равно m.
 Множество всех классов вычетов по модулю m обозначается Zmили Z/mZ или Z/(m).
 Операции сложения и умножения на Z индуцируют соответствующиеоперации на множестве Zm:
[a]m+[b]m=[a+b]m;
[a]m[b]m=[ab]m.
 Относительно этих операций множество Zm является конечнымкольцом, а для простого m — конечным полем.

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


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

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

0,1,,m1

  • или абсолютно наименьшие вычеты, состоящие из чисел

0,±1,±2,,±m12,
 Максимальный набор попарно несравнимых по модулю m чисел, взаимнопростых с m, называется приведённой системой вычетов помодулю m. Всякая приведённая система вычетов по модулю m содержитφ(m) элементов, где φ() — функция Эйлера.
 Например, для числа m=42 полная система вычетов может бытьпредставлена числами 0,1,2,3,,21,22,23,,39,40,41, а приведённая — 1,5,11,13,17,19,23,25,29,31,37,41.

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


 Рассматривается кольцо многочленов K[x] над полем K. Два многочленаg1 и g2, принадлежащие выбранному кольцу, называютсясравнимыми по модулю многочлена f, если их разность g1g2делится на f без остатка. Сравнение обозначается следующим образом:
g1g2(modf).
 Так же, как и в кольце целых чисел, такие сравнения можно складывать,вычитать и перемножать.

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


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


 В теории чисел, криптографии и других областях науки часто возникаетзадача поиска решений сравнения первой степени вида
axb(modm).
 Решение такого сравнения начинается с вычисления d=НОД(a,m). При этом возможны два случая:

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

a1xb1(modm1),
 Практическое вычисление значения c можно осуществить разнымиспособами: с помощью теоремы Эйлера, алгоритма Евклида, теории цепныхдробей (см. алгоритм) и др. В частности, теорема Эйлера позволяетзаписать значение c в виде:
ca11a1φ(m1)1(modm1).

Примеры


Пример 1. Для сравнения
6x26(mod22)
 имеем d=2, поэтому по модулю 22 сравнение имеет два решения. Заменим26 на 4, сравнимое с ним по модулю 22, и затем сократим все три числа на2:
3x2(mod11)
 Поскольку 3 взаимно просто с модулем 11, то его можно обратить по модулю11 и найти
314(mod11).
 Умножая сравнение на 4, получаем решение по модулю 11:
x8(mod11),
 эквивалентное совокупности двух решений по модулю 22:
x8(mod22) и x19(mod22).
Пример 2. Дано сравнение:
100x41(mod65537). Отметим, что модуль 65537 — простоечисло.
 Первый способ решения — воспользоваться соотношением Безу. С помощьюалгоритма Евклида или программы, приведенной в статье о соотношенииБезу, находим, что это соотношение для чисел 100 и 65537 имеет вид:
17695100+(27)65537=1, или176951001(mod65537)
 Умножив обе части этого сравнения на 41, получим:
10072549541(mod65537)
 Отсюда следует, что 725495 есть решение исходного сравнения. Удобнеезаменить его на сравнимое с ним 4588 (остаток от деления 725495 на65537). Ответ: x4588(mod65537).
 Второй способ решения, более простой и быстрый, не требует построениясоотношения Безу, но также эквивалентен алгоритму Евклида.
 Шаг 1. Делим модуль на коэффициент при x с остатком:65537=100655+37. Умножим обе части исходного сравнения начастное 655 и прибавим 37x; получим:65537x26855+37x(mod65537), но левая часть кратна 65537,то есть сравнима с нулём, откуда:
37x26855(mod65537)
 Мы получили при x коэффициент 37 вместо 100. На каждом следующем шагеуменьшаем аналогично, пока не получим единицу.
 Шаг 2. Аналогично делим на новый коэффициент при x:65537=371771+10. Умножим обе части сравнения, полученного впредыдущем шаге, на частное 1771 и прибавим 10x; снова заменив левуючасть на ноль, получим:
10x47560205(mod65537)
47560205 заменяем на его остаток при делении на 65537, равный45880:
10x45880(mod65537)
 Далее можно было бы сделать аналогично ещё 5 шагов, но проще разделитьобе части сравнения на 10 и сразу получить результат:x4588(mod65537).

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


 Сравнения второй степени по простому модулю имеет следующий общий вид:
c0x2+c1x+c0(modm).
 Это выражение можно привести к виду:
(x+b)2a(modm).,
 а при замене z=x+b упрощается максимально:
(z)2a(modm)..
 Решение этого сравнения сводится к выяснению, является ли данное числоквадратичным вычетом (с помощью квадратичного закона взаимности) ипоследующему вычислению квадратного корня по данному модулю. Длявычисления квадратного корня из квадратичного вычета существуетвероятностный метод Берлекэмпа.

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


 Китайская теорема об остатках утверждает, что система сравнений спопарно взаимно простыми модулями m1,m2,,mn:
{xa1(modm1),xa2(modm2),xan(modmn)

 x \{equiv a\_n \{pmod \{m\_n\}\{end\{cases\} всегда разрешима, и её решение единственнопо модулю m1m2mn.
 Другими словами, китайская теорема об остатках утверждает, что кольцовычетов по модулю произведения нескольких попарно взаимно простых чиселявляется прямым произведением соответствующих множителям колец вычетов.

Применение


 Методы теории сравнений используются в теории чисел, теории групп,теории колец, теории узлов, общей алгебре, криптографии, информатике,химии и других областях.
 Например, сравнения часто применяются для вычисления контрольных сумм,используемых в идентификаторах. Так, для определения ошибок при вводемеждународного номера банковского счета используется сравнение по модулю97.
 В криптографии сравнения можно встретить в системах с открытым ключом,использующих, например, алгоритм RSA или протокол Диффи — Хеллмана.Также, модульная арифметика обеспечивает конечные поля, над которымизатем строятся эллиптические кривые, и используется в различныхпротоколах с симметричным ключом (AES, IDEA).
 В химии последняя цифра в регистрационном номере CAS является значениемконтрольной суммы, которая вычисляется путём сложения последней цифрыномера, умноженной на 1, второй справа цифры, умноженной на 2, третьей,умноженной на три и так далее до первой слева цифры, завершаясьвычислением остатка от деления на 10