Сравнение чисел по модулю
Сравнение по модулю
Сравнения, система вычетов, решение линейных систем по модулю
Предпосылкой к созданию теории сравнений стало восстановление сочинений Диофанта , которые были выпущены в подлиннике и с латинским переводом, благодаря Баше де Мезириаку , в году. Например, в письме к Френиклю де Бесси ru fr [4] 18 октября года он сообщил без доказательства теорему , впоследствии получившую название малой теоремы Ферма. Кроме этого Лейбницем был предложен прообраз формулировки теоремы Вильсона. Позже изучение вопросов, посвященных теории чисел и теории сравнений, было продолжено Эйлером , который ввел квадратичный закон взаимности и обобщил теорему Ферма , установив, что. Понятие и символьное обозначение сравнений было введено Гауссом , как важный инструмент для обоснования его арифметической теории, работа над которой была начата им в году. Используя эти методы Гаусс преобразовал все накопленные до него сведения, связанные с операциями сравнения по модулю, в стройную теорию, которая впервые была изложена в этой же книге. Кроме этого, он исследовал сравнения первой и второй степени, теорию квадратичных вычетов и связанный с ней квадратичный закон взаимности [5]. Доказана равносильность определения условию 2 , которое эквивалентно условию 1. Например, числа 32 и сравнимы по модулю 7, так как оба числа при делении на 7 дают остаток Сравнения по одному и тому же модулю обладают многими свойствами обычных равенств. Например, их можно складывать, вычитать и перемножать: При этом нельзя выполнять эти операции со сравнениями, если их модули не совпадают [9]. Сравнения, однако, нельзя, вообще говоря, делить друг на друга или на другие числа. Правила сокращения для сравнений следующие. Система вычетов позволяет осуществлять арифметические операции над конечным набором чисел, не выходя за его пределы. Сравнение обозначается следующим образом:. Так же, как и в кольце целых чисел, такие сравнения можно складывать, вычитать и перемножать [14]. В теории чисел , криптографии и других областях науки часто возникает задача поиска решений сравнения первой степени вида. При этом возможны два случая:. Заменим 26 на 4, сравнимое с ним по модулю 22, и затем сократим все три числа на Первый способ решения — воспользоваться соотношением Безу. Второй способ решения, более простой и быстрый, не требует построения соотношения Безу, но также эквивалентен алгоритму Евклида. Делим модуль на коэффициент при x с остатком: На каждом следующем шаге уменьшаем аналогично, пока не получим единицу. Аналогично делим на новый коэффициент при x: Далее можно было бы сделать аналогично ещё 5 шагов, но проще разделить обе части сравнения на 10 и сразу получить результат: Сравнения второй степени по простому модулю m имеет следующий общий вид:. Решение этого сравнения сводится к выяснению, является ли данное число квадратичным вычетом с помощью квадратичного закона взаимности и последующему вычислению квадратного корня по данному модулю [16]. Для вычисления квадратного корня из квадратичного вычета существует вероятностный метод Берлекэмпа. Другими словами, китайская теорема об остатках утверждает, что кольцо вычетов по модулю произведения нескольких взаимно простых чисел является прямым произведением соответствующих множителям колец вычетов. Методы теории сравнений используются в теории чисел , теории групп , теории колец , теории узлов , общей алгебре , криптографии , информатике , химии и других областях. Например, сравнения часто применяются для вычисления контрольных сумм, используемых в идентификаторах. Так, для определения ошибок при вводе международного номера банковского счета используется сравнение по модулю 97 [17]. Также, модульная арифметика обеспечивает конечные поля , над которыми затем строятся эллиптические кривые , и используется в различных протоколах с симметричным ключом AES , IDEA [18]. В химии последняя цифра в регистрационном номере CAS является значением контрольной суммы , которая вычисляется путём сложения последней цифры номера, умноженной на 1, второй справа цифры, умноженной на 2, третьей, умноженной на три и так далее до первой слева цифры, завершаясь вычислением остатка от деления на 10 [19]. Необходимость условий 1 и 2 доказывается следующим образом: Достаточность условий 1 и 2: Кроме вышеперечисленных свойств, для сравнений справедливы следующие утверждения: Можно делить обе части сравнения на число, но только взаимно простое с модулем: Можно одновременно разделить обе части сравнения и модуль на их общий делитель: Системы вычетов Система вычетов позволяет осуществлять арифметические операции над конечным набором чисел, не выходя за его пределы. Сравнение обозначается следующим образом: При этом возможны два случая: Заменим 26 на 4, сравнимое с ним по модулю 22, и затем сократим все три числа на 2: Умножая сравнение на 4, получаем решение по модулю Системы сравнений Основная статья: Китайская теорема об остатках. Сложение по модулю 2 Возведение в степень по модулю Показатель числа по модулю Алгоритмы быстрого возведения в степень по модулю. Виртуальный компьютерный музей Проверено 31 июля Государственное издательство физико-математической литературы, Сравнения 2-й степени по простому модулю, Глава Научное изд-во ТВП, Уральский государственный университет им. Введение в алгебраические коды — 2-е изд. ИППИ РАН , Эта статья входит в число добротных статей русскоязычного раздела Википедии.
Возьмём произвольное фиксированное натуральное число и будем рассматривать остатки при делении на различных целых чисел. При рассмотрении свойств этих остатков и проведении операций над ними удобно ввести понятие сравнения по модулю. Два целых числа и называются сравнимыми по модулю , если их разность делится без остатка на. Число называется модулем сравнения. Если разность не делится на , то запишем:. Согласно определению, означает, что делится на. Поэтому в качестве определения сравнения можно взять следующую эквивалентную формулировку:. Целые числа и называются сравнимыми по модулю , если остатки от деления этих чисел на равны. Для фиксированного натурального числа отношение сравнимости по модулю обладает следующими свойствами:. Таким образом, отношение сравнимости по модулю является отношением эквивалентности на множестве целых чисел. При делении целых чисел на модуль в остатке получатся числа. Отнесём все целые числа, дающие при делении на один и тот же остаток в один класс, поэтому получится различных классов по модулю. В один класс попадут равноостаточные числа, они называются вычетами друг друга. Множество всех чисел сравнимых с по модулю называется классом вычетов по модулю. Обозначим через класс вычетов, которые при делении на дают остаток. Через — числа, дающие при делении остаток. Полной системой вычетов по модулю называется совокупность целых чисел, содержащая точно по одному представителю из каждого класса вычетов по модулю. Каждый класс вычетов по модулю содержит в точности одно из чисел совокупности всех возможных остатков от деления на: Можно доказать, что любая совокупность чисел , попарно несравнимых по модулю , есть полная система вычетов по модулю. Часто рассматривают полную систему наименьших неотрицательных вычетов по модулю:. Приведенной системой вычетов по модулю m называется совокупность всех вычетов из полной системы, взаимно простых с модулем. Иначе говоря, приведённая система вычетов по модулю - это система чисел, взаимно простых с модулем, взятых по одному и только по одному из каждого класса вычетов по модулю. Приведенную систему обычно выбирают из системы наименьших неотрицательных вычетов. Число классов, взаимно простых с модулем , равно значению функции Эйлера. Материал из Модулярная арифметики. Персональные инструменты Представиться системе. Пространства имён Статья Обсуждение. Просмотры Читать Просмотр История. Навигация Главная Свежие правки Спецстраницы Загрузить файл Контакты. Последнее изменение этой страницы: К этой странице обращались раз. Содержимое доступно в соответствии с Creative Commons Attribution Non-Commercial Share Alike. Политика конфиденциальности Описание Модулярная арифметики Отказ от ответственности. Содержание 1 Определения 2 Примеры 3 Свойства 4 Классы вычетов.
Образец рабочих местах для трудоустройства инвалидов
Каталог магазина h m в саратове
Спб расписание автобусов
Стихи пейзажной лирики тютчева
Существует ли волшебство