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

Для хронометража на этих часах используется арифметика по модулю 12.

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

Известное использование модульной арифметики - 12-часовые часы , в которых день делится на два 12-часовых периода. Если сейчас 7:00, то через 8 часов будет 3:00. Простое сложение приведет к 7 + 8 = 15 , но часы «переключаются» каждые 12 часов. Поскольку число часов начинается после того, как оно достигает 12, это арифметическое значение по модулю 12. Согласно приведенному ниже определению, 15 сравнимо с 3 по модулю 12, поэтому «15:00» в 24-часовых часах отображается как «3:00». "в 12-часовом формате.

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

Для целого числа $n > 1$ , называемого модулем , два целых числа называются конгруэнтными по модулю $n$ , если $n$ является делителем их разности (т. Е. Если существует целое число $k$ такое, что $a - b = kn$ ).

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

{\ Displaystyle a \ Equiv b {\ pmod {n}}.}

Скобки означают, что $(mod n)$ применяется ко всему уравнению, а не только к правой части (здесь $b$ ). Это обозначение не следует путать с обозначением $b mod n$ (без скобок), которое относится к операции по модулю . В самом деле, $b mod n$ обозначает уникальное целое число $a$ такое, что $0 \leq a < n$ и (то есть остаток от деления на ^[1] ). ${\ Displaystyle а \ эквив б \; ({\ текст {мод}} \; п)}$ ${\ displaystyle b}$ ${\ displaystyle n}$

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

{\ displaystyle a = kn + b,}

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

{\ displaystyle a = pn + r,}

b=qn+r,

где $0 \leq r < n$ - общий остаток. Вычитая эти два выражения, мы восстанавливаем предыдущее соотношение:

a-b=kn,

положив $k = p - q .$

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

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

38\equiv 14{\pmod {12}}

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

Если $a 1 \equiv b 1 (mod n)$ и $a 2 \equiv b 2 (mod n),$ или если $a \equiv b (mod n),$ то:

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

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

Если $с \equiv d (мод φ (п)),$ где $φ$ является Функция Эйлера , то $гр$ $\equiv$ $д$ $( по$ $модулю$ $п$ $)$ -provided , что является взаимно просты с $п$ .

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

Если $a + k \equiv b + k (mod n)$ , где $k$ - любое целое число, то $a \equiv b (mod n)$
Если $ka \equiv kb (mod n)$ и $k$ взаимно просто с $n$ , то $a \equiv b (mod n)$
Если $ka \equiv kb (mod kn)$ , то $a \equiv b (mod n)$

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

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

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

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

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

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

a^{(p-1)/2}\equiv 1{\pmod {p}}.

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

Как и любое отношение конгруэнтности, сравнение по модулю $n$ является отношением эквивалентности , а класс эквивалентности целого числа $a$ , обозначенного $a n$ , - это множество ${\dots, a - 2 n, a - n, a, a + n, a + 2 п,\dots}$ . Этот набор, состоящий из всех целых чисел конгруэнтных , чтобы $в$ по модулю $п$ , называется класс конгруэнции , класс вычетов , или просто остатокцелого числа $a$ по модулю $n$ . Когда модуль $n$ известен из контекста, этот остаток также может быть обозначен $[a]$ .

Системы остатков [ править ]

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

Набор целых чисел ${0, 1, 2,\dots, 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 [ править ]

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

Набор определяется для n > 0 как:

\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\}.

(При $п = 0$ , не является пустым множеством , а, скорее, она изоморфна к , так как $0$ $= {$ $}$ .) $\mathbb {Z} /n\mathbb {Z}$ $\mathbb {Z}$

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

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

Для проверки правильности этого определения используются свойства, приведенные ранее.

Таким образом, становится коммутативным кольцом . Например, в кольце мы имеем $\mathbb {Z} /n\mathbb {Z}$ $\mathbb {Z} /24\mathbb {Z}$

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

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

Мы используем обозначения , потому что это фактор - кольцо из по идеалу , набор , содержащий все целые числа , делящиеся на $п$ , где является одноточечное множество ${0}$ . Таким образом , это поле , когда это максимальный идеал (то есть, когда $п$ простой). $\mathbb {Z} /n\mathbb {Z}$ $\mathbb {Z}$ $n\mathbb {Z}$ $0\mathbb {Z}$ $\mathbb {Z} /n\mathbb {Z}$ $n\mathbb {Z}$

Его также можно построить из группы только с помощью операции сложения. Класс вычетов $a$ $n$ - это смежный класс группы $a$ в фактор-группе , циклической группе . ^[8] $\mathbb {Z}$ $\mathbb {Z} /n\mathbb {Z}$

Вместо исключения особого случая $n = 0$ более полезно включить (который, как упоминалось ранее, изоморфен кольцу целых чисел). На самом деле, это включение полезно при обсуждении характеристики в виде кольца . $\mathbb {Z} /0\mathbb {Z}$ $\mathbb {Z}$

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

Мультипликативная подгруппа целых чисел по модулю п обозначается . Он состоит из (где a взаимно просто с n ), которые являются в точности классами, обладающими мультипликативным обратным. Это образует коммутативную группу относительно умножения с порядком . $(\mathbb {Z} /n\mathbb {Z} )^{\times }$ ${\overline {a}}_{n}$ $\varphi (n)$

Приложения [ править ]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Этот раздел, возможно, содержит оригинальные исследования . Пожалуйста, улучшите его , проверив сделанные утверждения и добавив встроенные цитаты . Заявления, содержащие только оригинальные исследования, следует удалить. ( Май 2020 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения )

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

Алгоритмический способ вычисления : ^[11] $a\cdot b{\pmod {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 ;  int  i ;  если  ( a  > =  m )  a  % =  m ;  если  ( b  > =  m )  b  % =  m ;  для  ( i  =  0 ;  i  <  64 ;  ++ i )  {  d  =  ( d  >  mp2 )  ?  ( d  << 1 )  -  m  :  d  <<  1 ;  если  ( a  &  0x8000000000000000ULL )  d  + =  b ;  если  ( d  > =  m )  d  - =  m ;  а  << =  1 ;  }  return  d ; }

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

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

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

Алгоритмический способ вычисления : $a^{b}{\pmod {m}}$

uint64_t  pow_mod ( uint64_t  a ,  uint64_t  b ,  uint64_t  m ) {  uint64_t  r  =  m == 1 ? 0 : 1 ;  while  ( b  >  0 )  {  если  ( b  &  1 )  r  =  mul_mod ( r ,  a ,  m );  b  =  b  >>  1 ;  а  =  mul_mod (а ,  а ,  м );  }  return  r ; }

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

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

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

Заметки [ править ]

^ a b «Исчерпывающий список символов алгебры» . Математическое хранилище . 2020-03-25 . Проверено 12 августа 2020 .
^ Вайсштейн, Эрик В. «Модульная арифметика» . mathworld.wolfram.com . Проверено 12 августа 2020 .
^ Pettofrezzo & Byrkit (1970 , стр. 90)
^ Длинный (1972 , стр.78)
^ Длинный (1972 , стр. 85)
^ Это кольцо , как показано ниже.
^ "2.3: Целые числа по модулю n" . Математика LibreTexts . 2013-11-16 . Проверено 12 августа 2020 .
^ Сенгадир Т., Дискретная математика и комбинаторика , с. 293, в Google Книгах
^ "Гипотеза Эйлера о сумме степеней" . rosettacode.org . Проверено 11 ноября 2020 .
^ Garey, MR; Джонсон, Д.С. (1979). Компьютеры и неразрешимость, руководство по теории NP-полноты . WH Freeman. ISBN 0716710447.
^ В этом коде используется буквальная нотация C для длинных длинных шестнадцатеричных чисел без знака, которые заканчиваются наULL. См. Также раздел 6.4.4 спецификации языка n1570 .

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

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

Внешние ссылки [ править ]

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

[:0-1] «Исчерпывающий список символов алгебры» . Математическое хранилище . 2020-03-25 . Проверено 12 августа 2020 .

[2] Вайсштейн, Эрик В. «Модульная арифметика» . mathworld.wolfram.com . Проверено 12 августа 2020 .

[3] Pettofrezzo & Byrkit (1970 , стр. 90)

[4] Длинный (1972 , стр.78)

[5] Длинный (1972 , стр. 85)

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

[7] "2.3: Целые числа по модулю n" . Математика LibreTexts . 2013-11-16 . Проверено 12 августа 2020 .

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

[9] "Гипотеза Эйлера о сумме степеней" . rosettacode.org . Проверено 11 ноября 2020 .

[10] Garey, MR; Джонсон, Д.С. (1979). Компьютеры и неразрешимость, руководство по теории NP-полноты . WH Freeman. ISBN 0716710447.

[11] ^ В этом коде используется буквальная нотация C для длинных длинных шестнадцатеричных чисел без знака, которые заканчиваются наULL. См. Также раздел 6.4.4 спецификации языка n1570 .

[1]

vтеТеория чисел
Поля	Алгебраическая теория чисел Аналитическая теория чисел Геометрическая теория чисел Вычислительная теория чисел Трансцендентальная теория чисел Диофантова геометрия Арифметическая комбинаторика Арифметическая геометрия Арифметическая топология Арифметическая динамика
Ключевые идеи	Числа Натуральные числа простые числа Рациональное число Иррациональные числа Алгебраические числа Трансцендентные числа p-адические числа Арифметика Модульная арифметика Арифметические функции
Продвинутые концепции	Квадратичные формы Модульные формы L-функции Диофантовы уравнения Диофантово приближение Непрерывные дроби
Категория Список тем Список развлекательных тем Викибук Wikversity