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

Эта статья посвящена нотации (mod m ) . Информацию о двоичной операции mod( a,m ) см. по модулю .

В этих часах для измерения времени используется арифметика по модулю 12. Прибавление 4 часов к 9 часам дает 1 час, поскольку 13 соответствует 1 по модулю 12.

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

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

Конгруэнтность

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

а - б знак равно км .

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

а ≡ б (мод м ) .

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

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

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

а = км + б ,

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

а = pm + r ,

б = дм + р ,

где 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 .

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

${\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 ) , то:

• 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 ) (совместимость с умножением)
• а ^к ≡ б ^к (mod m ) для любого неотрицательного целого числа k (совместимость с возведением в степень)
• p ( a ) ≡ p ( b ) (mod m ) для любого многочлена p ( x ) с целыми коэффициентами (совместимость с полиномиальной оценкой)

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

• Если c ≡ d (mod φ ( m )), где φ — тотент-функция Эйлера , то a ^с ≡ а ^д (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 .

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

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

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

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

Расширенные свойства

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

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

  а ^{( п −1)/2} ≡ 1 (против п ) .

Классы конгруэнтности

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

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

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

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

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

Остаточные системы

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

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

Система наименьших вычетов — это полная система вычетов, а полная система вычетов — это просто набор, содержащий ровно одного представителя каждого класса вычетов по модулю m . Например, система наименьших вычетов по модулю 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, 15}, приведенный выше, является примером системы сокращенных вычетов по модулю 4.

Системы покрытия

Основная статья: Система покрытия

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

Целые числа по модулю m

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

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

Для m > 0 имеем

$\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 , $\mathbb {Z} /m\mathbb {Z}$– нулевое кольцо ; когда м = 0 , $\mathbb {Z} /m\mathbb {Z}$не является пустым множеством ; , он изоморфен скорее $\mathbb {Z}$, поскольку а ₀ = { а } .

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

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

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

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

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

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

Рассматривается как группа в стадии добавления, $\mathbb {Z} /m\mathbb {Z}$ является циклической группой , и все циклические группы изоморфны $\mathbb {Z} /m\mathbb {Z}$ для некоторых м .

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

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

Расширение до действительных чисел

См. также: по модулю

Приложения

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

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

В криптографии модульная арифметика напрямую лежит в основе с открытым ключом систем , таких как RSA и Диффи-Хеллмана , и обеспечивает конечные поля , лежащие в основе эллиптических кривых , и используется во множестве алгоритмов симметричного ключа , включая Advanced Encryption Standard (AES), Международный алгоритм шифрования данных ( ИДЕЯ) и RC4 . RSA и Диффи-Хеллмана используют модульное возведение в степень .

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

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

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

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

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

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

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

Вычислительная сложность

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

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

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

Пример реализации

Ниже приведены три достаточно быстрые функции C: две для выполнения модульного умножения и одна для модульного возведения в степень целых чисел без знака длиной не более 63 бит без переполнения переходных операций.

Алгоритм вычисления a ⋅ b (mod m ) :

uint64_t   mul_mod  (  uint64_t   a  ,   uint64_t   b  ,   uint64_t   m  )   { 
     if   (  !  ((  a   |   b  )   &   (  0xFFFFFFFFULL   <<   32  )))   return   a   *   b   %   m  ; 

      uint64_t   d   =   0  ,   mp2   =   m   >>   1  ; 
      интервал   я  ; 
      если   (  а   >=   м  )   а   %=   м  ; 
      если   (  б   >=   м  )   б   %=   м  ; 
      для   (  я   знак равно   0  ;   я   <   64  ;   ++  я  )   { 
         d   =   (  d   >   mp2  )   ?    (  d   <<   1  )   -   m   :   d   <<   1  ; 
          если   (  a   &   0x8000000000000000ULL  )   d   +=   b  ; 
          если   (  d   >=   м  )   d   -=   м  ; 
          а   <<=   1  ; 
      } 
     Вернуть   д  ; 
  } 

В компьютерных архитектурах, где доступен расширенный формат точности с минимум 64 битами мантиссы (например, тип long double в большинстве компиляторов C x86), следующая процедура выполняется быстрее, чем решение, использующее цикл, благодаря использованию трюка, который: аппаратно, умножение с плавающей запятой приводит к сохранению старших значащих битов произведения, а целочисленное умножение приводит к сохранению младших битов:

uint64_t   mul_mod  (  uint64_t   a  ,   uint64_t   b  ,   uint64_t   m  )   { 
     long   double   x  ; 
      uint64_t   c  ; 
      int64_t   р  ; 
      если   (  а   >=   м  )   а   %=   м  ; 
      если   (  б   >=   м  )   б   %=   м  ; 
      х знак   равно   а  ; 
      с   =   х   *   б   /   м  ; 
      r   =   (  int64_t  )(  a   *   b   -   c   *   m  )   %   (  int64_t  )  m  ; 
      вернуть   р   <   0   ?    р   +   м   :   р  ; 
  } 

Ниже приведена функция C для выполнения модульного возведения в степень, которая использует функцию mul_mod , реализованную выше.

Алгоритмический способ вычисления ^б (мод . м ) :

uint64_t   pow_mod  (  uint64_t   a  ,   uint64_t   b  ,   uint64_t   м  )   { 
     uint64_t   р   =   м   ==   1   ?    0   :   1  ; 
      в то время как   (  б   >   0  )   { 
         если   (  б   &   1  )   р   знак равно   mul_mod  (  р  ,   а  ,   м  ); 
          б   =   б   >>   1  ; 
          а   =   mul_mod  (  а  ,   а  ,   м  ); 
      } 
     Вернуть   р  ; 
  } 

Однако для того, чтобы все вышеперечисленные процедуры работали, m не должно превышать 63 бита.

См. также

• Булево кольцо
• Круговой буфер
• Отдел (математика)
• Конечное поле
• Легендарный символ
• Модульное возведение в степень
• По модулю (математика)
• Мультипликативная группа целых чисел по модулю n
• Период Пизано (последовательности Фибоначчи по модулю n )
• Примитивный корень по модулю n
• Квадратичная взаимность
• Квадратичный остаток
• Рациональная реконструкция (математика)
• Система пониженного остатка
• Арифметика серийных номеров (частный случай модульной арифметики)
• Двухэлементная булева алгебра
• Темы, относящиеся к теории групп, лежащей в основе модульной арифметики:
  • Циклическая группа
  • Мультипликативная группа целых чисел по модулю n
• Другие важные теоремы, относящиеся к модульной арифметике:
  • Теорема Кармайкла
  • Китайская теорема об остатках
  • Теорема Эйлера
  • Малая теорема Ферма (частный случай теоремы Эйлера)
  • Теорема Лагранжа
  • Лемма Туэ

Ссылки

• Джон Л. Берггрен. «модульная арифметика » Британская энциклопедия
• Апостол, Том М. (1976), Введение в аналитическую теорию чисел , Тексты для студентов по математике, Нью-Йорк-Гейдельберг: Springer-Verlag, ISBN  978-0-387-90163-3 , МР   0434929 , Збл   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-е изд.). Лексингтон: округ Колумбия, Хит и компания . LCCN   77171950 .
• Петтофреззо, Энтони Дж.; Биркит, Дональд Р. (1970). Элементы теории чисел . Энглвудские скалы: Прентис-холл . ISBN  9780132683005 . LCCN   71081766 .
• Сенгадир, Т. (2009). Дискретная математика и комбинаторика . Ченнаи, Индия: Pearson Education India. ISBN  978-81-317-1405-8 . OCLC   778356123 .

Внешние ссылки

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