простое число

Группы от двух до двенадцати точек, показывающие, что составные числа точек (4, 6, 8, 9, 10 и 12) можно расположить в прямоугольники, а простые числа — нет. — Составные числа можно расположить в прямоугольники , а простые числа — нет.

Простое число (или простое число ) — это натуральное число больше 1, которое не является произведением двух меньших натуральных чисел. Натуральное число больше 1, которое не является простым, называется составным числом . Например, число 5 является простым, потому что единственные способы записи его в виде произведения, 1 × 5 или 5 × 1 , включают в себя само число 5. Однако число 4 является составным, поскольку оно представляет собой произведение (2 × 2), в котором оба числа меньше 4. Простые числа занимают центральное место в теории чисел из-за фундаментальной теоремы арифметики : каждое натуральное число, большее 1, либо само является простым, либо можно факторизовать как произведение простых чисел, уникальное в пределах их порядка.

Свойство быть простым называется простотой . Простой, но медленный метод проверки простоты заданного числа $n$ , называемое пробным разделением , проверяет, $n$ кратно любому целому числу от 2 до ${\sqrt {n}}$ . Более быстрые алгоритмы включают тест на простоту Миллера-Рабина , который работает быстро, но имеет небольшую вероятность ошибки, и тест на простоту AKS , который всегда дает правильный ответ за полиномиальное время , но слишком медленный, чтобы быть практичным. Особенно быстрые методы доступны для чисел специальных форм, например чисел Мерсенна . По состоянию на декабрь 2018 г. ^[update] Самое большое известное простое число — простое число Мерсенна с 24 862 048 десятичными цифрами . ^[1]

Простых чисел бесконечно много , как показал Евклид около 300 г. до н.э. Ни одна известная простая формула не отделяет простые числа от составных чисел. Однако распределение простых чисел внутри натуральных чисел в целом можно смоделировать статистически. Первым результатом в этом направлении является теорема о простых числах , доказанная в конце XIX века, которая гласит, что вероятность того , что случайно выбранное большое число окажется простым, обратно пропорциональна количеству его цифр, то есть его логарифму .

Некоторые исторические вопросы, касающиеся простых чисел, до сих пор не решены. К ним относятся гипотеза Гольдбаха о том, что каждое четное целое число, большее 2, можно выразить как сумму двух простых чисел, и гипотеза о простых числах-близнецах , согласно которой существует бесконечно много пар простых чисел, отличающихся на два. Такие вопросы стимулировали развитие различных разделов теории чисел, сосредоточив внимание на аналитических или алгебраических аспектах чисел. Простые числа используются в нескольких процедурах в информационных технологиях , таких как криптография с открытым ключом , которая основана на сложности разложения больших чисел на их простые множители. В абстрактной алгебре объекты, которые ведут себя обобщенно, как простые числа, включают простые элементы и простые идеалы .

Определение и примеры

Натуральное число (1, 2, 3, 4, 5, 6 и т. д.) называется простым числом (или простым числом ), если оно больше 1 и не может быть записано в виде произведения двух меньших натуральных чисел. Числа больше 1, которые не являются простыми, называются составными числами . ^[2] Другими словами, $n$ является простым, если $n$ предметы не могут быть разделены на более мелкие группы одинакового размера, состоящие из более чем одного предмета, ^[3] или если невозможно организовать $n$ точек в прямоугольную сетку шириной более одной точки и высотой более одной точки. ^[4] Например, среди чисел от 1 до 6 числа 2, 3 и 5 являются простыми числами. ^[5]так как не существует других чисел, делящих их поровну (без остатка). 1 не является простым, поскольку это специально исключено из определения. 4 = 2 × 2 и 6 = 2 × 3 являются составными.

Делители числа натурального $n$ это натуральные числа, которые делят $n$ равномерно. Каждое натуральное число имеет в качестве делителя и 1, и само себя. Если у него есть какой-либо другой делитель, он не может быть простым. Это приводит к эквивалентному определению простых чисел: это числа, имеющие ровно два положительных делителя . Эти двое — 1 и само число. Поскольку число 1 само по себе имеет только один делитель, по этому определению оно не является простым. ^[6] Еще один способ выразить то же самое состоит в том, что число $n$ является простым, если оно больше единицы и если ни одно из чисел $2,3,\dots ,n-1$ делит $n$ равномерно. ^[7]

Первые 25 простых чисел (все простые числа меньше 100): ^[8]

2 , 3 , 5 , 7 , 11 , 13 , 17 , 19 , 23 , 29 , 31 , 37 , 41 , 43 , 47 , 53 , 59 , 61 , 67 , 71 , 73 , 79 , 83 , 89 , 97 ( последовательность A000040 в OEIS ).

Нет четного числа $n$ Число больше 2 является простым, поскольку любое такое число можно выразить как произведение $2\times n/2$ . Следовательно, каждое простое число, кроме 2, является нечетным числом и называется нечетным простым числом . ^[9] Аналогично, при записи в обычной десятичной системе все простые числа больше 5 оканчиваются на 1, 3, 7 или 9. Все числа, оканчивающиеся другими цифрами, являются составными: десятичные числа, оканчивающиеся на 0, 2, 4, 6. , или 8, являются четными, а десятичные числа, оканчивающиеся на 0 или 5, делятся на 5. ^[10]

Множество всех простых чисел иногда обозначается через $\mathbf {P}$ ( жирный шрифт с заглавной буквы П) ^[11] или через $\mathbb {P}$ ( на доске жирная заглавная буква П). ^[12]

История

, Математический папирус Ринда датируемый примерно 1550 годом до нашей эры, содержит египетские дроби различных форм для простых и составных чисел. ^[13]Однако самые ранние сохранившиеся записи об изучении простых чисел исходят от древнегреческих математиков , которые называли их протос арифмос ( πρῶτος ἀριθμὸς ). ( Евклида «Начала» ок. 300 г. до н. э.) доказывают бесконечность простых чисел и фундаментальную теорему арифметики , а также показывают, как построить совершенное число из простого числа Мерсенна . ^[14] Другое греческое изобретение, «Решето Эратосфена» , до сих пор используется для составления списков простых чисел. ^[15]^[16]

Около 1000 года нашей эры исламский математик Ибн аль-Хайсам (Альхазен) нашел теорему Вильсона , характеризующую простые числа как числа. $n$ которые поровну делят $(n-1)!+1$ . Он также предположил, что все даже совершенные числа происходят из конструкции Евклида с использованием простых чисел Мерсенна, но не смог это доказать. ^[17] Другой исламский математик, Ибн аль-Банна аль-Марракуши , заметил, что решето Эратосфена можно ускорить, рассматривая только простые делители до квадратного корня из верхнего предела. ^[16] Фибоначчи принёс инновации исламской математики в Европу. Его книга Liber Abaci (1202 г.) была первой, в которой описано пробное деление для проверки простоты, снова с использованием делителей только до квадратного корня. ^[16]

В 1640 году Пьер де Ферма сформулировал (без доказательства) малую теорему Ферма (позже доказанную Лейбницем и Эйлером ). ^[18] Ферма также исследовал простоту чисел Ферма. $2^{2^{n}}+1$ , ^[19] и Марин Мерсенн изучали простые числа Мерсенна , простые числа вида $2^{p}-1$ с $p$ сам по себе является праймом. ^[20] Кристиан Гольдбах в письме Эйлеру в 1742 году сформулировал гипотезу Гольдбаха о том, что каждое четное число является суммой двух простых чисел. ^[21] Эйлер доказал гипотезу Альхазена (теперь теорему Евклида-Эйлера ) о том, что все четные совершенные числа могут быть построены из простых чисел Мерсенна. ^[14] Он представил методы математического анализа в этой области в своих доказательствах бесконечности простых чисел и расходимости суммы обратных простых чисел. ${\tfrac {1}{2}}+{\tfrac {1}{3}}+{\tfrac {1}{5}}+{\tfrac {1}{7}}+{\tfrac {1}{11}}+\cdots$ . ^[22] В начале XIX века Лежандр и Гаусс предположили, что $x$ стремится к бесконечности, число простых чисел до $x$ асимптотически $x/\log x$ , где $\log x$ это логарифм натуральный $x$ . Более слабым следствием такой высокой плотности простых чисел был постулат Бертрана о том, что для каждого $n>1$ есть простое число между $n$ и $2n$ , доказанный в 1852 году Пафнутием Чебышевым . ^[23]Идеи Бернхарда Римана в его статье 1859 года о дзета-функции наметили схему доказательства гипотезы Лежандра и Гаусса. Хотя тесно связанная с ней гипотеза Римана остается недоказанной, схема Римана была завершена в 1896 году Адамаром и де ла Валле Пуссеном , и результат теперь известен как теорема о простых числах . ^[24] Другим важным результатом XIX века была теорема Дирихле об арифметических прогрессиях , согласно которой некоторые арифметические прогрессии содержат бесконечное количество простых чисел. ^[25]

Многие математики работали над тестами на простоту чисел, больших, чем те, для которых практически применимо пробное деление. Методы, ограниченные конкретными числовыми формами, включают тест Пепена для чисел Ферма (1877 г.), ^[26] Теорема Прота (ок. 1878 г.), ^[27] тест простоты Лукаса -Лемера (возник в 1856 г.) и обобщенный тест простоты Люка . ^[16]

С 1951 года все самые большие известные простые числа были найдены с помощью этих тестов на компьютерах . ^[а] Поиск все более крупных простых чисел вызвал интерес за пределами математических кругов, благодаря Великому поиску простых чисел Мерсенна в Интернете и другим проектам распределенных вычислений . ^[8]^[29] Идея о том, что простые числа имеют мало применений за пределами чистой математики. ^[б] была разрушена в 1970-х годах, когда были изобретены криптография с открытым ключом и криптосистема RSA , в основе которых лежали простые числа. ^[32]

Возросшая практическая значимость компьютеризированного тестирования простоты и факторизации привела к разработке улучшенных методов, способных обрабатывать большое количество неограниченных форм. ^[15]^[33]^[34] Математическая теория простых чисел также продвинулась вперед благодаря теореме Грина-Тао (2004 г.) о том, что существуют сколь угодно длинные арифметические прогрессии простых чисел, и доказательству Итан Чжана в 2013 г., что существует бесконечно много простых пробелов ограниченного размера. ^[35]

Первичность одного

Большинство ранних греков даже не считали 1 числом. ^[36]^[37]поэтому они не могли принять во внимание его первичность. Некоторые ученые греческой и более поздней римской традиции, в том числе Никомах , Ямвлих , Боэций и Кассиодор , также считали простые числа подразделением нечетных чисел, поэтому они также не считали 2 простым. Однако Евклид и большинство других греческих математиков считали 2 простым числом. Средневековые исламские математики во многом следовали грекам, считая, что единица не является числом. ^[36] К Средним векам и эпохе Возрождения математики начали рассматривать 1 как число, а некоторые из них включали его в качестве первого простого числа. ^[38]В середине 18 века Кристиан Гольдбах назвал 1 главным числом в своей переписке с Леонардом Эйлером ; однако сам Эйлер не считал 1 простым числом. ^[39] В XIX веке многие математики все еще считали единицу простым числом. ^[40] а списки простых чисел, включающие 1, продолжали публиковаться вплоть до 1956 года. ^[41]^[42]

Если бы определение простого числа было изменено, чтобы называть 1 простым, многие утверждения, связанные с простыми числами, пришлось бы переформулировать более неудобно. Например, фундаментальную теорему арифметики необходимо будет перефразировать в терминах факторизации в простые числа, большие 1, поскольку каждое число будет иметь несколько факторизаций с любым количеством копий 1. ^[40] Точно так же решето Эратосфена не работало бы правильно, если бы оно обрабатывало 1 как простое число, поскольку оно исключало бы все числа, кратные 1 (то есть все остальные числа), и выводило бы только одно число 1. ^[42] Некоторые другие, более технические свойства простых чисел также не справедливы для числа 1: например, формулы для функции тотента Эйлера или для функции суммы делителей для простых чисел отличаются от формул для 1. ^[43] К началу 20-го века математики начали соглашаться с тем, что единицу следует относить не к простому числу, а к отдельной категории « единицы ». ^[40]

Элементарные свойства

Уникальная факторизация

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

{\begin{aligned}34866&=2\times 3\times 3\times 13\times 149\\&=2\times 3^{2}\times 13\times 149.\end{aligned}}

Члены произведения называются простыми факторами . Один и тот же простой множитель может встречаться более одного раза; в этом примере есть две копии простого множителя $3.$ Когда простое число встречается несколько раз, возведение в степень можно использовать для группировки нескольких копий одного и того же простого числа: например, во втором способе записи произведения выше: $3^{2}$ обозначает квадрат или вторую степень $3.$

Центральное значение простых чисел для теории чисел и математики в целом вытекает из фундаментальной теоремы арифметики . ^[44]Эта теорема утверждает, что каждое целое число больше 1 можно записать в виде произведения одного или нескольких простых чисел. В более строгом смысле, это произведение уникально в том смысле, что любые две факторизации одного и того же числа будут иметь одинаковое количество копий одних и тех же простых чисел, хотя их порядок может различаться. ^[45]Итак, хотя существует много разных способов найти факторизацию с использованием алгоритма факторизации целых чисел , все они должны давать один и тот же результат. Таким образом, простые числа можно считать «основными строительными блоками» натуральных чисел. ^[46]

Некоторые доказательства единственности простых факторизаций основаны на лемме Евклида : если $p$ является простым числом и $p$ делит продукт $ab$ целых чисел $a$ и $b,$ затем $p$ делит $a$ или $p$ делит $b$ (или оба). ^[47] И наоборот, если число $p$ обладает тем свойством, что при делении продукта он всегда делит хотя бы один фактор продукта, то $p$ должен быть простым. ^[48]

Бесконечность

Существует бесконечно много простых чисел. Другой способ сказать это состоит в том, что последовательность

2, 3, 5, 7, 11, 13, ...

простых чисел никогда не заканчивается. Это утверждение называется теоремой Евклида в честь древнегреческого математика Евклида , поскольку ему приписывается первое известное доказательство этого утверждения. Известно еще множество доказательств бесконечности простых чисел, включая аналитическое доказательство Эйлера , Гольдбаха, доказательство основанное на числах Ферма , ^[49] Доказательство Фюрстенберга с использованием общей топологии . ^[50] и элегантное доказательство Куммера . ^[51]

Доказательство Евклида ^[52]показывает, что любой конечный список простых чисел является неполным. Основная идея состоит в том, чтобы перемножить простые числа в любом заданном списке и сложить $1.$ Если список состоит из простых чисел $p_{1},p_{2},\ldots ,p_{n},$ это дает номер

N=1+p_{1}\cdot p_{2}\cdots p_{n}.

По основной теореме $N$ имеет простую факторизацию

N=p'_{1}\cdot p'_{2}\cdots p'_{m}

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

Числа, образованные прибавлением единицы к произведению наименьших простых чисел, называются числами Евклида . ^[53] Первые пять из них простые, а шестой,

1+{\big (}2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13{\big )}=30031=59\cdot 509,

является составным числом.

Формулы для простых чисел

Не существует известной эффективной формулы для простых чисел. Например, не существует непостоянного полинома , даже от нескольких переменных, который принимает только простые значения. ^[54]Однако существует множество выражений, которые кодируют все простые числа или только простые числа. Одна из возможных формул основана на теореме Вильсона и генерирует число 2 много раз, а все остальные простые числа — ровно один раз. ^[55]Существует также система диофантовых уравнений с девятью переменными и одним параметром, обладающая следующим свойством: параметр является простым тогда и только тогда, когда полученная система уравнений имеет решение над натуральными числами. Это можно использовать для получения единственной формулы, у которой все положительные значения являются простыми. ^[54]

Другие примеры формул, порождающих простые числа, взяты из теоремы Миллса и теоремы Райта . Они утверждают, что существуют реальные константы $A>1$ и $\mu$ такой, что

\left\lfloor A^{3^{n}}\right\rfloor {\text{ and }}\left\lfloor 2^{\cdots ^{2^{2^{\mu }}}}\right\rfloor

являются простыми для любого натурального числа $n$ в первой формуле и любое количество показателей степени во второй формуле. ^[56] Здесь $\lfloor {}\cdot {}\rfloor$ представляет функцию пола , наибольшее целое число, меньшее или равное рассматриваемому числу. Однако они бесполезны для генерации простых чисел, поскольку сначала необходимо сгенерировать простые числа, чтобы вычислить значения $A$ или $\mu .$ ^[54]

Открытые вопросы

Было высказано множество гипотез, касающихся простых чисел. Многие из этих гипотез, часто имея элементарную формулировку, десятилетиями выдерживали проверку: все четыре проблемы Ландау 1912 года до сих пор не решены. ^[57] Одна из них — гипотеза Гольдбаха , утверждающая, что каждое четное целое число $n$ число больше 2 можно записать в виде суммы двух простых чисел. ^[58] По состоянию на 2014 год ^[update], эта гипотеза проверена для всех чисел до $n=4\cdot 10^{18}.$ ^[59] Были доказаны и более слабые утверждения, чем это, например, теорема Виноградова гласит, что каждое достаточно большое нечетное целое число можно записать в виде суммы трех простых чисел. ^[60] Теорема Чена гласит, что каждое достаточно большое четное число можно выразить как сумму простого и полупростого числа (произведение двух простых чисел). ^[61] Кроме того, любое четное целое число больше 10 можно записать как сумму шести простых чисел. ^[62] Раздел теории чисел, изучающий подобные вопросы, называется аддитивной теорией чисел . ^[63]

Другой тип проблем касается пробелов в простых числах , различий между последовательными простыми числами. В существовании сколь угодно больших простых пробелов можно убедиться, заметив, что последовательность $n!+2,n!+3,\dots ,n!+n$ состоит из $n-1$ составные числа для любого натурального числа $n.$ ^[64] Однако большие разрывы между простыми числами происходят гораздо раньше, чем показывает этот аргумент. ^[65] Например, первый пробел длиной 8 находится между простыми числами 89 и 97, ^[66] намного меньше, чем $8!=40320.$ Предполагается, что существует бесконечно много простых чисел-близнецов , пар простых чисел с разницей 2; это гипотеза о простых числах-близнецах . В более общем плане гипотеза Полиньяка утверждает, что для каждого положительного целого числа $k,$ существует бесконечно много пар последовательных простых чисел, отличающихся друг от друга на $2k.$ ^[67] Гипотеза Андрики , ^[67] Гипотеза Брокара , ^[68] Гипотеза Лежандра , ^[69] и гипотеза Оппермана ^[68] все предполагают, что самые большие промежутки между простыми числами из $1$ к $n$ должно быть не более приблизительно ${\sqrt {n}},$ результат, который, как известно, следует из гипотезы Римана, в то время как гораздо более сильная гипотеза Крамера устанавливает наибольший размер разрыва на уровне $O((\log n)^{2}).$ ^[67] Пробелы простых чисел можно обобщить до простых чисел. $k$ -кортежи — закономерности различий между более чем двумя простыми числами. Их бесконечность и плотность являются предметом первой гипотезы Харди-Литтлвуда , которая может быть мотивирована эвристикой, согласно которой простые числа ведут себя аналогично случайной последовательности чисел с плотностью, заданной теоремой о простых числах. ^[70]

Аналитические свойства

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

Эта область исследований началась с Леонарда Эйлера и его первого крупного результата — решения Базельской проблемы . Задача заключалась в определении значения бесконечной суммы. $1+{\tfrac {1}{4}}+{\tfrac {1}{9}}+{\tfrac {1}{16}}+\dots ,$ что сегодня можно признать ценностью $\zeta (2)$ Римана дзета-функции . Эта функция тесно связана с простыми числами и с одной из наиболее значительных нерешённых проблем математики — гипотезой Римана . Эйлер показал, что $\zeta (2)=\pi ^{2}/6$ . ^[71] обратное этому числу, $6/\pi ^{2}$ , — это предельная вероятность того, что два случайных числа, равномерно выбранных из большого диапазона, являются относительно простыми (не имеют общих факторов). ^[72]

Распределение простых чисел в целом, например вопрос, сколько простых чисел меньше заданного большого порога, описывается теоремой о простых числах , но эффективной формулы для этого не существует. $n$ -е простое число известно. Теорема Дирихле об арифметических прогрессиях в своей основной форме утверждает, что линейные многочлены

p(n)=a+bn

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

Аналитическое доказательство теоремы Евклида

Доказательство Эйлера о том, что простых чисел бесконечно много, рассматривает суммы обратных простых чисел:

{\frac {1}{2}}+{\frac {1}{3}}+{\frac {1}{5}}+{\frac {1}{7}}+\cdots +{\frac {1}{p}}.

Эйлер показал, что для любого произвольного действительного числа $x$ , существует простое число $p$ для которого эта сумма больше $x$ . ^[73] Это показывает, что существует бесконечно много простых чисел, потому что, если бы простых чисел было конечно, сумма достигла бы своего максимального значения в самом большом простом, а не превысила бы каждый раз. $x$ . Скорость роста этой суммы точнее описывается второй теоремой Мертенса . ^[74] Для сравнения, сумма

{\frac {1}{1^{2}}}+{\frac {1}{2^{2}}}+{\frac {1}{3^{2}}}+\cdots +{\frac {1}{n^{2}}}

не растет до бесконечности, так как $n$ стремится к бесконечности (см. Базельскую задачу ). В этом смысле простые числа встречаются чаще, чем квадраты натуральных чисел. хотя оба множества бесконечны. ^[75] Теорема Брюна утверждает, что сумма обратных чисел-близнецов ,

\left({{\frac {1}{3}}+{\frac {1}{5}}}\right)+\left({{\frac {1}{5}}+{\frac {1}{7}}}\right)+\left({{\frac {1}{11}}+{\frac {1}{13}}}\right)+\cdots ,

конечно. Из-за теоремы Брюна невозможно использовать метод Эйлера для решения гипотезы о простых числах-близнецах , согласно которой существует бесконечно много простых чисел-близнецов. ^[75]

Количество простых чисел ниже заданной границы

чисел Функция подсчета простых $\pi (n)$ определяется как количество простых чисел, не превышающее $n$ . ^[76] Например, $\pi (11)=5$ , поскольку существует пять простых чисел, меньших или равных 11. Такие методы, как алгоритм Мейселя – Лемера, могут вычислить точные значения $\pi (n)$ быстрее, чем можно было бы перечислить каждое простое число до $n$ . ^[77] Теорема о простых числах утверждает, что $\pi (n)$ асимптотически $n/\log n$ , который обозначается как

\pi (n)\sim {\frac {n}{\log n}},

и означает, что соотношение $\pi (n)$ правая дробь приближается к 1 как $n$ растет до бесконечности. ^[78] Это означает, что вероятность того, что случайно выбранное число меньше $n$ является простым (приблизительно) обратно пропорционально количеству цифр в $n$ . ^[79] Это также подразумевает, что $n$ простое число пропорционально $n\log n$ ^[80] и, следовательно, средний размер простого разрыва пропорционален $\log n$ . ^[65] Более точная оценка для $\pi (n)$ задается смещенным логарифмическим интегралом ^[78]

\pi (n)\sim \operatorname {Li} (n)=\int _{2}^{n}{\frac {dt}{\log t}}.

Арифметические прогрессии

Арифметическая прогрессия — это конечная или бесконечная последовательность чисел, в которой все последовательные числа в этой последовательности имеют одинаковую разницу. ^[81] Эта разница называется модулем прогрессии. ^[82] Например,

3, 12, 21, 30, 39, ...,

— бесконечная арифметическая прогрессия с модулем 9. В арифметической прогрессии все числа имеют одинаковый остаток при делении на модуль; в этом примере остаток равен 3. Поскольку и модуль 9, и остаток 3 кратны 3, то же самое относится и к каждому элементу последовательности. Следовательно, эта прогрессия содержит только одно простое число — саму 3. В общем, бесконечная прогрессия

a,a+q,a+2q,a+3q,\dots

может иметь более одного простого числа только тогда, когда его остаток $a$ и модуль $q$ являются относительно простыми. Если они относительно простые, теорема Дирихле об арифметических прогрессиях утверждает, что прогрессия содержит бесконечно много простых чисел. ^[83]

Простые числа в арифметической прогрессии мод 9

Простые числа в арифметической прогрессии по модулю 9. В каждом ряду тонкой горизонтальной полосы показана одна из девяти возможных прогрессий по модулю 9, простые числа отмечены красным. Прогрессии чисел 0, 3 или 6 по модулю 9 содержат не более одного простого числа (числа 3); Остальные прогрессии чисел, такие как 2, 4, 5, 7 и 8 по модулю 9, имеют бесконечно много простых чисел с одинаковым количеством простых чисел в каждой прогрессии.

Теорема Грина –Тао показывает, что существуют конечные арифметические прогрессии произвольной длины, состоящие только из простых чисел. ^[35]^[84]

Простые значения квадратичных многочленов

Эйлер заметил, что функция

n^{2}-n+41

дает простые числа для $1\leq n\leq 40$ , хотя среди его более поздних значений появляются составные числа. ^[85]^[86] Поиски объяснения этого явления привели к глубокой алгебраической теории чисел Хегнера и проблеме числа классов . ^[87]Гипотеза Харди – Литтлвуда F предсказывает плотность простых чисел среди значений квадратичных многочленов с целыми коэффициентами в терминах логарифмического интеграла и полиномиальных коэффициентов. Доказано, что ни один квадратичный многочлен не принимает бесконечное количество простых значений. ^[88]

Спираль Улама упорядочивает натуральные числа в двумерной сетке, спиралевидно образуя концентрические квадраты, окружающие начало координат, с выделенными простыми числами. Визуально кажется, что простые числа группируются на определенных диагоналях, а не на других, что позволяет предположить, что некоторые квадратичные многочлены принимают простые значения чаще, чем другие. ^[88]

Дзета-функция и гипотеза Римана

Одним из самых известных нерешенных вопросов математики, датируемым 1859 годом, и одной из задач Премии тысячелетия , является гипотеза Римана , которая спрашивает, где находятся нули . дзета-функции Римана $\zeta (s)$ расположены. Эта функция является аналитической функцией комплексных чисел . Для комплексных чисел $s$ с действительной частью больше единицы, он равен как бесконечной сумме всех целых чисел, так и бесконечному произведению простых чисел,

\zeta (s)=\sum _{n=1}^{\infty }{\frac {1}{n^{s}}}=\prod _{p{\text{ prime}}}{\frac {1}{1-p^{-s}}}.

Это равенство суммы и произведения, открытое Эйлером, называется эйлеровым произведением . ^[89] Произведение Эйлера может быть получено из фундаментальной теоремы арифметики и показывает тесную связь между дзета-функцией и простыми числами. ^[90]Это приводит к другому доказательству того, что простых чисел бесконечно много: если бы их было только конечное число, тогда равенство суммы и произведения также будет справедливым при $s=1$ , но сумма расходилась бы (это гармонический ряд $1+{\tfrac {1}{2}}+{\tfrac {1}{3}}+\dots$ ), хотя произведение было бы конечным, противоречие. ^[91]

Гипотеза Римана утверждает, что все нули дзета-функции являются либо отрицательными четными числами, либо комплексными числами с действительной частью, равной 1/2. ^[92] Первоначальное доказательство теоремы о простых числах было основано на слабой форме этой гипотезы о том, что не существует нулей с действительной частью, равной 1, ^[93]^[94] хотя были найдены и другие, более элементарные доказательства. ^[95]Функция подсчета простых чисел может быть выражена явной формулой Римана как сумма, в которой каждый член происходит от одного из нулей дзета-функции; главным членом этой суммы является логарифмический интеграл, а остальные члены заставляют сумму колебаться выше и ниже основного члена. ^[96]В этом смысле нули определяют, насколько регулярно распределяются простые числа. Если гипотеза Римана верна, эти флуктуации будут малы, и асимптотическое распределение простых чисел, заданное теоремой о простых числах, также будет выполняться на гораздо более коротких интервалах (длиной около квадратного корня из $x$ для интервалов возле числа $x$ ). ^[94]

Абстрактная алгебра

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

Модульная арифметика изменяет обычную арифметику, используя только числа. $\{0,1,2,\dots ,n-1\}$ , для натурального числа $n$ называется модулем. Любое другое натуральное число можно отобразить в эту систему, заменив его остатком после деления на $n$ . ^[97]Модульные суммы, разности и произведения рассчитываются путем выполнения той же замены на остаток на результат обычной суммы, разности или произведения целых чисел. ^[98] Равенство целых чисел соответствует сравнению в модульной арифметике: $x$ и $y$ совпадают (написано $x\equiv y$ против $n$ ), когда у них одинаковый остаток после деления на $n$ . ^[99]Однако в этой системе чисел деление на все ненулевые числа возможно тогда и только тогда, когда модуль является простым. Например, с простым числом $7$ по модулю, деление на $3$ возможно: $2/3\equiv 3{\bmod {7}}$ , поскольку очистка знаменателей путем умножения обеих частей на $3$ дает действительную формулу $2\equiv 9{\bmod {7}}$ . Однако при сложном модуле $6$ , деление на $3$ невозможно. Не существует действительного решения $2/3\equiv x{\bmod {6}}$ : очистка знаменателей путем умножения на $3$ приводит к тому, что левая часть становится $2$ в то время как правая часть становится либо $0$ или $3$ . В терминологии абстрактной алгебры способность осуществлять деление означает, что модулярная арифметика по модулю простого числа образует поле или, точнее, конечное поле , в то время как другие модули дают только кольцо , но не поле. ^[100]

Несколько теорем о простых числах можно сформулировать с помощью модульной арифметики. Например, маленькая теорема Ферма утверждает, что если $a\not \equiv 0$ (против $p$ ), затем $a^{p-1}\equiv 1$ (против $p$ ). ^[101] Суммируя это по всем вариантам $a$ дает уравнение

\sum _{a=1}^{p-1}a^{p-1}\equiv (p-1)\cdot 1\equiv -1{\pmod {p}},

действителен всегда, когда $p$ является простым. Гипотеза Джуги утверждает, что это уравнение также является достаточным условием для $p$ быть главным. ^[102] Теорема Вильсона утверждает, что целое число $p>1$ является простым тогда и только тогда, когда факториал $(p-1)!$ соответствует $-1$ против $p$ . Для составного числа $\;n=r\cdot s\;$ это не может быть выполнено, поскольку один из его факторов делит как $n$ , так и $(n-1)!$ , и так $(n-1)!\equiv -1{\pmod {n}}$ невозможно. ^[103]

p -адические числа

The $p$ - то есть заказ $\nu _{p}(n)$ целого числа $n$ это количество копий $p$ в простой факторизации $n$ . Эту же концепцию можно распространить на целые числа на рациональные числа, определив $p$ -адический порядок дроби $m/n$ быть $\nu _{p}(m)-\nu _{p}(n)$ . $p$ -адическое абсолютное значение $|q|_{p}$ любого рационального числа $q$ затем определяется как $|q|_{p}=p^{-\nu _{p}(q)}$ . Умножение целого числа на его $p$ -адическая абсолютная величина отменяет факторы $p$ в его факторизации, оставив только остальные простые числа. Точно так же, как расстояние между двумя действительными числами можно измерить по абсолютной величине их расстояния, расстояние между двумя рациональными числами можно измерить по их величине. $p$ -адическое расстояние, $p$ -адическая абсолютная величина их разности. Для этого определения расстояния два числа находятся близко друг к другу (они имеют небольшое расстояние), когда их разница делится на большую степень. $p$ . Точно так же, как действительные числа могут быть образованы из рациональных чисел и расстояний между ними, путем добавления дополнительных предельных значений для формирования полного поля , рациональные числа с $p$ -адическое расстояние может быть расширено до другого полного поля, $p$ -адические числа . ^[104]^[105]

Выведенную из них картину порядка, абсолютного значения и полного поля можно обобщить на поля алгебраических чисел и их оценки (некоторые отображения мультипликативной группы поля в полностью упорядоченную аддитивную группу , называемую также порядками), абсолютные значения ( некоторые мультипликативные отображения поля в действительные числа, также называемые нормами), ^[104] и места (расширения полных полей , в которых данное поле представляет собой плотное множество , также называемые пополнениями). ^[106] распространение рациональных чисел на действительные числа Например, — это место, в котором расстояние между числами является обычным абсолютным значением их разности. Соответствующим преобразованием в аддитивную группу будет логарифм абсолютной величины, хотя это не отвечает всем требованиям оценки. Согласно теореме Островского , с точностью до естественного понятия эквивалентности действительные числа и $p$ -адические числа с их порядками и абсолютными значениями являются единственными оценками, абсолютными значениями и местами в рациональных числах. ^[104] Локально -глобальный принцип позволяет решать определенные проблемы с рациональными числами путем объединения решений из каждого места, что еще раз подчеркивает важность простых чисел для теории чисел. ^[107]

Простые элементы в кольцах

Коммутативное кольцо — это алгебраическая структура , в которой определены сложение, вычитание и умножение. Целые числа представляют собой кольцо, а простые числа в целых числах были обобщены на кольца двумя разными способами: простые элементы и неприводимые элементы . Элемент $p$ кольца $R$ называется простым, если оно не равно нулю, не имеет обратного мультипликативного значения (то есть не является единицей ) и удовлетворяет следующему требованию: всякий раз, когда $p$ делит продукт $xy$ из двух элементов $R$ , оно также делит хотя бы одно из $x$ или $y$ . Элемент является несократимым, если он не является ни единицей, ни произведением двух других неединичных элементов. В кольце целых чисел простые и неприводимые элементы образуют один и тот же набор:

\{\dots ,-11,-7,-5,-3,-2,2,3,5,7,11,\dots \}\,.

В произвольном кольце все простые элементы неприводимы. Обратное утверждение не справедливо в общем случае, но справедливо для уникальных областей факторизации . ^[108]

Фундаментальная теорема арифметики продолжает выполняться (по определению) в уникальных областях факторизации. Примером такой области являются целые гауссовы числа. $\mathbb {Z} [i]$ , кольцо комплексных чисел вида $a+bi$ где $i$ обозначает мнимую единицу и $a$ и $b$ являются произвольными целыми числами. Его простые элементы известны как простые числа Гаусса . Не каждое число, которое является простым среди целых чисел, остается простым в гауссовских целых числах; например, число 2 можно записать как произведение двух простых гауссовых чисел $1+i$ и $1-i$ . Рациональные простые числа (простые элементы в целых числах), конгруэнтные 3 по модулю 4, являются гауссовскими простыми числами, а рациональные простые числа, конгруэнтные 1 по модулю 4, таковыми не являются. ^[109]Это следствие теоремы Ферма о суммах двух квадратов : в котором говорится, что нечетное простое число $p$ выражается как сумма двух квадратов, $p=x^{2}+y^{2}$ , и, следовательно, факторизуемы как $p=(x+iy)(x-iy)$ , именно тогда, когда $p$ это 1 мод 4. ^[110]

Главные идеалы

Не каждое кольцо является уникальной областью факторизации. Например, в кольце чисел $a+b{\sqrt {-5}}$ (для целых чисел $a$ и $b$ ) номер $21$ имеет две факторизации $21=3\cdot 7=(1+2{\sqrt {-5}})(1-2{\sqrt {-5}})$ , где ни один из четырех факторов не может быть сокращен дальше, поэтому он не имеет уникальной факторизации. Чтобы распространить уникальную факторизацию на более широкий класс колец, понятие числа можно заменить понятием идеала , подмножества элементов кольца, которое содержит все суммы пар его элементов и все произведения его элементов. элементы с кольцевыми элементами. Первичные идеалы , которые обобщают простые элементы в том смысле, что главный идеал , порожденный простым элементом, является простым идеалом, являются важным инструментом и объектом изучения в коммутативной алгебре , теории алгебраических чисел и алгебраической геометрии . Простыми идеалами кольца целых чисел являются идеалы (0), (2), (3), (5), (7), (11), ... Основная теорема арифметики обобщается на теорему Ласкера – Нётер. , которое выражает каждый идеал в нётеровом коммутативном кольце как пересечение первичных идеалов , которые являются соответствующими обобщениями простых степеней . ^[111]

Спектр кольца — это геометрическое пространство, точки которого являются простыми идеалами кольца. ^[112] Арифметическая геометрия также извлекает выгоду из этого понятия, и как в геометрии, так и в теории чисел существует множество концепций. Например, факторизация или ветвление простых идеалов при их переносе в поле расширения — основная проблема теории алгебраических чисел — имеет некоторое сходство с ветвлением в геометрии . Эти концепции могут даже помочь в решении теоретико-числовых вопросов, касающихся исключительно целых чисел. Например, простые идеалы в кольце целых полей квадратичных чисел можно использовать при доказательстве квадратичной взаимности - утверждения, которое касается существования квадратных корней по модулю целых простых чисел. ^[113] Ранние попытки доказать Великую теорему Ферма привели к регулярных введению Куммером простых чисел , целых простых чисел, связанных с невозможностью однозначной факторизации в круговых целых числах . ^[114] Вопрос о том, сколько целых простых чисел входит в произведение нескольких простых идеалов в поле алгебраических чисел, решается теоремой плотности Чеботарёва , которая (в применении к круговым целым числам) имеет теорему Дирихле о простых числах в арифметических прогрессиях как частный случай. ^[115]

Теория групп

В теории конечных групп из теорем Силова следует, что если степень простого числа $p^{n}$ делит порядок группы , то в группе есть подгруппа порядка $p^{n}$ . По теореме Лагранжа любая группа простого порядка является циклической группой . и по теореме Бернсайда любая группа, порядок которой делится только на два простых числа разрешима . ^[116]

Вычислительные методы

Долгое время теория чисел в целом и изучение простых чисел в частности рассматривались как канонический пример чистой математики, не имеющий никаких приложений за пределами математики. ^[б] за исключением использования зубьев шестерни с простыми номерами для равномерного распределения износа. ^[117] В частности, теоретики чисел, такие как британский математик Г.Х. Харди, гордились тем, что выполняли работу, не имевшую абсолютно никакого военного значения. ^[118]

Это представление о чистоте теории чисел было разрушено в 1970-х годах, когда было публично объявлено, что простые числа могут использоваться в качестве основы для создания криптографии с открытым ключом . алгоритмов ^[32]Эти приложения привели к значительному изучению алгоритмов вычислений с простыми числами и, в частности, проверки на простоту , методов определения того, является ли данное число простым. Самая простая процедура проверки простоты — пробное деление — слишком медленная, чтобы быть полезной для больших чисел. Одна группа современных тестов на простоту применима к произвольным числам, тогда как более эффективные тесты доступны для чисел специальных типов. Большинство тестов на простоту лишь показывают, является ли их аргумент простым или нет. Подпрограммы, которые также предоставляют простой множитель составных аргументов (или все его простые множители), называются алгоритмами факторизации . Простые числа также используются при вычислении контрольных сумм , хеш-таблиц и генераторов псевдослучайных чисел .

Пробное подразделение

Самый простой метод проверки простоты данного целого числа. $n$ называется пробным делением . Этот метод делит $n$ на каждое целое число от 2 до квадратного корня из $n$ . Любое такое целочисленное деление $n$ равномерно устанавливает $n$ как составной; в противном случае оно является простым. Целые числа, превышающие квадратный корень, проверять не нужно, поскольку всякий раз, когда $n=a\cdot b$ , один из двух факторов $a$ и $b$ меньше или равно квадратному корню из $n$ . Другая оптимизация — проверять только простые числа в качестве факторов в этом диапазоне. ^[119] Например, чтобы проверить, является ли 37 простым, этот метод делит его на простые числа в диапазоне от 2 до ${\sqrt {37}}$ , которые равны 2, 3 и 5. Каждое деление дает ненулевой остаток, поэтому 37 действительно является простым числом.

Хотя этот метод прост в описании, он непрактичен для проверки простоты больших целых чисел, поскольку количество выполняемых им тестов растет экспоненциально в зависимости от количества цифр этих целых чисел. ^[120] Однако пробное деление по-прежнему используется с меньшим пределом, чем квадратный корень размера делителя, для быстрого обнаружения составных чисел с небольшими делителями, прежде чем использовать более сложные методы для чисел, которые проходят этот фильтр. ^[121]

Сита

Анимация решета Эратосфена — Решето Эратосфена начинается с неотмеченных цифр (серого цвета). Он неоднократно находит первое немаркированное число, помечает его как простое (темные цвета) и отмечает его квадрат и все последующие кратные как составные (светлые цвета). После маркировки чисел, кратных 2 (красный), 3 (зеленый), 5 (синий) и 7 (желтый), все простые числа до квадратного корня из размера таблицы были обработаны, а все оставшиеся неотмеченные числа (11, 13) и т. д.) отмечены штрихами (пурпурным).

До появления компьютеров обычно печатались математические таблицы , в которых перечислялись все простые числа или их факторизации до заданного предела. ^[122] Самый старый известный метод создания списка простых чисел называется решетом Эратосфена. ^[123] На анимации показан оптимизированный вариант этого метода. ^[124] Другой, более асимптотически эффективный метод просеивания для той же задачи — это решето Аткина . ^[125] В высшей математике теория решета применяет аналогичные методы к другим задачам. ^[126]

Тестирование на простоту против доказательства простоты

Некоторые из самых быстрых современных тестов на предмет того, является ли произвольное заданное число $n$ является простым — это вероятностные алгоритмы (или алгоритмы Монте-Карло ), что означает, что у них есть небольшой случайный шанс дать неправильный ответ. ^[127] Например, критерий простоты Соловея – Штрассена для заданного числа. $p$ выбирает номер $a$ случайно из $2$ через $p-2$ и использует модульное возведение в степень для проверки ли $a^{(p-1)/2}\pm 1$ делится на $p$ . ^[с]Если да, то он отвечает «да», в противном случае — «нет». Если $p$ действительно простое число, оно всегда ответит «да», но если $p$ является составным, то он отвечает «да» с вероятностью не более 1/2 и «нет» с вероятностью не менее 1/2. ^[128] Если этот тест повторить $n$ раз на одно и то же число, вероятность того, что составное число сможет пройти проверку каждый раз, не превышает $1/2^{n}$ . Поскольку это значение экспоненциально уменьшается с увеличением количества тестов, это обеспечивает высокую уверенность (хотя и не уверенность) в том, что число, прошедшее повторный тест, является простым. С другой стороны, если тест когда-либо провалится, то число, безусловно, будет составным. ^[129] Составное число, которое проходит такой тест, называется псевдопростым . ^[128]

Напротив, некоторые другие алгоритмы гарантируют, что их ответ всегда будет правильным: простые числа всегда будут определяться как простые, а сложные числа всегда будут определяться как составные. Например, это справедливо для пробного деления. К алгоритмам с гарантированно правильным выводом относятся как детерминированные (неслучайные) алгоритмы, такие как тест на простоту AKS , ^[130] и рандомизированные алгоритмы Лас-Вегаса , в которых случайный выбор, сделанный алгоритмом, не влияет на его окончательный ответ, например, некоторые варианты доказательства простоты эллиптических кривых . ^[127] Когда метод эллиптической кривой приходит к выводу, что число является простым, он предоставляет сертификат простоты , который можно быстро проверить. ^[131]Тест на простоту эллиптической кривой является самым быстрым на практике из гарантированно правильных тестов на простоту, но его анализ во время выполнения основан на эвристических аргументах, а не на строгих доказательствах. Тест простоты AKS имеет математически доказанную временную сложность, но на практике он медленнее, чем проверка простоты эллиптической кривой. ^[132]Эти методы можно использовать для генерации больших случайных простых чисел путем генерации и проверки случайных чисел, пока не будет найдено простое число; при этом более быстрый вероятностный тест может быстро исключить большинство составных чисел, прежде чем будет использован гарантированно правильный алгоритм для проверки того, что оставшиеся числа являются простыми. ^[д]

В следующей таблице перечислены некоторые из этих тестов. Время их работы выражается в $n$ , число для проверки и, для вероятностных алгоритмов, число $k$ проведенных испытаний. Более того, $\varepsilon$ — сколь угодно малое положительное число, а log — логарифм по неопределенному основанию. Большое обозначение O означает, что каждую временную границу следует умножить на постоянный коэффициент , чтобы преобразовать ее из безразмерных единиц в единицы времени; этот фактор зависит от деталей реализации, таких как тип компьютера, используемого для запуска алгоритма, но не от входных параметров. $n$ и $k$ .

Тест	Разработано в	Тип	Продолжительность	Примечания	Рекомендации
Тест на простоту AKS	2002	детерминированный	$O((\log n)^{6+\varepsilon })$		^[130]^[133]
Доказательство простоты эллиптической кривой	1986	Лас Вегас	$O((\log n)^{4+\varepsilon })$ эвристически		^[132]
Тест на простоту Бэйли – PSW	1980	Монте-Карло	$O((\log n)^{2+\varepsilon })$		^[134]^[135]
Тест на простоту Миллера – Рабина	1980	Монте-Карло	$O(k(\log n)^{2+\varepsilon })$	вероятность ошибки $4^{-k}$	^[136]
Тест на простоту Соловея – Штрассена	1977	Монте-Карло	$O(k(\log n)^{2+\varepsilon })$	вероятность ошибки $2^{-k}$	^[136]

Алгоритмы специального назначения и самое большое известное простое число

В дополнение к вышеупомянутым тестам, применимым к любому натуральному числу, некоторые числа специального вида можно проверить на простоту быстрее. Например, тест на простоту Лукаса-Лемера может определить, является ли число Мерсенна (на единицу меньше степени двойки ) простым детерминированным образом. одновременно с одной итерацией теста Миллера-Рабина. ^[137] Именно поэтому с 1992 г. (по состоянию на декабрь 2018 г.) ^[update]) самым большим известным простым числом всегда было простое число Мерсенна. ^[138] Предполагается, что существует бесконечно много простых чисел Мерсенна. ^[139]

В следующей таблице приведены самые большие известные простые числа различных типов. Некоторые из этих простых чисел были найдены с помощью распределенных вычислений . В 2009 году проект Great Internet Mersenne Prime Search был награжден премией в размере 100 000 долларов США за первое обнаружение простого числа, содержащего не менее 10 миллионов цифр. ^[140] Electronic Frontier Foundation также предлагает 150 000 и 250 000 долларов за простые числа, содержащие не менее 100 миллионов цифр и 1 миллиард цифр соответственно. ^[141]

Тип	Основной	Количество десятичных цифр	Дата	Найден пользователем
Бонус Мерсенна	2 ^82,589,933 − 1	24,862,048	7 декабря 2018 г. ^[1]	Патрик Ларош, великий интернет-поиск простых чисел Мерсенна
Прот Прайм	10,223 × 2 ^31,172,165 + 1	9,383,761	31 октября 2016 г. ^[142]	Петер Сабольч, PrimeGrid ^[143]
факториал простого числа	208,003! − 1	1,015,843	июль 2016 г.	Соу Фукуи ^[144]
первобытный расцвет ^[Это]	1,098,133# − 1	476,311	Март 2012 г.	Джеймс П. Берт, PrimeGrid ^[146]
простые числа-близнецы	2,996,863,034,895 × 2 ^1,290,000 ± 1	388,342	Сентябрь 2016 г.	Том Грир, PrimeGrid ^[147]

Целочисленная факторизация

Учитывая составное целое число $n$ называется факторизацией , задача получения одного (или всех) простых множителей $n$ . Это значительно сложнее, чем тестирование на простоту, ^[148]и хотя известно множество алгоритмов факторизации, они медленнее, чем самые быстрые методы проверки простоты. Пробное деление и ро-алгоритм Полларда можно использовать для нахождения очень малых коэффициентов $n$ , ^[121] и факторизация эллиптической кривой может быть эффективной, когда $n$ имеет факторы умеренного размера. ^[149]Методы, подходящие для произвольно больших чисел, не зависящих от размера их факторов, включают квадратичное решето и решето общего числового поля . Как и при тестировании на простоту, существуют также алгоритмы факторизации, которые требуют, чтобы их входные данные имели специальную форму, включая решето специального числового поля . ^[150] По состоянию на декабрь 2019 г. ^[update] Самое большое число, которое, как известно, было факторизовано с помощью алгоритма общего назначения, — это RSA-240 , которое имеет 240 десятичных цифр (795 бит) и является произведением двух больших простых чисел. ^[151]

Алгоритм Шора может факторизовать любое целое число за полиномиальное число шагов на квантовом компьютере . ^[152]Однако современные технологии позволяют использовать этот алгоритм только для очень небольших чисел. По состоянию на октябрь 2012 г. ^[update] наибольшее число, которое было учтено квантовым компьютером с помощью алгоритма Шора, равно 21. ^[153]

Другие вычислительные приложения

Некоторые алгоритмы криптографии с открытым ключом , такие как RSA и обмен ключами Диффи-Хеллмана , основаны на больших простых числах ( 2048- битные простые числа). обычно ^[154] RSA исходит из предположения, что гораздо проще (то есть эффективнее) выполнить умножение двух (больших) чисел. $x$ и $y$ чем рассчитать $x$ и $y$ (предполагается взаимно простым ), если только произведение $xy$ известен. ^[32] Обмен ключами Диффи-Хеллмана основан на том факте, что существуют эффективные алгоритмы модульного возведения в степень (вычисления $a^{b}{\bmod {c}}$ ), тогда как обратная операция ( дискретный логарифм ) считается сложной задачей. ^[155]

Простые числа часто используются для хеш-таблиц . Например, оригинальный метод Картера и Вегмана для универсального хеширования был основан на вычислении хеш-функций путем выбора случайных линейных функций по модулю больших простых чисел. Картер и Вегман обобщили этот метод на $k$ -независимое хеширование с использованием полиномов более высокой степени, опять же по модулю больших простых чисел. ^[156] Как и в хеш-функции, простые числа используются для размера хеш-таблицы в хеш-таблицах на основе квадратичного зондирования , чтобы гарантировать, что последовательность зондирования покрывает всю таблицу. ^[157]

Некоторые методы контрольной суммы основаны на математике простых чисел. Например, контрольные суммы, используемые в международных стандартных книжных номерах, определяются путем взятия оставшейся части числа по модулю 11, простого числа. Поскольку 11 — простое число, этот метод может обнаруживать как однозначные ошибки, так и перестановки соседних цифр. ^[158] Другой метод контрольной суммы, Adler-32 , использует арифметику по модулю 65521, наибольшее простое число меньше $2^{16}$ . ^[159] Простые числа также используются в генераторах псевдослучайных чисел, включая линейные конгруэнтные генераторы. ^[160] и Твистер Мерсенна . ^[161]

Другие приложения

Простые числа имеют центральное значение для теории чисел, но также имеют множество приложений в других областях математики, включая абстрактную алгебру и элементарную геометрию. Например, можно разместить простые числа точек в двумерной сетке так, чтобы никакие три точки не находились на линии , или чтобы каждый треугольник, образованный тремя точками, имел большую площадь . ^[162] Другой пример — критерий Эйзенштейна , тест на неприводимость многочлена, основанный на делении его коэффициентов на простое число и его квадрат. ^[163]

Понятие простого числа настолько важно, что в разных разделах математики оно по-разному обобщалось. Обычно слово «простое» указывает на минимальность или неразложимость в соответствующем смысле. Например, простое поле данного поля — это его наименьшее подполе, содержащее как 0, так и 1. Это либо поле рациональных чисел, либо конечное поле с простым числом элементов, откуда и происходит название. ^[164]Часто при использовании слова «простой» подразумевается второе, дополнительное значение, а именно: любой объект можно, по существу, однозначно разложить на его простые компоненты. Например, в теории узлов — простой узел это узел , который неразложим в том смысле, что его нельзя записать как связную сумму двух нетривиальных узлов. Любой узел можно однозначно выразить как связную сумму простых узлов. ^[165] простое разложение трехмерных многообразий . Еще одним примером этого типа является ^[166]

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

Конструируемые многоугольники и разбиения многоугольников

Построение правильного пятиугольника с помощью линейки и циркуля. Это возможно только потому, что 5 — простое число Ферма .

Простые числа Ферма - это простые числа вида

F_{k}=2^{2^{k}}+1,

с $k$ неотрицательное целое число . ^[167]Они названы в честь Пьера Ферма , который предположил, что все такие числа являются простыми. Первые пять из этих чисел – 3, 5, 17, 257 и 65 537 – являются простыми. ^[168] но $F_{5}$ является составным, как и все другие числа Ферма, проверенные по состоянию на 2017 год. ^[169] Обычный $n$ -угольник можно построить с помощью линейки и циркуля тогда и только тогда, когда нечетные простые множители $n$ (если таковые имеются) являются различными простыми числами Ферма. ^[168] Аналогично, штатный $n$ -угольник можно построить с помощью линейки, циркуля и трисектора угла тогда и только тогда, когда простые множители $n$ — это любое количество копий 2 или 3 вместе с (возможно, пустым) набором различных простых чисел Пьерпона , простых чисел вида $2^{a}3^{b}+1$ . ^[170]

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

Квантовая механика

Начиная с работ Хью Монтгомери и Фримена Дайсона в 1970-х годах, математики и физики предположили, что нули дзета-функции Римана связаны с энергетическими уровнями квантовых систем . ^[172]^[173] Простые числа также играют важную роль в квантовой информатике благодаря математическим структурам, таким как взаимно несмещенные основания и симметричные информационно полные меры с положительным операторным значением . ^[174]^[175]

Биология

Эволюционная стратегия, используемая цикадами рода Magicicada, использует простые числа. ^[176]Эти насекомые проводят большую часть своей жизни в виде личинок под землей. Они только окукливаются, а затем выходят из своих нор через 7, 13 или 17 лет, после чего летают, размножаются, а затем умирают максимум через несколько недель. Биологи предполагают, что продолжительность цикла размножения с простыми числами возникла для того, чтобы не дать хищникам синхронизироваться с этими циклами. ^[177]^[178] Напротив, предполагается, что многолетние периоды между цветением растений бамбука представляют собой гладкие числа , имеющие лишь небольшие простые числа в своих факторизациях. ^[179]

Искусство и литература

Простые числа оказали влияние на многих художников и писателей. Французский композитор Оливье Мессиан использовал простые числа для создания метрической музыки посредством «природных явлений». В таких работах, как «Нативите дю сеньора» (1935) и «Четыре этюда ритма» (1949–50), он одновременно использует мотивы, длина которых определяется разными простыми числами, для создания непредсказуемых ритмов: простые числа 41, 43, 47 и 53 появляются в третий этюд «Ритмические стихи». По словам Мессиана, этот способ сочинения был «вдохновлен движениями природы, движениями свободной и неравной продолжительности». ^[180]

В своем научно-фантастическом романе «Контакт» учёный Карл Саган предположил, что факторизация простых чисел может использоваться как средство установления двумерных плоскостей изображения при общении с инопланетянами. Эту идею он впервые неофициально разработал вместе с американским астрономом Фрэнком Дрейком в 1975 году. ^[181] В романе «Загадочное ночное происшествие с собакой» Марка Хэддона рассказчик располагает разделы истории последовательными простыми числами, чтобы передать психическое состояние главного героя, математически одаренного подростка с синдромом Аспергера. . ^[182] Простые числа используются как метафора одиночества и изоляции в Паоло Джордано романе «Одиночество простых чисел» , в котором они изображаются как «чужаки» среди целых чисел. ^[183]

Примечания

^ 44-значное простое число, найденное в 1951 году Эме Феррье с помощью механического калькулятора, остается самым большим простым числом, которое не было найдено с помощью электронных компьютеров. ^[28]
^ Перейти обратно: ^а ^б Например, Бейлер пишет, что теоретик чисел Эрнст Куммер любил свои идеальные числа , тесно связанные с простыми числами, «потому что они не запятнали себя какими-либо практическими приложениями». ^[30] и Кац пишет, что Эдмунд Ландау , известный своей работой по распределению простых чисел, «ненавидел практические применения математики» и по этой причине избегал таких предметов, как геометрия , которые уже показали себя полезными. ^[31]
^ В этом тесте $\pm 1$ термин отрицательный, если $a$ является квадратом по модулю данного (предполагаемого) простого числа $p$ , и положительный в противном случае. В более общем смысле, для непростых значений $p$ , $\pm 1$ термин (отрицается) Символ Якоби , который можно вычислить с помощью квадратичной взаимности .
^ Действительно, большая часть анализа доказательства простоты эллиптических кривых основана на предположении, что входные данные алгоритма уже прошли вероятностный тест. ^[131]
^ Основная функция $n$ , обозначенный $n\#$ , дает произведение простых чисел до $n$ , а первичное простое число — это простое число одной из форм $n\#\pm 1$ . ^[145]

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

"Простое число" . Энциклопедия математики . ЭМС Пресс . 2001 [1994].
Колдуэлл, Крис, The Prime Pages на primes.utm.edu .
Простые числа в программе «В наше время» на BBC
Пакет Plus для учителей и студентов: простые числа из Plus, бесплатного онлайн-журнала по математике, выпускаемого в рамках проекта Millennium Mathematics Project в Кембриджском университете.

Генераторы и калькуляторы

Калькулятор простых коэффициентов может факторизовать любое положительное целое число до 20 цифр.
Быстрый онлайн-тест на простоту с факторизацией использует метод эллиптических кривых (до тысячных цифр, требуется Java).
Огромная база данных простых чисел
Простые числа до 1 триллиона. Архивировано 27 февраля 2021 г. на Wayback Machine.

[29] 44-значное простое число, найденное в 1951 году Эме Феррье с помощью механического калькулятора, остается самым большим простым числом, которое не было найдено с помощью электронных компьютеров. ^[28]

[pure-33] Перейти обратно: ^а ^б Например, Бейлер пишет, что теоретик чисел Эрнст Куммер любил свои идеальные числа , тесно связанные с простыми числами, «потому что они не запятнали себя какими-либо практическими приложениями». ^[30] и Кац пишет, что Эдмунд Ландау , известный своей работой по распределению простых чисел, «ненавидел практические применения математики» и по этой причине избегал таких предметов, как геометрия , которые уже показали себя полезными. ^[31]

[130] В этом тесте $\pm 1$ термин отрицательный, если $a$ является квадратом по модулю данного (предполагаемого) простого числа $p$ , и положительный в противном случае. В более общем смысле, для непростых значений $p$ , $\pm 1$ термин (отрицается) Символ Якоби , который можно вычислить с помощью квадратичной взаимности .

[136] Действительно, большая часть анализа доказательства простоты эллиптических кривых основана на предположении, что входные данные алгоритма уже прошли вероятностный тест. ^[131]

[150] Основная функция $n$ , обозначенный $n\#$ , дает произведение простых чисел до $n$ , а первичное простое число — это простое число одной из форм $n\#\pm 1$ . ^[145]

[GIMPS-2018-1] Перейти обратно: ^а ^б «Проект GIMPS обнаружил самое большое известное простое число: 2». ^82,589,933-1» . Mersenne Research, Inc. 21 декабря 2018 г. Дата обращения 21 декабря 2018 г.

[2] Гардинер, Энтони (1997). Справочник по математическим олимпиадам: введение в решение задач на основе первых 32 британских математических олимпиад 1965–1996 годов . Издательство Оксфордского университета. п. 26 . ISBN 978-0-19-850105-3 .

[3] Хендерсон, Энн (2014). Дислексия, дискалькулия и математика: Практическое руководство (2-е изд.). Рутледж. п. 62. ИСБН 978-1-136-63662-2 .

[4] Адлер, Ирвинг (1960). Гигантская золотая книга по математике: исследование мира чисел и пространства . Золотая Пресса. п. 16 . OCLC 6975809 .

[5] Лефф, Лоуренс С. (2000). Рабочая тетрадь по математике для SAT I. Образовательная серия Бэррона. п. 360 . ISBN 978-0-7641-0768-9 .

[6] Дадли, Андервуд (1978). «Раздел 2: Уникальная факторизация» . Элементарная теория чисел (2-е изд.). WH Freeman and Co. p. 10 . ISBN 978-0-7167-0076-0 .

[7] Серпинский, Вацлав (1988). Элементарная теория чисел Математическая библиотека Северной Голландии. Том. 31 (2-е изд.). Эльзевир. п. 113. ИСБН 978-0-08-096019-7 .

[ziegler-8] Перейти обратно: ^а ^б Циглер, Гюнтер М. (2004). «Великие гонки на рекорды простых чисел». Уведомления Американского математического общества . 51 (4): 414–416. МР 2039814 .

[9] Стиллвелл, Джон (1997). Числа и геометрия . Тексты для бакалавриата по математике. Спрингер. п. 9. ISBN 978-0-387-98289-2 .

[10] Серпинский, Вацлав (1964). Подборка задач теории чисел . Нью-Йорк: Макмиллан. п. 40 . МР 0170843 .

[11] Натансон, Мелвин Б. (2000). «Обозначения и соглашения» . Элементарные методы теории чисел . Тексты для аспирантов по математике. Том. 195. Спрингер. ISBN 978-0-387-22738-2 . МР 1732941 .

[12] Фатикони, Теодор Г. (2012). Математика бесконечности: Путеводитель по великим идеям . Чистая и прикладная математика: серия текстов, монографий и трактатов Wiley. Том. 111 (2-е изд.). Джон Уайли и сыновья. п. 44. ИСБН 978-1-118-24382-4 .

[13] Брюинз, Эверт Мари, обзор в Mathematical Reviews of Гиллингс, Р.Дж. (1974). «Лицевая сторона Математического папируса Ринда. Как его приготовил древнеегипетский писец?». Архив истории точных наук . 12 (4): 291–298. дои : 10.1007/BF01307175 . МР 0497458 . S2CID 121046003 .

[stillwell-2010-p40-14] Перейти обратно: ^а ^б Стиллвелл, Джон (2010). Математика и ее история . Тексты для студентов по математике (3-е изд.). Спрингер. п. 40. ISBN 978-1-4419-6052-8 .

[pomerance-sciam-15] Перейти обратно: ^а ^б Померанс, Карл (декабрь 1982 г.). «В поисках простых чисел». Научный американец . 247 (6): 136–147. Бибкод : 1982SciAm.247f.136P . дои : 10.1038/scientificamerican1282-136 . JSTOR 24966751 .

[mollin-16] Перейти обратно: ^а ^б ^с ^д Моллин, Ричард А. (2002). «Краткая история факторинга и тестирования простоты до нашей эры (до компьютеров)». Журнал «Математика» . 75 (1): 18–29. дои : 10.2307/3219180 . JSTOR 3219180 . МР 2107288 .

[17] О'Коннор, Джон Дж.; Робертсон, Эдмунд Ф. «Абу Али аль-Хасан ибн аль-Хайсам» . MacTutor Архив истории математики . Университет Сент-Эндрюс .

[18] Сандифер 2007 , 8. Маленькая теорема Ферма (ноябрь 2003 г.), стр. 45

[19] Сандифер, К. Эдвард (2014). Как Эйлер сделал еще больше . Математическая ассоциация Америки. п. 42. ИСБН 978-0-88385-584-3 .

[20] Коши, Томас (2002). Элементарная теория чисел с приложениями . Академическая пресса. п. 369. ИСБН 978-0-12-421171-1 .

[21] Юань, Ван (2002). Гипотеза Гольдбаха . Серия по чистой математике. Том. 4 (2-е изд.). Всемирная научная. п. 21. ISBN 978-981-4487-52-8 .

[22] Наркевич, Владислав (2000). «1.2 Сумма обратных простых чисел» . Развитие теории простых чисел: от Евклида до Харди и Литтлвуда . Монографии Спрингера по математике. Спрингер. п. 11. ISBN 978-3-540-66289-1 .

[23] Чебышев, П. (1852). «Память на простые числа» (PDF) . Журнал чистой и прикладной математики . Серия 1 (на французском языке): 366–390. . (Доказательство постулата: 371–382). См. также «Воспоминания об Императорской Академии наук Петербурга», т. 1, с. 7, с. 15–33, 1854 г.

[24] Апостол, Том М. (2000). «Столетняя история теоремы о простых числах» . В Бамбе, РП; Думир, ВК; Ханс-Гилл, Р.Дж. (ред.). Теория чисел . Тенденции в математике. Базель: Биркхойзер. стр. 1–14. МР 1764793 .

[25] Апостол, Том М. (1976). «7. Теорема Дирихле о простых числах в арифметических прогрессиях» . Введение в аналитическую теорию чисел . Нью-Йорк; Гейдельберг: Springer-Verlag. стр. 146–156. МР 0434929 .

[26] Шабер, Жан-Люк (2012). История алгоритмов: от камешка до микрочипа Спрингер. п. 261. ИСБН 978-3-642-18192-4 .

[27] Розен, Кеннет Х. (2000). «Теорема 9.20. Тест Прота на простоту». Элементарная теория чисел и ее приложения (4-е изд.). Аддисон-Уэсли. п. 342. ИСБН 978-0-201-87073-2 .

[28] Купер, С. Барри; Ходжес, Эндрю (2016). Тьюринг «Прошлое и будущее» . Издательство Кембриджского университета. стр. 37–38. ISBN 978-1-107-01083-3 .

[30] Розен 2000 , с. 245.

[31] Бейлер, Альберт Х. (1999) [1966]. Отдых в теории чисел: Королева математики развлекает . Дувр. п. 2. ISBN 978-0-486-21096-4 . OCLC 444171535 .

[32] Кац, Шауль (2004). «Берлинские корни - воплощение сионизма: идеал чистой математики и начало Института математики Эйнштейна в Еврейском университете в Иерусалиме». Наука в контексте . 17 (1–2): 199–234. дои : 10.1017/S0269889704000092 . МР 2089305 . S2CID 145575536 .

[ent-7-34] Перейти обратно: ^а ^б ^с Крафт, Джеймс С.; Вашингтон, Лоуренс К. (2014). Элементарная теория чисел . Учебники по математике. ЦРК Пресс. п. 7. ISBN 978-1-4987-0269-0 .

[35] Бауэр, Крейг П. (2013). Тайная история: история криптологии . Дискретная математика и ее приложения. ЦРК Пресс. п. 468. ИСБН 978-1-4665-6186-1 .

[36] Клее, Виктор ; Вагон, Стэн (1991). Старые и новые нерешенные проблемы плоской геометрии и теории чисел . Математические изложения Дольчиани. Том. 11. Издательство Кембриджского университета. п. 224. ИСБН 978-0-88385-315-3 .

[neale-18-47-37] Перейти обратно: ^а ^б Нил, 2017 , стр. 18, 47.

[crxk-34-38] Перейти обратно: ^а ^б Колдуэлл, Крис К.; Реддик, Анджела; Сюн, Йенг; Келлер, Уилфрид (2012). «История первобытности одного: подборка источников» . Журнал целочисленных последовательностей . 15 (9): Статья 12.9.8. МР 3005523 . Подборку цитат из древнегреческих позиций о статусе 1 и 2 и о них см., в частности, на стр. 3–4. Об исламских математиках см. с. 6.

[39] Таран, Леонард (1981). Спевсипп Афинский: критическое исследование со сборником связанных текстов и комментариев . Philosophia Antiqua: Серия монографий по древней философии. Том. 39. Брилл. стр. 100-1 35–38. ISBN 978-90-04-06505-5 .

[40] Колдуэлл и др. 2012 , стр. 101-1. 7–13. См., в частности, записи о Стивене, Бранкере, Уоллисе и Престете.

[41] Колдуэлл и др. 2012 , с. 15.

[cx-42] Перейти обратно: ^а ^б ^с Колдуэлл, Крис К.; Сюн, Йенг (2012). «Каково наименьшее простое число?» (PDF) . Журнал целочисленных последовательностей . 15 (9): Статья 12.9.7. МР 3005530 .

[43] Ризель, Ганс (1994). Простые числа и компьютерные методы факторизации (2-е изд.). Базель, Швейцария: Биркхойзер. п. 36. дои : 10.1007/978-1-4612-0251-6 . ISBN 978-0-8176-3743-9 . МР 1292250 .

[cg-bon-129-130-44] Перейти обратно: ^а ^б Конвей, Джон Хортон ; Гай, Ричард К. (1996). Книга чисел . Нью-Йорк: Коперник. стр. 129–130 . дои : 10.1007/978-1-4612-4072-3 . ISBN 978-0-387-97993-9 . МР 1411676 .

[45] Подробнее см. Серпинский 1988 , с. 245 . О сумме делителей см. Сандифер, К. Эдвард (2007). Как Эйлер это сделал МАА Спектр. Математическая ассоциация Америки. п. 59. ИСБН 978-0-88385-563-8 .

[46] Смит, Карл Дж. (2011). Природа математики (12-е изд.). Cengage Обучение. п. 188. ИСБН 978-0-538-73758-6 .

[47] Дадли 1978 , раздел 2, теорема 2, с. 16 ; Нил, Вики (2017). Устранение разрыва: стремление понять простые числа . Издательство Оксфордского университета. п. 107 . ISBN 978-0-19-109243-5 .

[48] дю Сотуа, Маркус (2003). Музыка простых чисел: в поисках решения величайшей тайны математики . Харпер Коллинз. п. 23 . ISBN 978-0-06-093558-0 .

[49] Дадли 1978 , раздел 2, лемма 5, с. 15 ; Хиггинс, Питер М. (1998). Математика для любознательных . Издательство Оксфордского университета. стр. 77–78. ISBN 978-0-19-150050-3 .

[50] Ротман, Джозеф Дж. (2000). Первый курс абстрактной алгебры (2-е изд.). Прентис Холл. Задача 1.40, с. 56. ИСБН 978-0-13-011584-3 .

[51] Письмо на латыни , июль 1730 г. Гольдбаха Эйлеру

[52] Фюрстенберг, Гарри (1955). «О бесконечности простых чисел». Американский математический ежемесячник . 62 (5): 353. дои : 10.2307/2307043 . JSTOR 2307043 . МР 0068566 .

[53] Рибенбойм, Пауло (2004). Маленькая книга больших простых чисел . Берлин; Нью-Йорк: Springer-Verlag. п. 4. ISBN 978-0-387-20169-6 .

[54] Евклида Элементы , Книга IX, Предложение 20. См. английский перевод Дэвида Джойса доказательства Евклида или Уильямсон, Джеймс (1782). Элементы Евклида с диссертациями . Оксфорд: Кларендон Пресс . п. 63. ОСЛК 642232959 .

[55] Варди, Илан (1991). Вычислительные развлечения в системе Mathematica . Аддисон-Уэсли. стр. 100-1 82–89. ISBN 978-0-201-52989-0 .

[matiyasevich-56] Перейти обратно: ^а ^б ^с Матясевич, Юрий В. (1999). «Формулы простых чисел » Табачников , Серж (ред.). Квантовый выбор: алгебра и анализ . Том. II. Американское математическое общество . стр. 100-1 13–24. ISBN 978-0-8218-1915-9 .

[57] Маккиннон, Ник (июнь 1987 г.). «Формулы простых чисел». Математический вестник . 71 (456): 113–114. дои : 10.2307/3616496 . JSTOR 3616496 . S2CID 171537609 .

[58] Райт, Э.М. (1951). «Функция, представляющая простое число». Американский математический ежемесячник . 58 (9): 616–618. дои : 10.2307/2306356 . JSTOR 2306356 .

[59] Гай 2013 , с. VII .

[60] Гай 2013 , Гипотеза C1 Гольдбаха, стр. 105–107 .

[61] Оливейра и Силва, Томас; Херцог, Зигфрид; Парди, Сильвио (2014). «Эмпирическая проверка четной гипотезы Гольдбаха и вычисление простых пробелов до $4\cdot 10^{18}$ " . Математика вычислений . 83 (288): 2033–2060. doi : 10.1090/S0025-5718-2013-02787-1 . MR 3194140 .

[62] Тао 2009 , 3.1 Структура и случайность простых чисел, стр. 239–247 . См. особенно п. 239.

[63] Гай 2013 , с. 159.

[64] Рамаре, Оливье (1995). «О постоянной Шнирельмана» . Анналы Высшей нормальной школы Пизы . 22 (4): 645–706. МР 1375315 . Архивировано из оригинала 9 февраля 2022 г. Проверено 23 января 2018 г.

[65] Рассиас, Майкл Т. (2017). Проблема Гольдбаха: избранные темы . Чам: Спрингер. п. VII. дои : 10.1007/978-3-319-57914-6 . ISBN 978-3-319-57912-2 . МР 3674356 .

[66] Коши 2002 , Теорема 2.14, с. 109 . Ризель 1994 приводит аналогичный аргумент, используя первоначальный принцип вместо факториала.

[riesel-gaps-67] Перейти обратно: ^а ^б Ризель 1994 , « Большие промежутки между последовательными простыми числами », стр. 78–79.

[68] Слоан, Нью-Джерси (ред.). «Последовательность A100964 (Наименьшее простое число, которое начинается с промежутка между простыми числами не менее 2n)» . Электронная энциклопедия целочисленных последовательностей . Фонд ОЭИС.

[rib-gaps-69] Перейти обратно: ^а ^б ^с Рибенбойм 2004 , Промежутки между простыми числами, стр. 186–192.

[rib-183-70] Перейти обратно: ^а ^б Рибенбойм 2004 , с. 183.

[chan-71] Чан, Джоэл (февраль 1996 г.). "ПРАЙМ-тайм!". Математические горизонты . 3 (3): 23–25. дои : 10.1080/10724117.1996.11974965 . JSTOR 25678057 . Обратите внимание, что Чан называет гипотезу Лежандра «постулатом Серпинского».

[72] Рибенбойм 2004 , Премьер $k$ Гипотеза о кортежах, стр. 201–202.

[73] Сандифер 2007 , Глава 35, Оценка Базельской проблемы, стр. 205–208 .

[74] Огилви, CS ; Андерсон, Дж. Т. (1988). Экскурсии по теории чисел . Dover Publications Inc., стр. 29–35. ISBN 978-0-486-25778-5 .

[75] Апостол 1976 , раздел 1.6, теорема 1.13.

[76] Апостол 1976 , раздел 4.8, теорема 4.12.

[mtb-invitation-77] Перейти обратно: ^а ^б Миллер, Стивен Дж.; Таклу-Бигхаш, Рамин (2006). Приглашение к современной теории чисел . Издательство Принстонского университета. стр. 43–44. ISBN 978-0-691-12060-7 .

[78] Крэндалл и Померанс 2005 , с. 6 .

[79] Crandall & Pomerance 2005 , Раздел 3.7, Подсчет простых чисел, стр. 152–162 .

[cranpom10-80] Перейти обратно: ^а ^б Крэндалл и Померанс 2005 , с. 10 .

[81] дю Сотуа, Маркус (2011). «Какова вероятность того, что ваш номер телефона простой?» . Загадки чисел: математическая одиссея через повседневную жизнь . Пресса Святого Мартина. стр. 50–52. ISBN 978-0-230-12028-0 .

[82] Апостол 1976 , раздел 4.6, теорема 4.7.

[83] Гельфанд, ИМ ; Шен, Александр (2003). Алгебра . Спрингер. п. 37. ИСБН 978-0-8176-3677-7 .

[84] Моллин, Ричард А. (1997). Фундаментальная теория чисел с приложениями . Дискретная математика и ее приложения. ЦРК Пресс. п. 76. ИСБН 978-0-8493-3987-5 .

[85] Crandall & Pomerance 2005 , Теорема 1.1.5, с. 12 .

[86] Грин, Бен ; Тао, Теренс (2008). «Простые числа содержат сколь угодно длинные арифметические прогрессии». Анналы математики . 167 (2): 481–547. arXiv : math.NT/0404188 . дои : 10.4007/анналы.2008.167.481 . S2CID 1883951 .

[87] Хуа, Л.К. (2009) [1965]. Аддитивная теория простых чисел . Переводы математических монографий. Том. 13. Провиденс, Род-Айленд: Американское математическое общество. стр. 176–177. ISBN 978-0-8218-4942-2 . МР 0194404 . OCLC 824812353 .

[88] Последовательность этих простых чисел, начиная с $n=1$ скорее, чем $n=0$ , указан Лава, Паоло Пьетро; Бальзаротти, Джорджо (2010). «Глава 33. Формулы удачи» . 103 математических диковинки: Теория чисел, цифр и отношений в современной математике (на итальянском языке). Ulrico Hoepli Editore SpA с. 133. ИСБН 978-88-203-5804-4 .

[89] Чемберленд, Марк (2015). «Числа Хигнера» . Однозначные числа: во славу маленьких чисел . Издательство Принстонского университета. стр. 213–215. ISBN 978-1-4008-6569-7 .

[guy-a1-90] Перейти обратно: ^а ^б Гай, Ричард (2013). «А1 Простые значения квадратичных функций» . Нерешенные проблемы теории чисел . Задачи по математике (3-е изд.). Спрингер. стр. 7–10. ISBN 978-0-387-26677-0 .

[91] Паттерсон, С.Дж. (1988). Введение в теорию дзета-функции Римана . Кембриджские исследования по высшей математике. Том. 14. Издательство Кембриджского университета, Кембридж. п. 1. дои : 10.1017/CBO9780511623707 . ISBN 978-0-521-33535-5 . МР 0933558 .

[92] Борвейн, Питер ; Чой, Стивен; Руни, Брендан; Вайратмюллер, Андреа (2008). Гипотеза Римана: ресурс как для любителей, так и для виртуозов . Книги CMS по математике / Математические труды SMC. Нью-Йорк: Спрингер. стр. 100-1 10–11. дои : 10.1007/978-0-387-72126-2 . ISBN 978-0-387-72125-5 . МР 2463715 .

[93] Сандифер 2007 , стр. 191–193 .

[94] Борвейн и др. 2008 , Гипотеза 2.7 (гипотеза Римана), с. 15 .

[95] Паттерсон 1988 , с. 7.

[bcrw18-96] Перейти обратно: ^а ^б Борвейн и др. 2008 , с. 18.

[97] Натансон 2000 , Глава 9, Теорема о простых числах, стр. 289–324 .

[98] Загер, Дон (1977). «Первые 50 миллионов простых чисел». Математический интеллект . 1 (С2): 7–19. дои : 10.1007/bf03351556 . S2CID 37866599 . См. особенно стр. 14–16.

[99] Крафт и Вашингтон (2014) , Предложение 5.3 , с. 96.

[100] Шахриари, Шахриар (2017). Алгебра в действии: курс групп, колец и полей . Чистые и прикладные тексты для студентов. Том. 27. Американское математическое общество. стр. 20–21. ISBN 978-1-4704-2849-5 .

[101] Дадли 1978 , Теорема 3, с. 28 .

[102] Шахриари 2017 , стр. 27–28 .

[103] Рибенбойм 2004 , Маленькая теорема Ферма и примитивные корни по простому модулю, стр. 17–21.

[104] Рибенбойм 2004 , Собственность Джуги, стр. 21–22.

[105] Рибенбойм 2004 , Теорема Вильсона, с. 21.

[childress-106] Перейти обратно: ^а ^б ^с Чилдресс, Нэнси (2009). Теория полей классов . Университеттекст. Спрингер, Нью-Йорк. стр. 8–11. дои : 10.1007/978-0-387-72490-4 . ISBN 978-0-387-72489-8 . МР 2462595 . См. также стр. 64.

[107] Эриксон, Марти; Ваззана, Энтони; Гарт, Дэвид (2016). Введение в теорию чисел . Учебники по математике (2-е изд.). Бока-Ратон, Флорида: CRC Press. п. 200. ИСБН 978-1-4987-1749-6 . МР 3468748 .

[108] Вейль, Андре (1995). Основная теория чисел . Классика по математике. Берлин: Springer-Verlag. п. 43 . ISBN 978-3-540-58655-5 . МР 1344916 . Однако обратите внимание, что некоторые авторы, такие как Чилдресс (2009), вместо этого используют слово «место» для обозначения класса эквивалентности норм.

[109] Кох, Х. (1997). Алгебраическая теория чисел . Берлин: Springer Verlag. стр. 136. CiteSeerX 10.1.1.309.8812 . дои : 10.1007/978-3-642-58095-6 . ISBN 978-3-540-63003-6 . МР 1474965 .

[110] Лауритцен, Нильс (2003). Конкретная абстрактная алгебра: от чисел к базисам Грёбнера . Кембридж: Издательство Кембриджского университета. п. 127. дои : 10.1017/CBO9780511804229 . ISBN 978-0-521-53410-9 . МР 2014325 .

[111] Лауритцен 2003 , следствие 3.5.14, с. 133; Лемма 3.5.18, с. 136.

[112] Kraft & Washington 2014 , Раздел 12.1, Суммы двух квадратов, стр. 297–301 .

[113] Эйзенбуд, Дэвид (1995). Коммутативная алгебра . Тексты для аспирантов по математике. Том. 150. Берлин; Нью-Йорк: Springer-Verlag. Раздел 3.3. дои : 10.1007/978-1-4612-5350-1 . ISBN 978-0-387-94268-1 . МР 1322960 .

[114] Шафаревич, Игорь Робертович (2013). "Значение $\operatorname {Spec} A$ " . Основная алгебраическая геометрия 2: схемы и комплексные многообразия (3-е изд.). Springer, Heidelberg. стр. 5. doi : 10.1007/978-3-642-38010-5 . ISBN 978-3-642-38009-9 . МР 3100288 .

[115] Нойкирх, Юрген (1999). Алгебраическая теория чисел . Фундаментальные основы математических наук. Том 322. Берлин: Springer-Verlag. Раздел I.8, с. 50. дои : 10.1007/978-3-662-03983-0 . ISBN 978-3-540-65399-8 . МР 1697859 .

[116] Нойкирх 1999 , Раздел I.7, с. 38

[117] Стивенхаген, П.; Ленстра, Х.В. младший (1996). «Чеботарёв и его теорема плотности». Математический интеллект . 18 (2): 26–37. CiteSeerX 10.1.1.116.9409 . дои : 10.1007/BF03027290 . МР 1395088 . S2CID 14089091 .

[118] Холл, Маршалл (2018). Теория групп . Дуврские книги по математике. Публикации Курьера Дувра. ISBN 978-0-486-81690-6 . Теоремы Силова см. на с. 43; теорему Лагранжа см. на с. 12; теорему Бернсайда см. на стр. 143.

[119] Брайант, Джон; Сангвин, Кристофер Дж. (2008). Насколько кругл ваш круг?: Где встречаются инженерия и математика . Издательство Принстонского университета. п. 178 . ISBN 978-0-691-13118-4 .

[120] Харди, Годфри Гарольд (2012) [1940]. Извинение математика . Издательство Кембриджского университета. п. 140 . ISBN 978-0-521-42706-7 . OCLC 922010634 . Никто еще не обнаружил какой-либо военной цели, которой могла бы служить теория чисел или теория относительности, и маловероятно, что кто-нибудь сделает это в течение многих лет.

[121] Гиблин, Питер (1993). Простые числа и программирование . Издательство Кембриджского университета. п. 39 . ISBN 978-0-521-40988-9 .

[122] Апрель 1993 г. , с. 54

[p._220-123] Перейти обратно: ^а ^б Ризель 1994 , с. 220 .

[124] Буллинк, Мартен (2010). «История таблиц факторов с примечаниями о рождении теории чисел 1657–1817» . Revue d'Histoire des Mathématiques . 16 (2): 133–216.

[125] Вагстафф, Сэмюэл С. младший (2013). Радость факторинга . Студенческая математическая библиотека. Том. 68. Американское математическое общество. п. 191. ИСБН 978-1-4704-1048-3 .

[126] Крэндалл, Ричард ; Померанс, Карл (2005). Простые числа: вычислительная перспектива (2-е изд.). Спрингер. п. 121. ИСБН 978-0-387-25282-7 .

[127] Фарах-Колтон, Мартин ; Цай, Мэн-Цунг (2015). «О сложности вычисления таблиц простых чисел». В Эльбасиони Халед; Макино, Казухиса (ред.). Алгоритмы и вычисления: 26-й Международный симпозиум, ISAAC 2015, Нагоя, Япония, 9–11 декабря 2015 г., Труды . Конспекты лекций по информатике. Том. 9472. Спрингер. стр. 677–688. arXiv : 1504.05240 . дои : 10.1007/978-3-662-48971-0_57 . ISBN 978-3-662-48970-3 .

[128] Гривз, Джордж (2013). Сита в теории чисел . Итоги математики и ее границы (3-я серия). Том 43. Спрингер. п. 1. ISBN 978-3-662-04658-6 .

[hromkovic-129] Перейти обратно: ^а ^б Хромкович, Юрай (2001). «5.5 Библиографические примечания» . Алгоритмы решения сложных задач . Тексты по теоретической информатике. Серия EATCS. Шпрингер-Верлаг, Берлин. стр. 383–385. дои : 10.1007/978-3-662-04616-6 . ISBN 978-3-540-66860-2 . МР 1843669 . S2CID 31159492 .

[koblitz-131] Перейти обратно: ^а ^б Коблиц, Нил (1987). «Глава V. Простота и факторинг». Курс теории чисел и криптографии . Тексты для аспирантов по математике. Том. 114. Спрингер-Верлаг, Нью-Йорк. стр. 112–149. дои : 10.1007/978-1-4684-0310-7_5 . ISBN 978-0-387-96576-5 . МР 0910297 .

[132] Пепшик, Йозеф; Харджоно, Томас; Себерри, Дженнифер (2013). «2.3.9 Вероятностные расчеты» . Основы компьютерной безопасности . Спрингер. стр. 51–52. ISBN 978-3-662-07324-7 .

[tao-aks-133] Перейти обратно: ^а ^б Тао, Теренс (2010). «1.11 Тест на простоту АКС» . Эпсилон комнаты, II: Страницы третьего года математического блога . Аспирантура по математике. Том. 117. Провиденс, Род-Айленд: Американское математическое общество. стр. 82–86. дои : 10.1090/gsm/117 . ISBN 978-0-8218-5280-4 . МР 2780010 .

[atkin-morain-134] Перейти обратно: ^а ^б Аткин, А.Л .; Морейн, Ф. (1993). «Эллиптические кривые и доказательство простоты» (PDF) . Математика вычислений . 61 (203): 29–68. Бибкод : 1993MaCom..61...29A . дои : 10.1090/s0025-5718-1993-1199989-x . JSTOR 2152935 . МР 1199989 .

[morain-135] Перейти обратно: ^а ^б Морейн, Ф. (2007). «Реализация асимптотически быстрой версии алгоритма доказательства простоты эллиптической кривой». Математика вычислений . 76 (257): 493–505. arXiv : math/0502097 . Бибкод : 2007MaCom..76..493M . дои : 10.1090/S0025-5718-06-01890-4 . МР 2261033 . S2CID 133193 .

[137] Ленстра, Х.В. младший ; Померанс, Карл (2019). «Тестирование простоты с гауссовскими периодами» (PDF) . Журнал Европейского математического общества . 21 (4): 1229–1269. дои : 10.4171/JEMS/861 . hdl : 21.11116/0000-0005-717D-0 . МР 3941463 . S2CID 127807021 .

[PSW-138] Карл Померанс ; Джон Л. Селфридж ; Сэмюэл С. Вагстафф-младший (июль 1980 г.). «Псевдопростые числа до 25·10 ⁹ JSTOR (PDF) Математика вычислений . 35 (151): 1003–1026. doi : 10.1090/S0025-5718-1980-0572872-7 . 2006210 . .

[lpsp-139] Роберт Бэйли; Сэмюэл С. Вагстафф-младший (октябрь 1980 г.). «Лукас Псевдопраймс» (PDF) . Математика вычислений . 35 (152): 1391–1417. дои : 10.1090/S0025-5718-1980-0583518-6 . JSTOR 2006406 . МР 0583518 .

[monier-140] Перейти обратно: ^а ^б Монье, Луи (1980). «Оценка и сравнение двух эффективных алгоритмов вероятностного тестирования простоты» . Теоретическая информатика . 12 (1): 97–108. дои : 10.1016/0304-3975(80)90007-9 . МР 0582244 .

[141] Тао, Теренс (2009). «1.7 Критерий Лукаса-Лемера для простых чисел Мерсенна» . Наследие Пуанкаре, страницы второго года математического блога. Часть I. Провиденс, Род-Айленд: Американское математическое общество. стр. 36–41. ISBN 978-0-8218-4883-8 . МР 2523047 .

[142] Крафт и Вашингтон, 2014 , с. 41 .

[143] Например, см. Гай 2013 , Простые числа Мерсенна A3. Репуниты. Числа Ферма. Простые числа формы $k\cdot 2^{n}+1$ . стр. 13–21 .

[144] «Рекордное простое число из 12 миллионов цифр принесет приз в 100 000 долларов» . Фонд электронных границ. 14 октября 2009 года . Проверено 4 января 2010 г.

[145] «Награда EFF в области кооперативных вычислений» . Фонд электронных границ. 29 февраля 2008 г. Проверено 4 января 2010 г.

[146] «Подпроект PrimeGrid «Семнадцать или крах»» (PDF) . Проверено 03 января 2017 г.

[147] Колдуэлл, Крис К. «Двадцать лучших: самые большие известные простые числа» . Главные страницы . Проверено 03 января 2017 г.

[148] Колдуэлл, Крис К. «Двадцатка лучших: факториал» . Главные страницы . Проверено 03 января 2017 г.

[149] Рибенбойм 2004 , с. 4.

[151] Колдуэлл, Крис К. «Двадцатка лучших: первобытные» . Главные страницы . Проверено 03 января 2017 г.

[152] Колдуэлл, Крис К. «Двадцатка лучших: простые числа-близнецы» . Главные страницы . Проверено 03 января 2017 г.

[153] Крафт и Вашингтон, 2014 , с. 275 .

[154] Хоффштейн, Джеффри; Пайфер, Джилл ; Сильверман, Джозеф Х. (2014). Введение в математическую криптографию . Тексты для студентов по математике (2-е изд.). Спрингер. п. 329. ИСБН 978-1-4939-1711-2 .

[155] Померанс, Карл (1996). «Сказка о двух решетах». Уведомления Американского математического общества . 43 (12): 1473–1485. МР 1416721 .

[156] Эммануэль Томе, «795-битный факторинг и дискретные логарифмы», 2 декабря 2019 г.

[157] Риффель, Элеонора Г .; Полак, Вольфганг Х. (2011). «Глава 8. Алгоритм Шора» . Квантовые вычисления: краткое введение . МТИ Пресс. стр. 163–176. ISBN 978-0-262-01506-6 .

[158] Мартин-Лопес, Энрике; Лэнг, Энтони; Лоусон, Томас; Альварес, Роберто; Чжоу, Сяо-Ци; О'Брайен, Джереми Л. (12 октября 2012 г.). «Экспериментальная реализация алгоритма квантового факторинга Шора с использованием переработки кубитов». Природная фотоника . 6 (11): 773–776. arXiv : 1111.4147 . Бибкод : 2012NaPho...6..773M . дои : 10.1038/nphoton.2012.259 . S2CID 46546101 .

[159] Чиргвин, Ричард (9 октября 2016 г.). «Криптовалюте необходимо больше прозрачности, предупреждают исследователи» . Регистр .

[160] Hoffstein, Pipher & Silverman 2014 , Раздел 2.3, Обмен ключами Диффи-Хеллмана, стр. 65–67.

[161] Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Штейн, Клиффорд (2001) [1990]. «11.3 Универсальное хеширование». Введение в алгоритмы (2-е изд.). MIT Press и McGraw-Hill. стр. 232–236. ISBN 0-262-03293-7 . Для $k$ -независимое хеширование см. задачу 11–4, с. 251. Благодарность Картеру и Вегману см. в примечаниях к главе, стр. 252.

[162] Гудрич, Майкл Т .; Тамассия, Роберт (2006). Структуры данных и алгоритмы в Java (4-е изд.). Джон Уайли и сыновья. ISBN 978-0-471-73884-8 . См. «Квадратичное измерение», с. 382 и упражнение С–9.9, с. 415.

[163] Киртланд, Джозеф (2001). Идентификационные номера и схемы контрольных цифр . Ресурсы для классных комнат. Том. 18. Математическая ассоциация Америки. стр. 43–44. ISBN 978-0-88385-720-5 .

[164] Дойч, П. (май 1996 г.). Спецификация формата сжатых данных ZLIB, версия 3.3 . Сетевая рабочая группа. дои : 10.17487/RFC1950 . РФК 1950 .

[165] Кнут, Дональд Э. (1998). «3.2.1 Линейная конгруэнтная модель». Искусство компьютерного программирования, Том. 2: Получисловые алгоритмы (3-е изд.). Аддисон-Уэсли. стр. 10–26. ISBN 978-0-201-89684-8 .

[166] Мацумото, Макото; Нисимура, Такудзи (1998). «Mersenne Twister: 623-мерный равнораспределенный равномерный генератор псевдослучайных чисел». ACM-транзакции по моделированию и компьютерному моделированию . 8 (1): 3–30. CiteSeerX 10.1.1.215.1141 . дои : 10.1145/272991.272995 . S2CID 3332028 .

[167] Рот, К.Ф. (1951). «О проблеме Гейльбронна». Журнал Лондонского математического общества . Вторая серия. 26 (3): 198–204. дои : 10.1112/jlms/s1-26.3.198 . МР 0041889 .

[168] Кокс, Дэвид А. (2011). «Почему Эйзенштейн доказал критерий Эйзенштейна и почему Шенеман открыл его первым» (PDF) . Американский математический ежемесячник . 118 (1): 3–31. CiteSeerX 10.1.1.398.3440 . doi : 10.4169/amer.math.monthly.118.01.003 . S2CID 15978494 .

[169] Ланг, Серж (2002). Алгебра . Тексты для аспирантов по математике. Том. 211. Берлин; Нью-Йорк: Springer-Verlag . дои : 10.1007/978-1-4613-0041-0 . ISBN 978-0-387-95385-4 . МР 1878556 . , раздел II.1, с. 90

[170] Шуберт, Хорст (1949). «Уникальная разложимость узла на простые узлы». С.-Б Гейдельбергер Акад. Матем.-Нац. кл . 1949 (3): 57–104. МР 0031733 .

[171] Милнор, Дж. (1962). «Единственная теорема о разложении трехмерных многообразий». Американский журнал математики . 84 (1): 1–7. дои : 10.2307/2372800 . JSTOR 2372800 . МР 0142125 .

[172] Боклан и Конвей (2017) также включают $2^{0}+1=2$ , который не имеет этой формы.

[kls-173] Перейти обратно: ^а ^б Кржижек, Михал; Лука, Флориан; Сомер, Лоуренс (2001). 17 лекций о числах Ферма: от теории чисел к геометрии . Книги CMS по математике. Том. 9. Нью-Йорк: Спрингер-Верлаг. стр. 1–2. дои : 10.1007/978-0-387-21850-2 . ISBN 978-0-387-95332-8 . МР 1866957 .

[174] Боклан, Кент Д.; Конвей, Джон Х. (январь 2017 г.). «Ожидайте не более одной миллиардной части нового простого числа Ферма ! ». Математический интеллект . 39 (1): 3–5. arXiv : 1605.01371 . дои : 10.1007/s00283-016-9644-3 . S2CID 119165671 .

[175] Глисон, Эндрю М. (1988). «Трисекция угла, семиугольник и трискайдекагон». Американский математический ежемесячник . 95 (3): 185–194. дои : 10.2307/2323624 . JSTOR 2323624 . МР 0935432 .

[176] Циглер, Гюнтер М. (2015). «Пушки по воробьям». Информационный бюллетень Европейского математического общества (95): 25–31. МР 3330472 .

[177] Петерсон, Иварс (28 июня 1999 г.). «Возвращение Зеты» . МАА Онлайн . Архивировано из оригинала 20 октября 2007 года . Проверено 14 марта 2008 г.

[178] Хейс, Брайан (2003). «Информатика: спектр римания». Американский учёный . 91 (4): 296–300. дои : 10.1511/2003.26.3349 . JSTOR 27858239 . S2CID 16785858 .

[179] Бенгтссон, Ингемар; Жичковский, Кароль (2017). Геометрия квантовых состояний: введение в квантовую запутанность (второе изд.). Кембридж: Издательство Кембриджского университета . стр. 313–354. ISBN 978-1-107-02625-4 . OCLC 967938939 .

[180] Чжу, Хуанцзюнь (2010). «SIC POVM и группы Клиффорда в простых измерениях» . Физический журнал A: Математический и теоретический . 43 (30): 305305. arXiv : 1003.3591 . Бибкод : 2010JPhA...43D5305Z . дои : 10.1088/1751-8113/43/30/305305 . S2CID 118363843 .

[181] Гоулс, Э.; Шульц, О.; Маркус, М. (2001). «Выбор простых чисел циклов в модели хищник-жертва». Сложность . 6 (4): 33–38. Бибкод : 2001Cmplx...6d..33G . дои : 10.1002/cplx.1040 .

[182] Кампос, Пауло Р.А.; де Оливейра, Вивиан М.; Джиро, Роналду; Гальвао, Дуглас С. (2004). «Появление простых чисел как результат эволюционной стратегии». Письма о физических отзывах . 93 (9): 098107. arXiv : q-bio/0406017 . Бибкод : 2004PhRvL..93i8107C . doi : 10.1103/PhysRevLett.93.098107 . ПМИД 15447148 . S2CID 88332 .

[183] «Нашествие выводка» . Экономист . 6 мая 2004 года . Проверено 26 ноября 2006 г.

[184] Циммер, Карл (15 мая 2015 г.). «Бамбуковые математики» . Феномены: Ткацкий станок. Национальная география . Проверено 22 февраля 2018 г.

[185] Хилл, Питер Дженсен, изд. (1995). Спутник Мессиана . Портленд, Орегон: Amadeus Press. Бывший. 13.2 Месса Пятидесятницы 1 «Вход». ISBN 978-0-931340-95-6 .

[186] Померанс, Карл (2004). «Простые числа и поиск внеземного разума» (PDF) . В Хейсе, Дэвид Ф.; Росс, Питер (ред.). Математические приключения для школьников и любителей . МАА Спектр. Вашингтон, округ Колумбия: Математическая ассоциация Америки. стр. 3–6. ISBN 978-0-88385-548-5 . МР 2085842 .

[187] GrrlScientist (16 сентября 2010 г.). «Загадочное ночное происшествие с собакой» . Наука. Хранитель . Проверено 22 февраля 2010 г.

[188] Шиллингер, Лизл (9 апреля 2010 г.). «Рассчитываем друг на друга» . Воскресное книжное обозрение. Нью-Йорк Таймс .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[а]

[29]

[б]

[32]

[33]

[34]

[35]

[36]

[37]

[38]

[39]

[40]

[41]

[42]

[43]

[44]

[45]

[46]

[47]

[48]

[49]

[50]

[51]

[52]

[53]

[54]

[55]

[56]

[57]

[58]

[59]

[60]

[61]

[62]

[63]

[64]

[65]

[66]

[67]

[68]

[69]

[70]

[71]

[72]

[73]

[74]

[75]

[76]

[77]

[78]

[79]

[80]

[81]

[82]

[83]

[84]

[85]

[86]

[87]

[88]

[89]

[90]

[91]

[92]

[93]

[94]

[95]

[96]

[97]

[98]

[99]

[100]

[101]

Базы данных авторитетного контроля
International	FAST
National	France BnF data Germany Israel United States Latvia Japan Czech Republic

v т Это Теория чисел
Fields	Algebraic number theory (class field theory, non-abelian class field theory, Iwasawa theory, Iwasawa–Tate theory, Kummer theory) Analytic number theory (analytic theory of L-functions, probabilistic number theory, sieve theory) Geometric number theory Computational number theory Transcendental number theory Diophantine geometry (Arakelov theory, Hodge–Arakelov theory) Arithmetic combinatorics (additive number theory) Arithmetic geometry (anabelian geometry, P-adic Hodge theory) Arithmetic topology Arithmetic dynamics
Key concepts	Numbers 0 Natural numbers Unity Prime numbers Composite numbers Rational numbers Irrational numbers Algebraic numbers Transcendental numbers P-adic numbers (P-adic analysis) Arithmetic Modular arithmetic Chinese remainder theorem Arithmetic functions
Advanced concepts	Quadratic forms Modular forms L-functions Diophantine equations Diophantine approximation Continued fractions
Category List of topics List of recreational topics Wikibook Wikiversity

v т Это Наборы целых чисел на основе делимости
Overview	Integer factorization Divisor Unitary divisor Divisor function Prime factor Fundamental theorem of arithmetic
Factorization forms	Prime Composite Semiprime Pronic Sphenic Square-free Powerful Perfect power Achilles Smooth Regular Rough Unusual
Constrained divisor sums	Perfect Almost perfect Quasiperfect Multiply perfect Hemiperfect Hyperperfect Superperfect Unitary perfect Semiperfect Practical Erdős–Nicolas
With many divisors	Abundant Primitive abundant Highly abundant Superabundant Colossally abundant Highly composite Superior highly composite Weird
Aliquot sequence-related	Untouchable Amicable (Triple) Sociable Betrothed
Base-dependent	Equidigital Extravagant Frugal Harshad Polydivisible Smith
Other sets	Arithmetic Deficient Friendly Solitary Sublime Harmonic divisor Descartes Refactorable Superperfect

v т Это простых чисел Классы
By formula	Fermat ( $2 2 n + 1$ ) Mersenne ( $2 p - 1$ ) Double Mersenne ( $2 2 p -1 - 1$ ) Wagstaff $(2 p + 1)/3$ Proth ( $k \cdot2 n + 1$ ) Factorial ( $n! \pm 1$ ) Primorial ( $p n # \pm 1$ ) Euclid ( $p n # + 1$ ) Pythagorean ( $4 n + 1$ ) Pierpont ( $2 m \cdot3 n + 1$ ) Quartan ( $x 4 + y 4$ ) Solinas ( $2 m \pm 2 n \pm 1$ ) Cullen ( $n \cdot2 n + 1$ ) Woodall ( $n \cdot2 n - 1$ ) Cuban ( $x 3 - y 3)/(x - y$ ) Leyland ( $x y + y x$ ) Thabit ( $3\cdot2 n - 1$ ) Williams ( $(b -1)\cdot b n - 1$ ) Mills ( $⌊ A 3 n ⌋$ )
By integer sequence	Fibonacci Lucas Pell Newman–Shanks–Williams Perrin
By property	Wieferich (pair) Wall–Sun–Sun Wolstenholme Wilson Lucky Fortunate Ramanujan Pillai Regular Strong Stern Supersingular (elliptic curve) Supersingular (moonshine theory) Good Super Higgs Highly cototient Unique
Base-dependent	Palindromic Emirp Repunit $(10 n - 1)/9$ Permutable Circular Truncatable Minimal Delicate Primeval Full reptend Unique Happy Self Smarandache–Wellin Strobogrammatic Dihedral Tetradic
Patterns	Twin ( $p, p + 2$ ) Bi-twin chain ( $n \pm 1, 2 n \pm 1, 4 n \pm 1, \dots$ ) Triplet ( $p, p + 2 or p + 4, p + 6$ ) Quadruplet ( $p, p + 2, p + 6, p + 8$ ) k-tuple Cousin ( $p, p + 4$ ) Sexy ( $p, p + 6$ ) Chen Sophie Germain/Safe ( $p, 2 p + 1$ ) Cunningham ( $p, 2 p \pm 1, 4 p \pm 3, 8 p \pm 7, ...$ ) Arithmetic progression ( $p + a\cdotn, n = 0, 1, 2, 3, ...$ ) Balanced ( $consecutive p - n, p, p + n$ )
By size	Mega (1,000,000+ digits) Largest known list
Complex numbers	Eisenstein prime Gaussian prime
Composite numbers	Pseudoprime Catalan Elliptic Euler Euler–Jacobi Fermat Frobenius Lucas Perrin Somer–Lucas Strong Carmichael number Almost prime Semiprime Sphenic number Interprime Pernicious
Related topics	Probable prime Industrial-grade prime Illegal prime Formula for primes Prime gap
First 60 primes	2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281
List of prime numbers