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

Вычисление по модулю фиксированного целого числа

Для измерения времени в этих часах используется арифметика по модулю 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).

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

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

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

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

а ≡ б (мод п ) .

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

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

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

а = кн + б ,

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

а = рп + р ,

б = qn + р ,

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

Примеры

По модулю 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 n )
• Симметрия: a ≡ b (mod n ), если b ≡ a (mod n ) .
• Транзитивность: если a ≡ b (mod n ) и b ≡ c (mod n ) , то a ≡ c (mod n ).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  а ^{( п -1)/2} ≡ 1 (мод п ) .

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

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

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

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

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

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

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

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

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

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

Системы пониженного остатка

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

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

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

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

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

Для n > 0 имеем

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

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

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

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

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

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

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

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

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

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

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

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

Приложения

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

Очень практичным применением является вычисление контрольных сумм в идентификаторах серийных номеров. Например, международный стандартный номер книги (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 , чтобы опровергнуть ее двумя десятилетиями ранее. через поиск методом перебора . ^[9]

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

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

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

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

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

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

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

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

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

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

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

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

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

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 , реализованную выше.

Алгоритмический способ вычисления a ^b (mod m ) :

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
• Другие важные теоремы, относящиеся к модульной арифметике:
  • Теорема Кармайкла
  • Китайская теорема об остатках
  • Теорема Эйлера
  • Малая теорема Ферма (частный случай теоремы Эйлера)
  • Теорема Лагранжа
  • Лемма Туэ

Примечания

1. Шандор Лехоцкий; Ричард Руски (2006). Дэвид Патрик (ред.). Искусство решения проблем . Том. 1 (7-е изд.). Компания «АоПС Инкорпорейтед». п. 44. ИСБН 0977304566.
2. Вайсштейн, Эрик В. «Модульная арифметика». mathworld.wolfram.com . Проверено 12 августа 2020 г.
3. Петтофреззо и Биркит (1970, стр. 90)
4. Лонг (1972, стр. 78)
5. Лонг (1972, стр. 85)
6. Это кольцо , как показано ниже.
7. «2.3: Целые числа по модулю n» . Математика LibreTexts . 16 ноября 2013 г. Проверено 12 августа 2020 г.
8. Сенгадир Т., Дискретная математика и комбинаторика , с. 293, в Google Книгах.
9. "Гипотеза Эйлера о сумме степеней" . Rosettacode.org . Проверено 11 ноября 2020 г.
10. Гэри, MR; Джонсон, DS (1979). Компьютеры и трудноразрешимые проблемы. Руководство по теории NP-полноты . У. Х. Фриман. ISBN 0716710447.
11. Этот код использует литеральную нотацию C для беззнаковых длинных шестнадцатеричных чисел, которые заканчиваются на ULL. См. также раздел 6.4.4 спецификации языка n1570.

Рекомендации

• Джон Л. Берггрен. «модульная арифметика». Британская энциклопедия .
• Апостол, Том М. (1976), Введение в аналитическую теорию чисел , Тексты для студентов по математике, Нью-Йорк-Гейдельберг: Springer-Verlag, ISBN 978-0-387-90163-3, МР  0434929, Збл  0335.10001. См., в частности, главы 5 и 6, где представлен обзор базовой модульной арифметики.
• Маартен Буллинк «Модулярная арифметика до CF Gauss. Систематизация и обсуждение проблем остатка в Германии 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. ОСЛК  778356123.

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

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