Модульная арифметика

В математике модульная арифметика — это система арифметики для целых чисел , где числа «переходят» при достижении определенного значения, называемого модулем . Современный подход к модульной арифметике был разработан Карлом Фридрихом Гауссом в его книге Disquisitiones Arithmeticae , опубликованной в 1801 году.

Знакомое использование модульной арифметики — в 12-часовом формате , в котором день делится на два 12-часовых периода. Если сейчас 7:00, то через 8 часов будет 3:00. Простое сложение даст результат 7 + 8 = 15 , но 15:00 читается как 3:00 на циферблате часов, потому что часы «переворачиваются» каждые 12 часов, и номер часа начинается заново с нуля, когда достигает 12. Мы говорим, что 15 сравнимо с 3 по модулю 12, что записывается как 15 ≡ 3 (mod 12), так что 7 + 8 ≡ 3 (mod 12). Аналогично, 8:00 представляет собой период в 8 часов, а умножив это число дважды, получим 16:00, что на циферблате часов отображается как 4:00, что записывается как 2 × 8 ≡ 4 (mod 12).

Для данного целого числа m ≥ 1 , называемого модулем , два целых числа a и b называются сравнимыми по модулю m , если m является делителем их разности; то есть если существует целое число k такое, что

а − b = км .

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

а ≡ b (mod m ) .

Скобки означают, что (mod m ) применяется ко всему уравнению, а не только к правой части (здесь b ).

Эту запись не следует путать с записью b mod m (без скобок), которая относится к операции деления по модулю , остатку от b при делении на m : то есть b mod m обозначает уникальное целое число r, такое что 0 ≤ r < m и r ≡ b (mod m ) .

Отношение конгруэнтности можно переписать как

а = км + б ,

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

а = пм + г ,

б = qм + г ,

где 0 ≤ r < m — общий остаток. Мы восстанавливаем предыдущее соотношение ( a − b = km ), вычитая эти два выражения и устанавливая k = p − q .

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

В модуле 12 можно утверждать, что:

38 ≡ 14 (мод 12)

потому что разность составляет 38 − 14 = 24 = 2 × 12 , кратная 12. Эквивалентно, 38 и 14 имеют одинаковый остаток 2 при делении на 12 .

Определение конгруэнтности применимо и к отрицательным значениям. Например:

${\displaystyle {\begin{aligned}2&\equiv -3{\pmod {5}}\\-8&\equiv 7{\pmod {5}}\\-3&\equiv -8{\pmod {5}}.\end{aligned}}}$

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

• Рефлексивность: a ≡ a (mod m )
• Симметрия: a ≡ b (mod m ), если b ≡ a (mod m ) .
• Транзитивность: Если a ≡ b (mod m ) и b ≡ c (mod m ) , то a ≡ c (mod m )

Если a ₁ ≡ b ₁ (mod m ) и a ₂ ≡ b ₂ (mod m ) , или если a ≡ b (mod m ) , то: ^[1]

• a + k ≡ b + k (mod m ) для любого целого числа k (совместимость с переводом)
• ka ≡ kb (mod m ) для любого целого числа k (совместимость с масштабированием)
• ka ≡ kb (mod km ) для любого целого числа k
• a ₁ + a ₂ ≡ b ₁ + b ₂ (mod m ) (совместимость со сложением)
• a ₁ − a ₂ ≡ b ₁ − b ₂ (mod m ) (совместимость с вычитанием)
• a ₁ a ₂ ≡ b ₁ b ₂ (mod m ) (совместимость с умножением)
• a ^k ≡ b ^k (mod m ) для любого неотрицательного целого числа k (совместимость с возведением в степень)
• p ( a ) ≡ p ( b ) (mod m ) для любого полинома p ( x ) с целыми коэффициентами (совместимость с оценкой полинома)

Если a ≡ b (mod m ) , то, как правило, неверно, что k ^a ≡ k ^b (mod m ) . Однако верно следующее:

• Если c ≡ d (mod φ ( m )), где φ — функция Эйлера , то a ^c ≡ a ^d (mod m ) — при условии, что a взаимно просто с m .

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

• Если a + k ≡ b + k (mod m ) , где k — любое целое число, то a ≡ b (mod m ) .
• Если ka ≡ kb (mod m ) и k взаимно просто с m , то a ≡ b (mod m ) .
• Если ka ≡ kb (mod km ) и k ≠ 0 , то a ≡ b (mod m ) .

Последнее правило можно использовать для переноса модульной арифметики в деление. Если b делит a , то ( a / b ) mod m = ( a mod bm )/ b .

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

• Существование: Существует целое число, обозначенное a ⁻¹ , такое, что aa ⁻¹ ≡ 1 (mod m ) , тогда и только тогда, когда a взаимно просто с m . Это целое число a ⁻¹ называется модульным мультипликативным обратным числом a по модулю m .
• Если a ≡ b (mod m ) и a ⁻¹ существует, то a ⁻¹ ≡ b ⁻¹ (mod m ) (совместимость с мультипликативной инверсией и, если a = b , уникальность по модулю m ).
• Если ax ≡ b (mod m ) и a взаимно просто с m , то решение этого линейного сравнения задается формулой x ≡ a ⁻¹ b (mod m ) .

Мультипликативный обратный элемент x ≡ a ⁻¹ (mod m ) можно эффективно вычислить, решив уравнение Безу a x + my = 1 для x , y , используя расширенный алгоритм Евклида .

В частности, если p — простое число, то a взаимно просто с p для любого a, такого что 0 < a < p ; таким образом, существует мультипликативная обратная величина для всех a , которые не сравнимы с нулем по модулю p .

Некоторые из более продвинутых свойств отношений конгруэнтности следующие:

• Малая теорема Ферма : Если p — простое число и не делит a , то a ^{p −1} ≡ 1 (mod p ) .
• Теорема Эйлера : Если a и m взаимно просты, то a ^{φ ( m )} ≡ 1 (mod m ) , где φ — функция Эйлера .
• Простым следствием малой теоремы Ферма является то, что если p — простое число, то a ⁻¹ ≡ a ^{p −2} (mod p ) — мультипликативное обратное к 0 < a < p . В более общем смысле, из теоремы Эйлера, если a и m взаимно просты, то a ⁻¹ ≡ a ^{φ ( m )−1} (mod m ) . Следовательно, если ax ≡ 1 (mod m ) , то x ≡ a ^{φ ( m )−1} (mod m ) .
• Другим простым следствием является то, что если a ≡ b (mod φ ( m )) , где φ — функция Эйлера, то k ^a ≡ k ^b (mod m ) при условии, что k взаимно просто с m .
• Теорема Вильсона : p является простым числом тогда и только тогда, когда ( p − 1)! ≡ −1 (mod p ) .
• Китайская теорема об остатках : Для любых a , b и взаимно простых m , n существует единственный x (mod mn ), такой что x ≡ a (mod m ) и x ≡ b (mod n ) . Фактически, x ≡ bm _n ⁻¹ m + an _m ⁻¹ n (mod mn ), где m _n ⁻¹ — обратное число m по модулю n , а n _m ⁻¹ — обратное число n по модулю m .
• Теорема Лагранжа : если p — простое число и f ( x ) = a ₀ x ^d + ... + a _d — многочлен с целыми коэффициентами, такой что p не является делителем a ₀ , то сравнение f ( x ) ≡ 0 (mod p ) имеет не более d неконгруэнтных решений.
• Первообразный корень по модулю m : Число g является первообразным корнем по модулю m , если для каждого целого числа a, взаимно простого с m , существует целое число k, такое что g ^k ≡ a (mod m ) . Первообразный корень по модулю m существует тогда и только тогда, когда m равно 2, 4, p ^k или 2 p ^k , где p — нечетное простое число, а k — положительное целое число. Если первообразный корень по модулю m существует, то существует ровно φ ( φ ( m )) таких первообразных корней, где φ — функция Эйлера.
• Квадратичный вычет : Целое число a является квадратичным вычетом по модулю m , если существует целое число x, такое что x ² ≡ a (mod m ) . Критерий Эйлера утверждает, что если p — нечетное простое число, а a не кратно p , то a является квадратичным вычетом по модулю p тогда и только тогда, когда

  а ^{( p −1)/2} ≡ 1 (mod p ) .

Отношение конгруэнтности — это отношение эквивалентности . Класс эквивалентности по модулю m целого числа a — это множество всех целых чисел вида a + km , где k — любое целое число. Он называется классом конгруэнтности или классом вычетов a по модулю  m и может обозначаться как ( a mod m ) , или как a или [ a ], когда модуль m известен из контекста.

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

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

Следовательно, ( a mod m ) обозначает, как правило, единственное целое число k, такое что 0 ≤ k < m и k ≡ a (mod m ) ; оно называется вычетом числа a по модулю  m .

В частности, ( a mod m ) = ( b mod m ) эквивалентно a ≡ b (mod m ) , и это объясняет, почему в этом контексте « = » часто используется вместо « ≡ ».

Каждый класс остатков по модулю m может быть представлен любым из его членов, хотя мы обычно представляем каждый класс остатков наименьшим неотрицательным целым числом, которое принадлежит этому классу ^[2] (так как это правильный остаток, который получается в результате деления). Любые два члена различных классов остатков по модулю m являются несопоставимыми по модулю m . Более того, каждое целое число принадлежит одному и только одному классу остатков по модулю m . ^[3]

Набор целых чисел {0, 1, 2, ..., m − 1} называется наименьшей системой вычетов по модулю m . Любой набор из m целых чисел, никакие два из которых не сравнимы по модулю m , называется полной системой вычетов по модулю m .

Система наименьших остатков — это полная система остатков, а полная система остатков — это просто набор, содержащий ровно одного представителя каждого класса остатков по модулю m . ^[4] Например, система наименьших остатков по модулю 4 — это {0, 1, 2, 3} . Некоторые другие системы полных остатков по модулю 4 включают:

• {1, 2, 3, 4}
• {13, 14, 15, 16}
• {−2, −1, 0, 1}
• {−13, 4, 17, 18}
• {−5, 0, 6, 21}
• {27, 32, 37, 42}

Некоторые наборы, которые не являются полными системами остатков по модулю 4:

• {−5, 0, 6, 22} , так как 6 сравнимо с 22 по модулю 4 .
• {5, 15} , поскольку полная система вычетов по модулю 4 должна иметь ровно 4 неконгруэнтных класса вычетов.

При наличии функции Эйлера φ ( m ) любой набор целых чисел φ ( m ) , которые взаимно просты с m и взаимно неконгруэнтны по модулю m, называется приведенной системой вычетов по модулю m . ^[5] Например, набор {5, 15} из вышеприведенного примера является примером приведенной системы вычетов по модулю 4.

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

Замечание: В контексте этого параграфа модуль m почти всегда принимается положительным.

Множество всех классов конгруэнтности по модулю m называется кольцом целых чисел по модулю m , ^[6] и обозначается , , или . ^[7] Однако эта нотация не рекомендуется, поскольку ее можно спутать с множеством m -адических целых чисел . Кольцо является основополагающим для различных разделов математики (см. § Приложения ниже).${\textstyle \mathbb {Z} /m\mathbb {Z} }$${\displaystyle \mathbb {Z} /m}$${\displaystyle \mathbb {Z} _{m}}$${\displaystyle \mathbb {Z} _{m}}$ ${\displaystyle \mathbb {Z} /m\mathbb {Z} }$

При m > 0 имеем

${\displaystyle \mathbb {Z} /m\mathbb {Z} =\left\{{\overline {a}}_{m}\mid a\in \mathbb {Z} \right\}=\left\{{\overline {0}}_{m},{\overline {1}}_{m},{\overline {2}}_{m},\ldots ,{\overline {m{-}1}}_{m}\right\}.}$

При m = 1 — нулевое кольцо ; при m = 0 — не пустое множество ; скорее, оно изоморфно , поскольку a ₀ = { a } .${\displaystyle \mathbb {Z} /m\mathbb {Z} }$${\displaystyle \mathbb {Z} /m\mathbb {Z} }$${\displaystyle \mathbb {Z} }$

Сложение, вычитание и умножение определяются следующими правилами:${\displaystyle \mathbb {Z} /m\mathbb {Z} }$

• ${\displaystyle {\overline {a}}_{m}+{\overline {b}}_{m}={\overline {(a+b)}}_{m}}$
• ${\displaystyle {\overline {a}}_{m}-{\overline {b}}_{m}={\overline {(a-b)}}_{m}}$
• ${\displaystyle {\overline {a}}_{m}{\overline {b}}_{m}={\overline {(ab)}}_{m}.}$

Из приведенных выше свойств следует, что с этими операциями — коммутативное кольцо . Например, в кольце имеем${\displaystyle \mathbb {Z} /m\mathbb {Z} }$${\displaystyle \mathbb {Z} /24\mathbb {Z} }$

${\displaystyle {\overline {12}}_{24}+{\overline {21}}_{24}={\overline {33}}_{24}={\overline {9}}_{24}}$

как в арифметике для 24-часового формата времени.

Обозначение используется потому, что это кольцо является фактор-кольцом по идеалу , множеству, образованному всеми km с${\displaystyle \mathbb {Z} /m\mathbb {Z} }$${\displaystyle \mathbb {Z} }$ ${\displaystyle m\mathbb {Z} }$${\displaystyle k\in \mathbb {Z} .}$

Рассматриваемая как группа по сложению, является циклической группой , и все циклические группы изоморфны для некоторого m . ^[8]${\displaystyle \mathbb {Z} /m\mathbb {Z} }$${\displaystyle \mathbb {Z} /m\mathbb {Z} }$

Кольцо целых чисел по модулю m является полем тогда и только тогда, когда m — простое число (это гарантирует, что каждый ненулевой элемент имеет мультипликативный обратный элемент ). Если m = p ^k — степень простого числа с k > 1 , то существует единственное (с точностью до изоморфизма) конечное поле с m элементами, которое не изоморфно , которое не является полем, поскольку имеет делители нуля .${\displaystyle \mathrm {GF} (m)=\mathbb {F} _{m}}$${\displaystyle \mathbb {Z} /m\mathbb {Z} }$

Если m > 1 , обозначает мультипликативную группу целых чисел по модулю m , которые обратимы. Она состоит из классов конгруэнтности a _m , где a взаимно просто с m ; это как раз те классы, которые обладают мультипликативным обратным. Они образуют абелеву группу относительно умножения; ее порядок равен φ ( m ) , где φ — функция Эйлера${\displaystyle (\mathbb {Z} /m\mathbb {Z} )^{\times }}$

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

Очень практичным применением является вычисление контрольных сумм в идентификаторах серийных номеров. Например, Международный стандартный номер книги (ISBN) использует арифметику по модулю 11 (для 10-значного ISBN) или по модулю 10 (для 13-значного ISBN) для обнаружения ошибок. Аналогично, например, Международные номера банковских счетов (IBAN) используют арифметику по модулю 97 для обнаружения ошибок ввода пользователя в номера банковских счетов. В химии последняя цифра номера реестра CAS (уникальный идентификационный номер для каждого химического соединения) является контрольной цифрой , которая вычисляется путем взятия последней цифры первых двух частей номера реестра CAS, умноженного на 1, предыдущей цифры, умноженной на 2, предыдущей цифры, умноженной на 3 и т. д., сложения всех этих цифр и вычисления суммы по модулю 10.

В криптографии модульная арифметика напрямую поддерживает системы открытого ключа , такие как RSA и Диффи–Хеллмана , и обеспечивает конечные поля , которые лежат в основе эллиптических кривых , и используется во множестве алгоритмов симметричного ключа , включая Advanced Encryption Standard (AES), International Data Encryption Algorithm (IDEA) и RC4 . RSA и Диффи–Хеллмана используют модульное возведение в степень .

В компьютерной алгебре модульная арифметика обычно используется для ограничения размера целочисленных коэффициентов в промежуточных вычислениях и данных. Она используется в полиномиальной факторизации , задаче, для которой все известные эффективные алгоритмы используют модульную арифметику. Она используется наиболее эффективными реализациями полиномиального наибольшего общего делителя , точной линейной алгебры и алгоритмов базиса Грёбнера над целыми и рациональными числами. Как было опубликовано на Fidonet в 1980-х годах и заархивировано в Rosetta Code , модульная арифметика была использована для опровержения гипотезы Эйлера о сумме степеней на микрокомпьютере Sinclair QL, используя всего одну четвертую целочисленной точности, используемой суперкомпьютером CDC 6600, чтобы опровергнуть ее два десятилетия назад с помощью поиска методом грубой силы . ^[9]

В информатике модульная арифметика часто применяется в побитовых операциях и других операциях, включающих циклические структуры данных фиксированной ширины . Операция по модулю, реализованная во многих языках программирования и калькуляторах , является применением модульной арифметики, которое часто используется в этом контексте. Логический оператор XOR суммирует 2 бита по модулю 2.

Использование длинного деления для превращения дроби в периодическую десятичную дробь в любой системе счисления с основанием b эквивалентно модульному умножению b на знаменатель. Например, для десятичной дроби b = 10.

В музыке арифметика по модулю 12 используется при рассмотрении системы двенадцатитоновой равномерной темперации , где имеет место октавная и энгармоническая эквивалентность (то есть высоты тона в соотношении 1:2 или 2:1 эквивалентны, а нота до- диез считается такой же, как и нота ре- бемоль ).

Метод выбрасывания девяток предлагает быструю проверку вычислений десятичных арифметических чисел, выполняемых вручную. Он основан на модульной арифметике по модулю 9, и в частности на решающем свойстве, что 10 ≡ 1 (mod 9).

Арифметика по модулю 7 используется в алгоритмах, которые определяют день недели для заданной даты. В частности, сравнение Целлера и алгоритм Судного дня активно используют арифметику по модулю 7.

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

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

Некоторые операции, такие как нахождение дискретного логарифма или квадратичного сравнения, кажутся такими же сложными, как факторизация целых чисел , и поэтому являются отправной точкой для криптографических алгоритмов и шифрования . Эти задачи могут быть NP-промежуточными .

Решение системы нелинейных модульных арифметических уравнений является NP-полной задачей . ^[10]

• Джон Л. Берггрен. "Модулярная арифметика". Encyclopaedia Britannica .
• Апостол, Том М. (1976), Введение в аналитическую теорию чисел , Бакалаврские тексты по математике, Нью-Йорк-Гейдельберг: Springer-Verlag, ISBN 978-0-387-90163-3, MR  0434929, Zbl  0335.10001. См., в частности, главы 5 и 6 для обзора базовой модульной арифметики.
• Маартен Буллинк «Модулярная арифметика до К. Ф. Гаусса. Систематизации и обсуждения проблем остатков в Германии XVIII века»
• Томас Х. Кормен , Чарльз Э. Лейзерсон , Рональд Л. Ривест и Клиффорд Стайн . Введение в алгоритмы , второе издание. MIT Press и McGraw-Hill, 2001. ISBN 0-262-03293-7 . Раздел 31.3: Модульная арифметика, стр. 862–868. 
• Энтони Джойя, Теория чисел, введение , переиздание (2001) Дувр. ISBN 0-486-41449-3 . 
• Лонг, Кэлвин Т. (1972). Элементарное введение в теорию чисел (2-е изд.). Лексингтон: DC Heath and Company . LCCN  77171950.
• Pettofrezzo, Anthony J.; Byrkit, Donald R. (1970). Элементы теории чисел . Englewood Cliffs: Prentice Hall . ISBN 9780132683005. LCCN  71081766.
• Сенгадир, Т. (2009). Дискретная математика и комбинаторика . Ченнаи, Индия: Pearson Education India. ISBN 978-81-317-1405-8. OCLC  778356123.

• «Конгруэнтность», Энциклопедия математики , EMS Press , 2001 [1994]
• В этой статье о модульном искусстве можно узнать больше о применении модульной арифметики в искусстве.
• Статья о модульной арифметике на вики GIMPS
• Модульная арифметика и закономерности в таблицах сложения и умножения