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

В математике — модульная арифметика это система арифметики целых чисел , в которой числа «закручиваются» при достижении определенного значения, называемого модулем . Современный подход к модульной арифметике был развит Карлом Фридрихом Гауссом в его книге 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 \geq 1$ , называемое модулем , два целых числа $a$ и $b$ называются конгруэнтными по модулю $m$ , если $m$ является делителем их разности; то есть, если существует целое число $k$ такое, что

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

.

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

а \equiv б (мод м)

.

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

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

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

а = км + б

,

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

а = pm + r

,

б = дм + р

,

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

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

Примеры [ править ]

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

38 \equiv 14 (мод. 12)

потому что разница составляет $38 - 14 = 24 = 2 \times 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 \equiv a (mod m)$
Симметрия: $a \equiv b (mod m),$ если $b \equiv a (mod m)$ .
Транзитивность: если $a \equiv b (mod m)$ и $b \equiv c (mod m)$ , то $a \equiv c (mod m).$

Если $a 1 \equiv b 1 (mod m)$ и $a 2 \equiv b 2 (mod m)$ или если $a \equiv b (mod m)$ , то: ^[1]

$a + k \equiv b + k (mod m)$ для любого целого числа $k$ (совместимость с переводом)
$ka \equiv kb (mod m)$ для любого целого числа $k$ (совместимость с масштабированием)
$ka \equiv kb (mod km)$ для любого целого $k$
$a 1 + a 2 \equiv b 1 + b 2 (mod m)$ (совместимость со сложением)
$a 1 - a 2 \equiv b 1 - b 2 (mod m)$ (совместимость с вычитанием)
$a 1 a 2 \equiv b 1 b 2 (mod m)$ (совместимость с умножением)
$а к \equiv б к (mod m)$ для любого неотрицательного целого числа $k$ (совместимость с возведением в степень)
$p (a) \equiv p (b) (mod m)$ для любого многочлена $p (x)$ с целыми коэффициентами (совместимость с полиномиальной оценкой)

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

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

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

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

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

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

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

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

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

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

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

Маленькая теорема Ферма : если $p$ простое и не делит $a$ , то $a р -1 \equiv 1 (против п)$ .
Теорема Эйлера : если $a$ и $m$ взаимно просты, то $a φ (м) \equiv 1 (mod m)$ , где $φ$ — функция тотента Эйлера .
Простое следствие маленькой теоремы Ферма состоит в том, что если $p$ простое, то $a -1 \equiv а р -2 (mod p)$ является мультипликативным обратным $0 < a < p$ . В более общем смысле, согласно теореме Эйлера, если $a$ и $m$ взаимно просты, то $a -1 \equiv а φ (м)-1 (мод. м)$ .
Другое простое следствие состоит в том, что если $a \equiv b (mod φ (m))$ , где $φ$ — тотент-функция Эйлера, то $k а \equiv к б (mod m)$ при условии, что $k$ взаимно просто с $m$ .
Теорема Вильсона : $p$ простое тогда и только тогда, когда $(p - 1)! \equiv -1 (мод п)$ .
Китайская теорема об остатках : для любых $a$ , $b$ и взаимно простых $m$ , $n$ существует единственный $x (mod mn)$ такой, что $x \equiv a (mod m)$ и $x \equiv b (mod n)$ . В самом деле, $x \equiv bm n -1 м + м -1 n (mod mn)$ , где $m n -1$ является обратным к $m$ по модулю $n$ и $n m -1$ является обратным $n$ по модулю $m$ .
Теорема Лагранжа : сравнение $f (x) \equiv 0 (mod p)$ , где $p$ — простое число, и $f (x) = a 0 x м + ... + a m$ — многочлен с целыми коэффициентами такой, что $a 0 \neq 0 (mod p)$ имеет не более $m$ корней.
Примитивный корень по модулю $m$ : число $g$ является примитивным корнем по модулю $m$ , если для каждого целого числа, $взаимно$ простого с $m$ , существует целое число $k$ такое, что $g к \equiv а (мод м)$ . Примитивный корень по модулю $m$ существует тогда и только тогда, когда $m$ равно $2, 4, p к$ или $2 п. к$ , где $p$ — нечетное простое число, а $k$ — целое положительное число. Если примитивный корень по модулю $m$ существует, то таких примитивных корней ровно $φ (φ (m))$ , где $φ$ — тотент-функция Эйлера.
Квадратичный вычет : Целое число $a$ является квадратичным вычетом по модулю $m$ , если существует целое число $x$ такое, что $x 2 \equiv а (мод м)$ . Критерий Эйлера утверждает, что если $p$ — нечетное простое число и $a$ не кратно $p$ , то $a$ — квадратичный вычет по модулю $p$ тогда и только тогда, когда
$а (п -1)/2 \equiv 1 (против п)$ .

Классы конгруэнтности [ править ]

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

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

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

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

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

Остаточные системы [ править ]

Каждый класс остатков по модулю $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$ называется кольцом целых чисел по модулю $m$ , ^[6] и обозначается ${\textstyle \mathbb {Z} /m\mathbb {Z} }$ , $\mathbb {Z} /m$ , или $\mathbb {Z} _{m}$ . ^[7] Обозначения $\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}$ , поскольку $а 0 = {а}$ .

Сложение, вычитание и умножение определены на $\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}$ для некоторых $м$ . ^[8]

Кольцо целых чисел по модулю $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 микрокомпьютере с использованием всего лишь одной четверти целочисленной точности, используемой суперкомпьютером 6600, CDC чтобы опровергнуть ее двумя десятилетиями ранее. через поиск методом перебора . ^[9]

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

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

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

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

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

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

Вычислительная сложность [ править ]

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

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

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

Пример реализации [ править ]

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

Алгоритм вычисления $a \cdot 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;
    int i;
    if (a >= m) a %= m;
    if (b >= m) b %= m;
    for (i = 0; i < 64; ++i) {
        d = (d > mp2) ? (d << 1) - m : d << 1;
        if (a & 0x8000000000000000ULL) d += b;
        if (d >= m) d -= m;
        a <<= 1;
    }
    return d;
}

В компьютерных архитектурах, где расширенный формат точности доступен с минимум 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;
    if (a >= m) a %= m;
    if (b >= m) b %= m;
    x = a;
    c = x * b / m;
    r = (int64_t)(a * b - c * m) % (int64_t)m;
    return r < 0 ? r + m : r;
}

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

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

uint64_t pow_mod(uint64_t a, uint64_t b, uint64_t m) {
    uint64_t r = m == 1 ? 0 : 1;
    while (b > 0) {
        if (b & 1) r = mul_mod(r, a, m);
        b = b >> 1;
        a = mul_mod(a, a, m);
    }
    return r;
}

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

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

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

Примечания [ править ]

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

Ссылки [ править ]

Джон Л. Берггрен. «модульная арифметика» . Британская энциклопедия .
Апостол, Том М. (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
Модульная арифметика и шаблоны сложения и таблицы умножения

[1] Шандор Лехочки; Ричард Руски (2006). Дэвид Патрик (ред.). Искусство решения проблем . Том. 1 (7-е изд.). Компания «АоПС Инкорпорейтед». п. 44. ИСБН 0977304566 .

[2] Вайсштейн, Эрик В. «Модульная арифметика» . Вольфрам Математический мир . Архивировано из оригинала 14 июля 2023 г. Проверено 12 августа 2020 г.

[3] Петтофреззо и Биркит (1970 , стр. 90)

[4] Лонг (1972 , стр. 78)

[5] Лонг (1972 , стр. 85)

[6] Это кольцо , как показано ниже.

[7] «2.3: Целые числа по модулю n» . Математика LibreTexts . 16 ноября 2013 г. Архивировано из оригинала 19 апреля 2021 г. Проверено 12 августа 2020 г.

[8] Сенгадир Т., Дискретная математика и комбинаторика , с. 293, в Google Книгах.

[9] «Гипотеза Эйлера о сумме степеней» . Rosettacode.org . Архивировано из оригинала 26 марта 2023 г. Проверено 11 ноября 2020 г.

[10] Гэри, MR; Джонсон, DS (1979). Компьютеры и трудноразрешимые проблемы. Руководство по теории NP-полноты . У. Х. Фриман. ISBN 0716710447 .

[11] Этот код использует литеральную нотацию C для беззнаковых длинных шестнадцатеричных чисел, которые заканчиваются на ULL. См. также раздел 6.4.4 спецификации языка n1570. Архивировано 29 марта 2018 г. на Wayback Machine .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

v т и Теория чисел
Поля	Алгебраическая теория чисел ( теория полей классов , неабелева теория полей классов , теория Ивасавы , теория Ивасавы–Тейта , теория Куммера ) Аналитическая теория чисел ( аналитическая теория L-функций , вероятностная теория чисел , теория решета ) Геометрическая теория чисел Вычислительная теория чисел Трансцендентная теория чисел Диофантова геометрия ( теория Аракелова , теория Ходжа–Аракелова ) Арифметическая комбинаторика ( аддитивная теория чисел ) Арифметическая геометрия ( анабелева геометрия , P-адическая теория Ходжа ) Арифметическая топология Арифметическая динамика
Ключевые понятия	Числа 0 Натуральные числа Единство Простые числа Составные числа Рациональные числа Иррациональные числа Алгебраические числа Трансцендентные числа P-адические числа ( P-адический анализ ) Арифметика Модульная арифметика Китайская теорема об остатках Арифметические функции
Расширенные концепции	Квадратичные формы Модульные формы L-функции Диофантовы уравнения Диофантово приближение Непрерывные дроби
Категория Список тем Список развлекательных тем Викибук Викиверситет