Как найти сравнение по модулю - Сайт, где вы сможете решить свои вопросы

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

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

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

Предпосылкой к созданию теории сравнений стало восстановление сочинений Диофанта, которые были выпущены в подлиннике и с латинским переводом, благодаря Баше де Мезириаку, в 1621 году. Их изучение привело Ферма́ к открытиям, которые по значению существенно опередили своё время. Например, в письме к Френиклю де Бесси^ru_fr^[4] 18 октября 1640 года он сообщил без доказательства теорему, впоследствии получившую название малой теоремы Ферма. В современной формулировке теорема утверждает, что если — простое число и — целое число, не делящееся на , то

$a^{p-1}equiv 1{pmod {p}}$

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

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

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

где — функция Эйлера.

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

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

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

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

Определение сравнимости чисел и по модулю равносильно любому из следующих утверждений:

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

Также числа 32 и -10 сравнимы по модулю 7, так как их разность делится на 7 и к тому же имеет место представление

Свойства сравнимости по модулю[править | править код]

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

Таким образом, отношение сравнимости по модулю является отношением эквивалентности на множестве целых чисел^[8].

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

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

Пусть

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

где

— некое целое число.

Так как является делителем числа , то

где

— некое целое число.

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

где

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

Следствие:

Для того, чтобы числа

были сравнимы по модулю

, каноническое разложение на простые сомножители которого имеет вид

$m = prod_{i=1}^d p_i^{alpha_i},$

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

${displaystyle aequiv b{pmod {p_{i}^{alpha _{i}}}},}$

где

^[9].

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

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

${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}}.}$

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

К обеим частям сравнения можно прибавить одно и то же число :

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

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

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

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

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

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

Также обе части сравнения и модуль можно умножить на одно и то же число, то есть, если числа и сравнимы по модулю некоторого целого числа , то и числа и сравнимы по модулю числа , где — целое:

Сравнения, однако, нельзя, вообще говоря, делить друг на друга или на другие числа. Пример: , однако, сократив в 2 раза, мы получаем ошибочное сравнение: . Правила сокращения для сравнений следующие.

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

и НОД

то

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

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

если , то ^[9].

Пример[править | править код]

Применение сравнений позволяет легко получать разнообразные признаки делимости. Например, выведем признак делимости натурального числа N на 7. Запишем в виде (то есть отделим цифру единиц). Условие, что делится нацело на 7, можно записать в виде: Умножим это сравнение на

{displaystyle -20a-2bequiv 0{pmod {7}}.}

Или, прибавив слева число кратное модулю:

Отсюда вытекает следующий признак делимости на 7: надо вычесть из числа десятков удвоенное число единиц, затем повторять эту операцию до тех пор, пока не получится двузначное или однозначное число; если оно делится на 7, то и исходное число делится. Например, пусть Алгоритм проверки^[10]:

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

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

Связанные определения[править | править код]

Классы вычетов[править | править код]

Множество всех чисел, сравнимых с по модулю , называется классом вычетов по модулю , и обычно обозначается [a]_m или bar a_m . Таким образом, сравнение равносильно равенству классов вычетов ^[11].

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

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

Множество всех классов вычетов по модулю обозначается $mathbb {Z} _{m}$ или ^[13] или ^[14].

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

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

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

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

Системы вычетов[править | править код]

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

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

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

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

и в случае чётного

из чисел

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

Максимальный набор попарно несравнимых по модулю чисел, взаимно простых с , называется приведённой системой вычетов по модулю . Всякая приведённая система вычетов по модулю содержит элементов, где — функция Эйлера^[12].

Например, для числа 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] над полем . Два многочлена $g_{1}$ и
$g_{2}$ , принадлежащие выбранному кольцу, называются сравнимыми по модулю многочлена , если их разность g_1-g_2 делится на без остатка. Сравнение обозначается следующим образом:

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

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

Решение сравнений[править | править код]

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

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

{displaystyle acdot xequiv b{pmod {m}}.}

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

${displaystyle a_{1}xequiv b_{1}{pmod {m_{1}}},}$

где ${displaystyle a_{1}={frac {a}{d}},}$

$b_1 = frac{b}{d}$

и $m_1 = frac{m}{d}$

являются целыми числами, причём $a_{1}$

взаимно просты. Поэтому число $a_{1}$

можно обратить по модулю m_1

, то есть найти такое число

, что ${displaystyle ccdot a_{1}equiv 1{pmod {m_{1}}}}$

(другими словами, ${displaystyle cequiv a_{1}^{-1}{pmod {m_{1}}}}$

). Теперь решение находится умножением полученного сравнения на

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

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

${displaystyle cequiv a_{1}^{-1}equiv a_{1}^{varphi (m_{1})-1}{pmod {m_{1}}}}$

^[16].

Примеры[править | править код]

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

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

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

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

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

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

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

Отметим, что модуль 65537

— простое число.

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

{displaystyle 17695cdot 100+(-27)cdot 65537=1,}

или

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

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

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

Шаг 1. Делим модуль на коэффициент при x с остатком: . Умножим обе части исходного сравнения на частное 655 и прибавим 37x ; получим: , но левая часть кратна 65537 , то есть сравнима с нулём, откуда:

{displaystyle 37xequiv -26855{pmod {65537}}}

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

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

заменяем на его остаток при делении на 65537, равный 45880 :

Далее можно было бы сделать аналогично ещё 5 шагов, но проще разделить обе части сравнения на 10 и сразу получить результат:

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

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

$c_0x^2+c_1x+c equiv 0pmod {m}.$

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

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

а при замене упрощается до

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

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

Системы сравнений[править | править код]

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

${begin{cases}xequiv a_{1}{pmod {m_{1}}}\xequiv a_{2}{pmod {m_{2}}}\ldots \xequiv a_{n}{pmod {m_{n}}}end{cases}}$

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

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

Применение[править | править код]

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

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

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

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

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

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

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

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

Источник

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

Определение 1. Если два числа¹) a и b при делении на p дают один и тот же остаток r, то такие числа называются равноостаточными или сравнимыми по модулю p.

Утверждение 1. Пусть p какое нибудь положительное число. Тогда всякое число a всегда и притом единственным способом может быть представлено в виде

где s – число, и r одно из чисел 0,1, …, p−1.

¹) В данной статье под словом число будем понимать целое число.

Действительно. Если s получит значение от −∞ до +∞, то числа sp представляют собой совокупность всех чисел, кратных p. Рассмотрим числа между sp и (s+1)p=sp+p. Так как p целое положительное число, то между sp и sp+p находятся числа

Но эти числа можно получить задав r равным 0, 1, 2,…, p−1. Следовательно sp+r=a получит всевозможные целые значения.

Покажем, что это представление единственно. Предположим, что p можно представить двумя способами a=sp+r и a=s₁p+r₁. Тогда

или

(2)

Так как r₁ принимает один из чисел 0,1, …, p−1, то абсолютное значение r₁−r меньше p. Но из (2) следует, что r₁−r кратно p. Следовательно r₁=r и s₁=s.

Число r называется вычетом числа a по модулю p (другими словами, число r называется остатком от деления числа a на p).

Утверждение 2. Если два числа a и b сравнимы по модулю p, то a−b делится на p.

Действительно. Если два числа a и b сравнимы по модулю p, то они при делении на p имеют один и тот же остаток p. Тогда

где s и s₁ некоторые целые числа.

Разность этих чисел

(3)

делится на p, т.к. правая часть уравнения (3) делится на p.

Утверждение 3. Если разность двух чисел делится на p, то эти числа сравнимы по модулю p.

Доказательство. Обозначим через r и r₁ остатки от деления a и b на p. Тогда

откуда

По утверждению a−b делится на p. Следовательно r−r₁ тоже делится на p. Но т.к. r и r₁ числа 0,1,…, p−1, то абсолютное значение |r−r₁|<p. Тогда, для того, чтобы r−r₁ делился на p должно выполнятся условие r=r₁.

Из утверждения следует, что сравнимые числа – это такие числа, разность которых делится на модуль.

Если нужно записать, что числа a и b сравнимы между собой по модулю p, то пользуются обозначением (введенным Гауссом):

Примеры 25≡39 (mod 7), −18≡14 (mod 4).

Из первого примера следует, что 25 при делении на 7 дает тот же остаток, что и 39. Действительно 25=3·7+4 (остаток 4). 39=3·7+4 (остаток 4). При рассмотрении второго примера нужно учитывать, что остаток должен быть неотрицательным числом, меньшим, чем модуль (т.е. 4). Тогда можно записать: −18=−5·4+2 (остаток 2), 14=3·4+2 (остаток 2). Следовательно −18 при делении на 4 дает остаток 2, и 14 при делении на 4 дает остаток 2.

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

Свойство 1. Для любого a и p всегда

Свойство 2. Если два числа a и c сравнимы с числом b по модулю p , то a и c сравнимы между собой по тому же модулю, т.е. если

a≡b mod (p), b≡c mod (p).

то

Действительно. Из условия свойства 2 следует a−b и b−c делятся на p. Тогда их сумма a−b+(b−c)=a−c также делится на p.

Свойство 3. Если

a≡b mod (p) и m≡n mod (p),

то

a+m≡b+n mod (p) и a−m≡b−n mod (p).

Действительно. Так как a−b и m−n делятся на p, то

(a−b)+ (m−n)=(a+m)−(b+n) ,

также делятся на p.

Это свойство можно распространить на какое угодно число сравнений, имеющих один и тот же модуль.

Свойство 4. Если

a≡b mod (p) и m≡n mod (p),

то

Действительно.Так как a−b делится на p, то (a−b)m также делится на p, следовательно

Далее m−n делится на p, следовательно b(m−n)=bm−bn также делится на p, значит

Таким образом два числа am и bn сравнимы по модулю с одним и тем же числом bm, следовательно они сравнимы между собой (свойство 2).

Свойство 5. Если

то

где k некоторое неотрицательное целое число.

Действительно. Имеем a≡b mod (p). Из свойства 4 следует

Все свойства 1-5 представить в следующем утверждении:

Утверждение 4. Пусть f(x₁, x₂, x₃, …) целая рациональная функция с целыми коэффициентами и пусть

a₁≡b₁, a₂≡b₂, a₃≡b₃, … mod (p).

тогда

f(a₁, a₂, a₃, …)≡f(b₁, b₂, b₃, …) mod (p).

При делении все обстоит иначе. Из сравнения

не всегда следует сравнение

Утверждение 5. Пусть

тогда

где λ это наибольший общий делитель чисел m и p.

Доказательство. Пусть λ наибольший общий делитель чисел m и p. Тогда

Так как m(a−b) делится на k, то

имеет нулевой остаток. Тогда

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

имеет нулевой остаток, т.е. m₁(a−b) делится на k₁. Но числа m₁ и k₁ числа взаимно простые. Следовательно a−b делится на k₁=k/λ и, тогда, a≡b mod (p/λ).

Утверждение 6. Если

и m является один из делителей числа p, то

Действительно. a−b делится на p. p делится на m. Следовательно a−b делится на m.

Утверждение 7. Если

a≡b mod (p), a≡b mod (q), a≡b mod (s)

то

где h наименьшее общее кратное чисел p,q,s.

Действительно. Разность a≡b должна быть числом, кратным p,q,s. и, следовательно должна быть кратным h.

В частном случае, если модули p,q,s взаимно простые числа, то

где h=pqs.

Заметим, что можно допустить сравнения по отрицательным модулям, т.е. сравнение a≡b mod (p) означает и в этом случае, что разность a−b делится на p. Все свойства сравнений остаются в силе и для отрицательных модулей.

Источник

Решение сравнений по модулю

Решений нет

Файл очень большой, при загрузке и создании может наблюдаться торможение браузера.

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

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

Сравнимость чисел a и b по модулю сравнения m записывается как

Выражение

называется сравнением первой степени или линейным сравнением по модулю m.

Для проверки существования решений сравнения сначала вычисляется НОД(a, m). Если b не кратно полученному НОД, то у сравнения нет решений.
Если кратно, то количество решений по модулю m равно полученному НОД.

Существует несколько алгоритмов нахождения всех решений сравнения, но в данном калькуляторе применяется алгоритм решения линейных диофантовых уравнений с двумя переменными. В самом деле, сравнение эквивалентно следующему линейному диофантовому уравнению:

поэтому я использовал уже реализованный калькулятор решения линейных диофантовых уравнений для получения общей формулы решения, после чего выбрал все частные решения в диапазоне от 0 до m.

Источник

1.2 Теория сравнений и ее приложения

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

Определение 1.11 Числа, дающие при делении на m одинаковые остатки, называются сравнимыми по модулю . Обозначение: .

Теорема 1.14 (признак сравнимости по модулю) Два целых числа сравнимы по модулю тогда и только тогда, когда их разность делится на .

Итак, если два целых числа и сравнимы по модулю , то этот факт можно записать разными способами: или a=b+mk , где – целое число, или a-b=mk или .

Далее, если a=mq+r , то есть при делении на дает остаток , то a-r=mq или . Таким образом, любое целое число всегда сравнимо с остатком , получающимся при делении его на .

Свойства сравнений, не зависящие от модуля

Отношение сравнимости удовлетворяет условиям:

Отношение, заданное на множестве и обладающее перечисленными свойствами, задает разбиение этого множества на непересекающиеся классы. Применительно к отношению сравнимости по модулю это означает: все множество целых чисел разбивается на классы чисел, эти классы не пересекаются. Так, есть класс нуля: это все числа, сравнимые с нулем по модулю ,то есть делящиеся на без остатка(включая и само число 0), класс единицы – все числа, дающие остаток 1 при делении на , класс 2, …,класс m-1 . Например, пусть m=5 . Получаем следующие классы:

$begin{array}{lcl} bar{0}&=&{dots,-10, -5, 0, 5, 10, 15, 20,dots} \[1ex] bar{1}&=&{dots,-9, -4, 1, 6, 11, 16, 21,{dots}} \[1ex] bar{2}&=&{dots,-8, -3, 2, 7, 12, 17, 22,{dots}} \[1ex] bar{3}&=&{{dots},-7, -2, 3, 8, 13, 18, 23,{dots}} \[1ex] bar{4}&=&{{dots},-6, -1, 4, 9, 14, 19, 24,{dots}}. end{array}$

(
1.2)

Определение 1.12 Классы (1.2) называются классами вычетов.

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

Следствие 1.6 Члены сравнения можно переносить из одной части сравнения в другую с противоположным знаком.
Сравнения по одному и тому же модулю можно почленно перемножать.

Следствие 1.7 Обе части сравнения можно возводить в одну и ту же целую неотрицательную степень: если и – целое неотрицательное число, то .
Обе части сравнения можно умножать на одно и то же целое число.

Свойства сравнений, зависящие от модуля

Если и , то .
Обе части сравнения и модуль можно умножить на одно и то же целое положительное число.
Если и , то $a equiv b mod {frac{m}{d}}$ .

Приведем следствия из свойства 9.

Следствие 1.8 Если , т. е. если , то из следует $a equiv b mod frac{m}{k}$ , а это означает, что обе части сравнения и модуль можно разделить на любой их общий делитель.

Большое значение имеет

Следствие 1.9 Если , т. е. если , то из следует , а это означает, что обе части сравнения можно разделить на их общий делитель, если он взаимно прост с модулем.

Пример 1.9 .

После деления обеих частей сравнения на получим .

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

Пример 1.10 , но .
Если сравнение имеет место по нескольким разным модулям, то оно имеет место и по модулю, равному наименьшему общему кратному этих модулей.
Из рассмотренных свойств сравнений вытекает следующее общее свойство.
Пусть – многочлен с целыми коэффициентами, и – переменные, принимающие целые значения. Тогда если , то .

Если и , то

$c_na^n+c_{n-1}a^{n-1}+ldots+c_1a + c_0 = d_nb^n + d_{n-1}b^{n-1}+ldots+d_1b + d_0 ~(mod m).$

Таким образом, в сравнении по модулю отдельные слагаемые и множители можно заменять числами, сравнимыми по тому же модулю . В частности, все числа, кратные модулю, можно заменять нулями (так как если , то ).

Вместе с тем следует обратить внимание на то, что встречающиеся в сравнениях показатели степеней заменять таким образом нельзя: из $a^{n} equiv c~(mod m)$ и не следует, что $a^{k} equiv c~(mod m)$ .

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

Пример 1.11 Доказать, что при любом натуральном число $37^{n+2} + 16^{n+1} +23^{n }$ делится на .

Решение. Очевидно, что , , .

Возведем первое сравнение в степень , второе – в степень , третье – в степень . Полученные сравнения: $37^{n+2} equiv 2^{n+2}~(mod 7)$ , $16^{n+1} equiv 2^{n+1}~(mod 7)$ , $23^{n} equiv 2^{n}~(mod 7)$ , сложим:

$37^{n+2} +16^{n+1} +23^{n } equiv 2^{n} cdot (2^{2}+2^{1}+1) ~(mod 7) equiv 2^{n}cdot 7~(mod 7)$ , то есть $37^{n+2} +16^{n+1} +23^{n}$ делится на .

Пример 1.12 Найти остаток от деления числа $(9674^{6} +28)^{15}$ на .

Решение. Так как , то $9674^{6} equiv 2^{6}~(mod 39)=64 equiv 25~(mod 39)$ . Далее, . Следовательно, $(9674^{6} +28)^{15}equiv 14^{15}$ . И задача теперь сведена к следующей: найти остаток от деления $14^{15}$ на . Воспользуемся сравнениями: и . Из следует: $14^{14}equiv 1~(mod 3)$ . А из сравнения следует: $14^{14}equiv 1~(mod 13)$ . И так как сравнение имеет место по модулям и , то оно имеет место и по модулю , являющемуся НОК чисел и . Итак, $14^{14}equiv 1~(mod 39)$ . Но в таком случае $14^{15}equiv 14~(mod 39)$ .

1.2.2 Возведение в степень по модулю

Пусть , нам необходимо вычислить . В дальнейшем перед нами часто будет стоять такая задача с очень большими числами , , . Очевиднейший способ вычислить – вычислить произведение $underbrace{acdot acdots a}_{n text{раз}}$ и взять остаток от деления на . Для этого потребуется умножений и взятие остатка от деления огромного числа (не всегда даже его хранение в памяти может быть простым) по модулю . Приведём оптимизации для этой задачи.

Из свойства

следует, что промежуточные результаты вычислений можно перед хранением брать по модулю .
Сгруппируем сомножители в произведении особым образом. Пусть , $b_iin{0,1}$ . Имеем:

$a^b ~(mod m) = a^{b_0} cdot (a^2)^{b_1} cdot (a^4)^{b_2} cdots left(a^{(2^n)}right)^{b_n} ~(mod m).$

Используя пункт 1, будем все промежуточные результаты хранить по модулю . Также для деления на 2 мы будем использовать операцию сдвига бит вправо:

$2^n b_n + 2^{n-1} b_{n-1} + ldots + 2 cdot b_1 + b_0 ~~rightarrow~~ 2^{n-1} b_{n} + ldots + 2 cdot b_2 + b_1.$

Микропроцессоры имеют специальные инструкции, а языки программирования – специальные операторы для оптимизированного выполнения битового сдвига, которые и следует использовать при реализации данного алгоритма.

Пункт 2 даёт следующий алгоритм возведения в степень по модулю.

Вход: , , – целые неотрицательные числа.

Выход: – результат возведения в степень по модулю .

Также отметим, что на шаге 1 копирование b'=b , x=a выполняются для того, чтобы не испортить значения , , которые могут передаваться в наш алгоритм по указателю или ссылке.

Источник

§5
Числовые
сравнения

п.1 Определение и основные свойства
сравнений

Пусть

— произвольное натуральное число. Будем
называть его модулем.

Определение: Целые числа a
и b сравнимы по
модулю m, если их
разность a–b
делятся на m.

Обозначение: a ≡
b (mod
m).

Пример:

17 ≡ 5 (mod
17), 19 ≡ -1 (mod 10)

15 ≡ 0 (mod 5), 11≡ 1
(mod 5)

Замечание: Сравнение 17 ≡
5 (mod 12)
иллюстрирует хорошо знакомую ситуацию.
По модулю 12 мы обычно называем время,
говоря “сейчас 5 часов”, вместо
“сейчас 17 часов”.

Теорема 1: Следующее утверждения
для целых чисел a и
b равносильны:

разность a–b
делится на m.
,
где
.
a и b
имеют одинаковые остатки при делении
на m.

Доказательство: 1)2)
Пусть a–b
делятся на m. Тогда
a–b=mt

или
.

2)3)
Пусть
,
и пусть b при делении
на m имеет остаток r,
т.е.
.
Тогда
,
где 0 ≤ r < m.

Следовательно r
— остаток от деления a
на m. Значит, a
и b имеют равные
остатки от деления на m.

3)1)
Пусть

Тогда

делится на m.

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

Перейдем к изучению свойств сравнений.
Отношение сравнимости двух целых чисел
является примером бинарного отношения
на множестве Z. Во
многом это отношение похоже на отношение
равенства. Свойства 1°—4° иллюстрируют
это сходство.

1°. Отношение сравнения является
отношением эквивалентности:

a ≡ a
(mod m)
a ≡ b (mod m)

b ≡ a (mod m)
a ≡ b (mod m), b ≡ c (mod m)
a ≡ c (mod m)

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

1. Рефлексивно очевидна, т.к. a–a
делиться на m.

2. Симметричность не менее ясна: если
a–b
делиться на m, то

b– a
тоже делится на m.

3. Транзитивность следует из равенства
и
свойств делимости.

■

2°. Сравнения по одному и тому же модулю
можно складывать, вычитать и умножать:

если a ≡ b
(mod m),
c ≡ d
(mod m),
то

a + c
=b + d
(mod m)

a – c
=b – d
(mod m)

a · c
=b · d
(mod m)

Доказательство: Пусть
,
,
где

и

— целые. Тогда

что по теореме 1 равносильно требуемым
сравнениям.

■

Пример:

3°. Обе части сравнения можно увеличить
на одно и тоже число, домножать на
одинаковый множитель или возвести в
одинаковую степень:

если a ≡ b
(mod m),
то

a + k ≡ b + k (mod m), kZ,

a · k ≡b · k (mod m), kZ,

(mod m),
kN.

Доказательство: Требуемые утверждения
легко получить, применяя свойство 2° к
сравнениям a ≡ b
(mod m)
и

k ≡ k
(mod m).

■

Пример: 9 ≡ 4 (mod
5). Для k = 2 получим
верные сравнения:

11 ≡ 6 (mod 5),
18 ≡ 8 (mod 5),
81 ≡ 16 (mod 5).

4°. Члены сравнения можно переносить из
одной части в другую с переменой знака:

a + b ≡ с
(mod m)

a ≡ c-b
(mod m)

Доказательство: Следует из свойства
3° при k = –b.

■

Следующие два свойства показывают
отличие числовых сравнений от обычных
равенств.

5°. В любой части сравнения можно добавить
или отбросить слагаемое, кратное модулю:

a ≡ b (mod m)
a
+ m · k ≡ b (mod m)

Доказательство: По определению
сравнимости:

m · k
≡ 0 (mod m).
Складывая это сравнение с данным
сравнением

a ≡ b
(mod m)
получим требуемое. Для доказательства
обратного утверждения используем
операцию вычитания.

■

Пример: Свойство 5° используют при
подсчете дней недели:

3 ≡ b (mod
7)
24
≡ b (mod
7).

Если 3 числа были вторник, то 24 числа
тоже будет вторник.

6°. Обе части сравнения можно сократить
на их общий множитель, если он взаимно
прост с m:

если a · k
≡ b · k
(mod m)
и при этом НОД(k,m)
= 1,

то a ≡ b
(mod m).

Доказательство: Пусть a
· k – b
· k делится на
m. По условию

k и m
взаимно простые

a–b
делиться на m

a ≡ b
(mod m).

■

Замечание: Условие взаимной
простоты k и m
очень важно. Вообще говоря, сокращение
может привести к неверному результату.
Например, 8 ≡ 6 (mod
2), но 4

3 (mod 2).
Впрочем, иногда после сокращения на k
результат может оказаться верным, хотя
k и m
не взаимно просты:

Например, 85 ≡ 10 (mod
15).

После сокращения на 5 получим верное
сравнение

17 ≡ 2 (mod 15).

Рассмотренные свойства сравнений
обобщаются следующее теоремой.

Теорема 2: Пусть

— с целыми коэффициентами. Пусть x
≡ y (mod
m).

Тогда p(x) ≡
p(y) (mod m).

Если, кроме того,

(mod m),
i = 0,1,2…n,
то

(mod m).

Доказательство: Непосредственно
следует из свойств 2° и 3°.

Замечание 1: Аналогичная
теорема верна и для многочленов от n
переменных с целыми коэффициентами.
Например,

если

(mod m), i =1,2,3…n, то

(mod m).

Замечание 2: Встречающиеся
в сравнении показатели степеней, нельзя
заменять сравнимыми по модулю m.
Иначе говоря, из того, что n
≡ k (mod
m) не следует,
что

(mod m).
Например, 3 ≡ 8 (mod
5), но

(mod 5), так
как
(mod
5), а

(mod 5).

В свойствах 7° — 10° некоторые манипуляции
проводят не только с обеими частями
сравнения, но и с модулем m.

7°. Обе части сравнения и модуль можно
домножить или сократить на их общий
множитель:

a ≡ b (mod
m)

a · k ≡ b · k (mod mk)

Доказательство: Пусть a
≡ b (mod
m). Тогда a
= b + m∙t

a∙k
= b∙k
+ m∙k∙t

a∙k
≡ b∙k
(mod mk).

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

■

8°. Если два числа сравнимы по модулю m,
то они сравнимы по любому модулю d,
делителю числа m:

Доказательство: Если a–b
делиться на m, а m
делиться на d, то по
транзитивности a–b
делиться d

a ≡ b
(mod d).

■

9°. Если два числа сравнимы по нескольким
модулям, то они сравнимы по модулю,
равному наименьшему общему кратному
этих модулей:

где
.

Доказательство: Если
,
то разность a–b
делиться на

и на
.
Значит, (свойство 1 НОК) a–b
делиться на
,
т.е. a ≡ b
(mod m).
Такое же рассуждение сохраняет силу и
для нескольких модулей.

■

10°. Если a ≡ b
(mod m),
то множество общих делителей a
и m совпадает с
множеством общих делителей b
и m. В частности
НОД(a,m)
= НОД(b,m).

Доказательство: Пусть a
≡ b (mod
m). Тогда a
– b = m∙t.Если
d — общий делитель a
и m, то
—
общий делитель b и
m. Обратное
аналогично.

■

п.2 Простейшие применения сравнений

Теория сравнений дает в руки исследователя
очень эффективный инструмент для решения
теоретико − числовых задач. Проиллюстрируем
его действенность несколькими
элементарными примерами.

Пример 1: Найти остаток от деления

на 7.

Решение: Имеем сравнение 2012 ≡ 612 ≡ -18 ≡
3 (mod 7). Значит,

(mod 7)

Но
,
поэтому

Ответ: остаток равен 3.

Пример 2: Доказать, что

делится на 17 при всех
.

Решение: Воспользуемся тем, что 258
(mod 17). Имеем

Следовательно, данная сумма делится на
17.

Пример 3: Вывести признаки делимости
на 9 и на 11.

Решение: Любое натурально число N
можно записать в виде

Заметим, что 10 ≡ 1 (mod 9).
Следовательно,

Число сравнимы по модулю 9, значит они
имеют одинаковые остатки при делении
на 9. В частности,

|| N делится на 9
сумма
цифр числа N делится
на 9||

Аналогично, из сравнения 10 ≡ -1 (mod
11) следует, что

Отсюда следует, что

N делится на
11Разность
между суммой цифр числа N,
стоящих на нечетных местах и суммой
цифр, стоящих на четных местах, делится
на 11.

Пример 4: Доказать, что уравнение

не имеет решений в целых числах.

Решение: Любое решение x
должно удовлетворять сравнению

При делении на 5 число x
может иметь в остатке 0,1,2,3 и 4.

Но, так как

значит

не может иметь остаток 3, т.е. сравнение

не имеет решений.

Пример 5: Определить день недели по
заданной дате.

Решение: Пусть N
обозначает год, m —
месяц, d — день

(1≤ m≤12), (1≤
d≤31) Первым
месяцем года (m = 1)
будем считать март, вторым (m
=2) — апрель и т.д. Тогда в високосные
годы день 29 февраля добавляется в конце
года, что удобно для расчета.

Обозначим ω —
номер для недели (1≤ ω≤
7), начиная отсчет с понедельника:

ω = 1 — Пн, ω
= 2 — Вт, ω = 3 — Ср
,…, ω=7 —Вс.

Пусть

— номер того дня недели, который мы
примем за точку отсчета. Напомним, что
Россия перешла на григорианский календарь
в феврале 1918 года, поэтому примем в
качестве

день недели 1 марта 1920 года. Таким образом,
считаем

N ≥ 1920.

Пусть

— номер дня 1 марта N-го
года. Заметим, что

365 ≡ 1 (mod 7),
поэтому каждый невисокосный год номер
дня недели увеличивается на 1. Если же
прошлый год был високосным, то к номеру
дня недели добавим 2, т.к.

366 ≡ 2 (mod 7).
Следовательно,

(mod
7)

Упростив это выражение, получим

(mod
7),

(mod
7).

Вычислим
.
1 марта 2012 года приходится на четверг,
т.е.

отсюда следует, что

(mod 7),

(mod
7).

Итак, 1 марта 1920 года был понедельник,
следовательно,

(mod 7). (1)

Пусть теперь задано число d
месяца m года N.
Чтобы определить искомый день недели
осталось вычислить количество дней,
прошедших от 1 марта до заданной даты.
Вычислим сначала номер дней недели для
1 числа каждого месяца.

В марте 31 день

1 апреля имеет номер
(mod
7)

В апреле 30 дней
1
мая имеет номер
(mod
7)

и так далее, составим небольшую таблицу,
в которой указано то слагаемое, которое
нужно прибавит к
.

Номер возрастает примерно на

в месяц. Поэтому нетрудно подобрать
формулу

m = 1,2,3…,12

которая дает нужное добавочное слагаемое
для любого месяца.

Итак, если ω — искомый день недели d
числа m месяца N
года, то к формуле (1) нужно прибавить

и (d-1) —
количество дней от 1 числа до нужной
даты. В итоге получим

(mod 7)

Определим, для примера день недели 22
июня 1941 года. Имеем N
= 1941, m = 4,
d = 22.

Итак, 22 июня 1941 года было воскресенье.

Соседние файлы в предмете Математический анализ

Источник

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

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

Свойства сравнимости по модулю[править | править код]

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

Пример[править | править код]

Связанные определения[править | править код]

Классы вычетов[править | править код]

Системы вычетов[править | править код]

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

Решение сравнений[править | править код]

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

Примеры[править | править код]

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

Системы сравнений[править | править код]

Применение[править | править код]

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

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

Литература[править | править код]

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

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

Решение сравнений по модулю

Решений нет

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

1.2 Теория сравнений и ее приложения

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

Свойства сравнений, не зависящие от модуля

Свойства сравнений, зависящие от модуля

1.2.2 Возведение в степень по модулю

Вам также может понравиться

Как найти отель в венеции

Глубокий мангал как исправить

Как составить схематический план места происшествия

Добавить комментарий Отменить ответ