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

В математике — модульная арифметика это система арифметики целых чисел , в которой числа «закручиваются» при достижении определенного значения, называемого модулем . Современный подход к модульной арифметике был развит Карлом Фридрихом Гауссом в его книге 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$ .
Теорема Лагранжа : если $p$ простое число и $f (x) = a 0 x д + ... + a d$ — многочлен с целыми коэффициентами такой, что $p$ не является делителем $a 0$ , то сравнение $f (x) \equiv 0 (mod p)$ имеет не более $d$ неконгруэнтных решений.
Примитивный корень по модулю $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$ , ^[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), Международный алгоритм шифрования данных (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]

См. также

Булево кольцо
Круговой буфер
Отдел (математика)
Конечное поле
Символ Лежандра
Модульное возведение в степень
По модулю (математика)
Мультипликативная группа целых чисел по модулю 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 .

Ссылки

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

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

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