Простое число - Prime number

"Prime" перенаправляется сюда. Для использования в других целях см. Prime (значения).

Составные числа можно расположить в прямоугольники, но простые числа нельзя.

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

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

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

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

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

Основная статья: Список простых чисел

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

Демонстрация с Удилища Cuisenaire, что 7 простое число, потому что ни одно из чисел 2, 3, 4, 5 или 6 не делит его равномерно

В делители натурального числа ${\displaystyle n}$ натуральные числа, которые делят ${\displaystyle n}$ Любое натуральное число имеет как 1, так и само себя в качестве делителя. Если у него есть другой делитель, он не может быть простым. Эта идея приводит к другому, но эквивалентному определению простых чисел: это числа с ровно двумя положительными делители, 1 и само число.^[6]Еще один способ выразить то же самое - число ${\displaystyle n}$ является простым, если оно больше единицы и если ни одно из чисел ${\displaystyle 2,3,\dots ,n-1}$ разделяет ${\displaystyle 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 ).

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

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

История

В Математический папирус Райнда

В Математический папирус Райнда, примерно с 1550 г. до н.э. Египетская фракция разложения разных форм для простых и составных чисел.^[13] Однако самые ранние сохранившиеся записи явного изучения простых чисел происходят из древнегреческая математика. Евклид с Элементы (ок. 300 г. до н.э.) доказывает бесконечность простых чисел и основная теорема арифметики, и показывает, как построить идеальное число из Мерсенн прайм.^[14] Еще одно греческое изобретение, Сито Эратосфена, до сих пор используется для построения списков простых чисел.^[15][16]

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

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

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

С 1951 года все самые большие известные простые числа были обнаружены с помощью этих тестов на компьютеры.^[а] Поиск все более крупных простых чисел вызвал интерес за пределами математических кругов благодаря Отличный Интернет-поиск Mersenne Prime и другие распределенных вычислений проекты.^[8][28] Идея о том, что простые числа имеют мало приложений за пределами чистая математика^[b] был разрушен в 1970-х, когда криптография с открытым ключом и ЮАР криптосистема была изобретена, взяв за основу простые числа.^[31]

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

Первобытность одного

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

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

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

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

Основная статья: Основная теорема арифметики

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

${\displaystyle {\begin{aligned}34866&=2\cdot 3\cdot 3\cdot 13\cdot 149\\&=2\cdot 3^{2}\cdot 13\cdot 149.\end{aligned}}}$

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

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

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

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

Основная статья: Теорема евклида

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

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

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

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

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

По основной теореме ${\displaystyle N}$ имеет разложение на простые множители

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

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

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

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

- составное число.

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

Основная статья: Формула для простых чисел

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

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

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

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

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

Дальнейшая информация: Категория: Домыслы о простых числах

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

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

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

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

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

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

${\displaystyle p(n)=a+bn}$

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

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

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

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

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

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

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

${\displaystyle \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 ,}$

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

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

Основные статьи: Теорема о простых числах и Функция подсчета простых чисел

В относительная ошибка из ${\displaystyle {\tfrac {n}{\log n}}}$ и логарифмический интеграл ${\displaystyle \operatorname {Li} (n)}$ как приближения к функция подсчета простых чисел. Обе относительные ошибки уменьшаются до нуля при ${\displaystyle n}$ растет, но сходимость к нулю для логарифмического интеграла происходит гораздо быстрее.

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

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

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

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

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

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

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

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

${\displaystyle a,a+q,a+2q,a+3q,\dots }$

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

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

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

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

В Спираль Улама. Простые числа (красные) сгруппированы на одних диагоналях, а на других нет. Основные ценности ${\displaystyle 4n^{2}-2n+41}$ показаны синим цветом.

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

${\displaystyle n^{2}-n+41}$

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

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

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

Основная статья: Гипотеза Римана

График абсолютных значений дзета-функции, показывающий некоторые ее особенности

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

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

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

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

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

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

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

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

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

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

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

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

Основная статья: p-адическое число

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

Эта картина порядка, абсолютного значения и полного поля, полученного из них, может быть обобщена на поля алгебраических чисел и их оценки (определенные отображения из мультипликативная группа поля на полностью упорядоченная аддитивная группа, также называемые заказами), абсолютные значения (определенные мультипликативные отображения поля в действительные числа, также называемые нормами),^[103] и места (расширения заполненные поля в котором данное поле является плотный набор, также называемые доработками).^[105] Продолжение рациональных чисел до действительные числа, например, это место, в котором расстояние между числами обычное абсолютная величина об их различии. Соответствующим отображением в аддитивную группу будет логарифм абсолютной стоимости, хотя это не отвечает всем требованиям оценки. В соответствии с Теорема Островского, с точностью до естественного понятия эквивалентности действительные числа и ${\displaystyle p}$-адические числа с их порядками и абсолютными значениями - единственные оценки, абсолютные значения и места в рациональных числах.^[103] В локально-глобальный принцип позволяет решать определенные проблемы, связанные с рациональными числами, собирая вместе решения с каждого из их мест, что еще раз подчеркивает важность простых чисел для теории чисел.^[106]

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

Основные статьи: Главный элемент и Неприводимый элемент

В Простые числа Гаусса при норме менее 500

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

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

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

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

Основные идеалы

Основная статья: Основные идеалы

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

В спектр кольца - геометрическое пространство, точками которого являются первичные идеалы кольца.^[111] Арифметическая геометрия также извлекает пользу из этого понятия, и многие концепции существуют как в геометрии, так и в теории чисел. Например, факторизация или разветвление главных идеалов, когда их возносят к поле расширения, основная проблема алгебраической теории чисел, имеет некоторое сходство с разветвление в геометрии. Эти концепции могут даже помочь в вопросах теории чисел, связанных исключительно с целыми числами. Например, главные идеалы в кольцо целых чисел из поля квадратичных чисел can be used in proving квадратичная взаимность, a statement that concerns the existence of square roots modulo integer prime numbers.^[112]Early attempts to prove Последняя теорема Ферма привело к Куммер введение regular primes, integer prime numbers connected with the failure of unique factorization in the cyclotomic integers.^[113]The question of how many integer prime numbers factor into a product of multiple prime ideals in an algebraic number field is addressed by Теорема плотности Чеботарева, which (when applied to the cyclotomic integers) has Dirichlet's theorem on primes in arithmetic progressions as a special case.^[114]

Теория групп

В теории конечные группы то Теоремы Силова imply that, if a power of a prime number ${\displaystyle p^{n}}$ разделяет order of a group, then the group has a subgroup of order ${\displaystyle p^{n}}$. К Lagrange's theorem, any group of prime order is a циклическая группа,and by Burnside's theorem any group whose order is divisible by only two primes is разрешимый.^[115]

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

The small gear in this piece of farm equipment has 13 teeth, a prime number, and the middle gear has 21, relatively prime to 13

For a long time, number theory in general, and the study of prime numbers in particular, was seen as the canonical example of pure mathematics, with no applications outside of mathematics^[b] other than the use of prime numbered gear teeth to distribute wear evenly.^[116] In particular, number theorists such as Британский математик Г. Х. Харди prided themselves on doing work that had absolutely no military significance.^[117]

This vision of the purity of number theory was shattered in the 1970s, when it was publicly announced that prime numbers could be used as the basis for the creation of криптография с открытым ключом алгоритмы.^[31]These applications have led to significant study of алгоритмы for computing with prime numbers, and in particular of primality testing, methods for determining whether a given number is prime.The most basic primality testing routine, trial division, is too slow to be useful for large numbers. One group of modern primality tests is applicable to arbitrary numbers, while more efficient tests are available for numbers of special types. Most primality tests only tell whether their argument is prime or not. Routines that also provide a prime factor of composite arguments (or all of its prime factors) are called факторизация algorithms.Prime numbers are also used in computing for контрольные суммы, hash tables, и генераторы псевдослучайных чисел.

Пробный отдел

Основная статья: Пробный отдел

The most basic method of checking the primality of a given integer ${\displaystyle n}$ называется судебное отделение. This method divides ${\displaystyle n}$ by each integer from 2 up to the квадратный корень из ${\displaystyle n}$. Any such integer dividing ${\displaystyle n}$ evenly establishes ${\displaystyle n}$ as composite; otherwise it is prime.Integers larger than the square root do not need to be checked because, whenever ${\displaystyle n=a\cdot b}$, one of the two factors ${\displaystyle a}$ и ${\displaystyle b}$ is less than or equal to the квадратный корень из ${\displaystyle n}$. Another optimization is to check only primes as factors in this range.^[118]For instance, to check whether 37 is prime, this method divides it by the primes in the range from 2 to √37, which are 2, 3, and 5. Each division produces a nonzero remainder, so 37 is indeed prime.

Although this method is simple to describe, it is impractical for testing the primality of large integers, because the number of tests that it performs grows exponentially as a function of the number of digits of these integers.^[119] However, trial division is still used, with a smaller limit than the square root on the divisor size, to quickly discover composite numbers with small factors, before using more complicated methods on the numbers that pass this filter.^[120]

Сита

В sieve of Eratosthenes starts with all numbers unmarked (gray). It repeatedly finds the first unmarked number, marks it as prime (dark colors) and marks its square and all later multiples as composite (lighter colors). After marking the multiples of 2 (red), 3 (green), 5 (blue), and 7 (yellow), all primes up to the square root of the table size have been processed, and all remaining unmarked numbers (11, 13, etc.) are marked as primes (magenta).

Основная статья: Сито Эратосфена

Before computers, mathematical tables listing all of the primes or prime factorizations up to a given limit were commonly printed.^[121] The oldest method for generating a list of primes is called the sieve of Eratosthenes.^[122] The animation shows an optimized variant of this method.^[123]Another more asymptotically efficient sieving method for the same problem is the сито Аткина.^[124] In advanced mathematics, sieve theory applies similar methods to other problems.^[125]

Primality testing versus primality proving

Some of the fastest modern tests for whether an arbitrary given number ${\displaystyle n}$ is prime are вероятностный (или же Монте-Карло ) algorithms, meaning that they have a small random chance of producing an incorrect answer.^[126]Например, Тест на простоту Соловея – Штрассена on a given number ${\displaystyle p}$ chooses a number ${\displaystyle a}$ случайно из ${\displaystyle 2}$ через ${\displaystyle p-2}$ и использует modular exponentiation to checkwhether ${\displaystyle a^{(p-1)/2}\pm 1}$ делится на ${\displaystyle p}$.^[c] If so, it answers yes and otherwise it answers no. Если ${\displaystyle p}$ really is prime, it will always answer yes, but if ${\displaystyle p}$ is composite then it answers yes with probability at most 1/2 and no with probability at least 1/2.^[127]If this test is repeated ${\displaystyle n}$ times on the same number,the probability that a composite number could pass the test every time is at most ${\displaystyle 1/2^{n}}$. Because this decreases exponentially with the number of tests, it provides high confidence (although not certainty) that a number that passes the repeated test is prime. On the other hand, if the test ever fails, then the number is certainly composite.^[128]A composite number that passes such a test is called a pseudoprime.^[127]

In contrast, some other algorithms guarantee that their answer will always be correct: primes will always be determined to be prime and composites will always be determined to be composite.For instance, this is true of trial division.The algorithms with guaranteed-correct output include both deterministic (non-random) algorithms, such as the Тест на простоту AKS,^[129]and randomized Las Vegas algorithms where the random choices made by the algorithm do not affect its final answer, such as some variations of elliptic curve primality proving.^[126]When the elliptic curve method concludes that a number is prime, it provides primality certificate that can be verified quickly.^[130]The elliptic curve primality test is the fastest in practice of the guaranteed-correct primality tests, but its runtime analysis is based on heuristic arguments rather than rigorous proofs. В Тест на простоту AKS has mathematically proven time complexity, but is slower than elliptic curve primality proving in practice.^[131] These methods can be used to generate large random prime numbers, by generating and testing random numbers until finding one that is prime;when doing this, a faster probabilistic test can quickly eliminate most composite numbers before a guaranteed-correct algorithm is used to verify that the remaining numbers are prime.^[d]

The following table lists some of these tests. Their running time is given in terms of ${\displaystyle n}$, the number to be tested and, for probabilistic algorithms, the number ${\displaystyle k}$ of tests performed. Более того, ${\displaystyle \varepsilon }$ is an arbitrarily small positive number, and log is the логарифм to an unspecified base. В нотация большой O means that each time bound should be multiplied by a constant factor to convert it from dimensionless units to units of time; this factor depends on implementation details such as the type of computer used to run the algorithm, but not on the input parameters ${\displaystyle n}$ и ${\displaystyle k}$.

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

Special-purpose algorithms and the largest known prime

Дальнейшая информация: Список простых чисел

In addition to the aforementioned tests that apply to any natural number, some numbers of a special form can be tested for primality more quickly.For example, the Тест на простоту Лукаса-Лемера can determine whether a Число Мерсенна (one less than a сила двух ) is prime, deterministically,in the same time as a single iteration of the Miller–Rabin test.^[136] This is why since 1992 (as of December 2018^{[Обновить]}) самый большой известен основной has always been a Mersenne prime.^[137]It is conjectured that there are infinitely many Mersenne primes.^[138]

The following table gives the largest known primes of various types. Some of these primes have been found using распределенных вычислений. В 2009 г. Отличный Интернет-поиск Mersenne Prime project was awarded a US$100,000 prize for first discovering a prime with at least 10 million digits.^[139] В Фонд электронных рубежей also offers $150,000 and $250,000 for primes with at least 100 million digits and 1 billion digits, respectively.^[140]

Тип	основной	Number of decimal digits	Дата	Найдено
Мерсенн прайм	2^82,589,933 − 1	24,862,048	7 декабря 2018 г.[1]	Patrick Laroche, Отличный Интернет-поиск Mersenne Prime
Proth Prime	10,223 × 2^31,172,165 + 1	9,383,761	31 октября 2016 г.[141]	Péter Szabolcs, PrimeGrid[142]
факториальное простое число	208,003! − 1	1,015,843	Июль 2016	Sou Fukui[143]
primorial prime[e]	1,098,133# − 1	476,311	Март 2012 г.	James P. Burt, PrimeGrid[145]
простые числа-близнецы	2,996,863,034,895  × 2^1,290,000 ± 1	388,342	Сентябрь 2016	Tom Greer, PrimeGrid[146]

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

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

Given a composite integer ${\displaystyle n}$, the task of providing one (or all) prime factors is referred to as факторизация из ${\displaystyle n}$. It is significantly more difficult than primality testing,^[147] and although many factorization algorithms are known, they are slower than the fastest primality testing methods. Trial division and Алгоритм ро Полларда can be used to find very small factors of ${\displaystyle n}$,^[120] и elliptic curve factorization can be effective when ${\displaystyle n}$ has factors of moderate size.^[148] Methods suitable for arbitrary large numbers that do not depend on the size of its factors include the quadratic sieve и general number field sieve. As with primality testing, there are also factorization algorithms that require their input to have a special form, including the special number field sieve.^[149] По состоянию на декабрь 2019 г.^{[Обновить]} то largest number known to have been factored by a general-purpose algorithm is RSA-240, which has 240 decimal digits (795 bits) and is the product of two large primes.^[150]

Алгоритм Шора can factor any integer in a polynomial number of steps on a квантовый компьютер.^[151] However, current technology can only run this algorithm for very small numbers. As of October 2012^{[Обновить]} the largest number that has been factored by a quantum computer running Shor's algorithm is 21.^[152]

Other computational applications

Несколько криптография с открытым ключом алгоритмы, такие как ЮАР и Обмен ключами Диффи – Хеллмана, are based on large prime numbers (2048-кусочек primes are common).^[153] RSA relies on the assumption that it is much easier (that is, more efficient) to perform the multiplication of two (large) numbers ${\displaystyle x}$ и ${\displaystyle y}$ than to calculate ${\displaystyle x}$ и ${\displaystyle y}$ (assumed совмещать ) if only the product ${\displaystyle xy}$ известен.^[31] The Diffie–Hellman key exchange relies on the fact that there are efficient algorithms for modular exponentiation (computing ${\displaystyle a^{b}{\bmod {c}}}$), while the reverse operation (the discrete logarithm ) is thought to be a hard problem.^[154]

Prime numbers are frequently used for hash tables. For instance the original method of Carter and Wegman for universal hashing was based on computing хэш-функции by choosing random linear functions modulo large prime numbers. Carter and Wegman generalized this method to ${\displaystyle k}$-независимое хеширование by using higher-degree polynomials, again modulo large primes.^[155] As well as in the hash function, prime numbers are used for the hash table size in quadratic probing based hash tables to ensure that the probe sequence covers the whole table.^[156]

Немного контрольная сумма methods are based on the mathematics of prime numbers. For instance the checksums used in International Standard Book Numbers are defined by taking the rest of the number modulo 11, a prime number. Because 11 is prime this method can detect both single-digit errors and transpositions of adjacent digits.^[157] Another checksum method, Адлер-32, uses arithmetic modulo 65521, the largest prime number less than ${\displaystyle 2^{16}}$.^[158]Prime numbers are also used in генераторы псевдослучайных чисел включая linear congruential generators^[159] и Мерсенн Твистер.^[160]

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

Prime numbers are of central importance to number theory but also have many applications to other areas within mathematics, including абстрактная алгебра and elementary geometry. For example, it is possible to place prime numbers of points in a two-dimensional grid so that no three are in a line, or so that every triangle formed by three of the points has large area.^[161] Другой пример Eisenstein's criterion, a test for whether a polynomial is irreducible based on divisibility of its coefficients by a prime number and its square.^[162]

The connected sum of two prime knots

The concept of prime number is so important that it has been generalized in different ways in various branches of mathematics. Generally, "prime" indicates minimality or indecomposability, in an appropriate sense. Например, основное поле of a given field is its smallest subfield that contains both 0 and 1. It is either the field of rational numbers or a конечное поле with a prime number of elements, whence the name.^[163] Often a second, additional meaning is intended by using the word prime, namely that any object can be, essentially uniquely, decomposed into its prime components. Например, в теория узлов, а prime knot это knot that is indecomposable in the sense that it cannot be written as the связанная сумма of two nontrivial knots. Any knot can be uniquely expressed as a connected sum of prime knots.^[164] В prime decomposition of 3-manifolds is another example of this type.^[165]

Beyond mathematics and computing, prime numbers have potential connections to квантовая механика, and have been used metaphorically in the arts and literature. Они также использовались в эволюционная биология to explain the life cycles of цикады.

Constructible polygons and polygon partitions

Construction of a regular pentagon using straightedge and compass. This is only possible because 5 is a Ферма Прайм.

Простые числа Ферма are primes of the form

${\displaystyle F_{k}=2^{2^{k}}+1,}$

с ${\displaystyle k}$ а неотрицательное целое число.^[166] Они названы в честь Пьер де Ферма, who conjectured that all such numbers are prime. The first five of these numbers – 3, 5, 17, 257, and 65,537 – are prime,^[167] но ${\displaystyle F_{5}}$ is composite and so are all other Fermat numbers that have been verified as of 2017.^[168] А обычный ${\displaystyle n}$-угольник является constructible using straightedge and compass if and only if the odd prime factors of ${\displaystyle n}$ (if any) are distinct Fermat primes.^[167] Likewise, a regular ${\displaystyle n}$-gon may be constructed using straightedge, compass, and an angle trisector if and only if the prime factors of ${\displaystyle n}$ are any number of copies of 2 or 3 together with a (possibly empty) set of distinct Простые числа Пьерпона, primes of the form ${\displaystyle 2^{a}3^{b}+1}$.^[169]

It is possible to partition any convex polygon into ${\displaystyle n}$ smaller convex polygons of equal area and equal perimeter, when ${\displaystyle n}$ это power of a prime number, but this is not known for other values of ${\displaystyle n}$.^[170]

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

Beginning with the work of Хью Монтгомери и Фриман Дайсон in the 1970s, mathematicians and physicists have speculated that the zeros of the Riemann zeta function are connected to the energy levels of quantum systems.^[171][172] Prime numbers are also significant in quantum information science, thanks to mathematical structures such as mutually unbiased bases и symmetric informationally complete positive-operator-valued measures.^[173][174]

Биология

The evolutionary strategy used by цикады рода Magicicada makes use of prime numbers.^[175] These insects spend most of their lives as личинки под землей. They only pupate and then emerge from their burrows after 7, 13 or 17 years, at which point they fly about, breed, and then die after a few weeks at most. Biologists theorize that these prime-numbered breeding cycle lengths have evolved in order to prevent predators from synchronizing with these cycles.^[176][177]In contrast, the multi-year periods between flowering in бамбук plants are hypothesized to be smooth numbers, having only small prime numbers in their factorizations.^[178]

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

Prime numbers have influenced many artists and writers.The French композитор Оливье Мессиан used prime numbers to create ametrical music through "natural phenomena". В таких произведениях, как La Nativité du Seigneur (1935) и Quatre études de rythme (1949–50), he simultaneously employs motifs with lengths given by different prime numbers to create unpredictable rhythms: the primes 41, 43, 47 and 53 appear in the third étude, "Neumes rythmiques". According to Messiaen this way of composing was "inspired by the movements of nature, movements of free and unequal durations".^[179]

В его научно-фантастическом романе Контакт, ученый Карл Саган suggested that prime factorization could be used as a means of establishing two-dimensional image planes in communications with aliens, an idea that he had first developed informally with American astronomer Фрэнк Дрейк в 1975 г.^[180] In the novel Любопытный случай с собакой в ​​ночное время к Марк Хэддон, the narrator arranges the sections of the story by consecutive prime numbers as a way to convey the mental state of its main character, a mathematically gifted teen with синдром Аспергера.^[181] Prime numbers are used as a metaphor for loneliness and isolation in the Паоло Джордано Роман The Solitude of Prime Numbers, in which they are portrayed as "outsiders" among integers.^[182]

Примечания

1. A 44-digit prime number found in 1951 by Aimé Ferrier with a mechanical calculator remains the largest prime not to have been found with the aid of electronic computers.^[27]
2. For instance, Beiler writes that number theorist Эрнст Куммер loved his ideal numbers, closely related to the primes, "because they had not soiled themselves with any practical applications",^[29] and Katz writes that Эдмунд Ландау, known for his work on the distribution of primes, "loathed practical applications of mathematics", and for this reason avoided subjects such as геометрия that had already shown themselves to be useful.^[30]
3. In this test, the ${\displaystyle \pm 1}$ term is negative if ${\displaystyle a}$ is a square modulo the given (supposed) prime ${\displaystyle p}$, and positive otherwise. More generally, for non-prime values of ${\displaystyle p}$, то ${\displaystyle \pm 1}$ term is the (negated) Символ Якоби, which can be calculated using квадратичная взаимность.
4. Indeed, much of the analysis of elliptic curve primality proving is based on the assumption that the input to the algorithm has already passed a probabilistic test.^[130]
5. В первобытный функция ${\displaystyle n}$, обозначаемый ${\displaystyle n\#}$, yields the product of the prime numbers up to ${\displaystyle n}$, а primorial prime is a prime of one of the forms ${\displaystyle n\#\pm 1}$.^[144]

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

1. "GIMPS Project Discovers Largest Known Prime Number: 2^82,589,933-1". Mersenne Research, Inc. 21 декабря 2018 г.. Получено 21 декабря 2018.
2. Гардинер, Энтони (1997). The Mathematical Olympiad Handbook: An Introduction to Problem Solving Based on the First 32 British Mathematical Olympiads 1965–1996. Издательство Оксфордского университета. п.26. ISBN  978-0-19-850105-3.
3. Henderson, Anne (2014). Dyslexia, Dyscalculia and Mathematics: A practical guide (2-е изд.). Рутледж. п. 62. ISBN  978-1-136-63662-2.
4. Адлер, Ирвинг (1960). The Giant Golden Book of Mathematics: Exploring the World of Numbers and Space. Golden Press. п.16. OCLC  6975809.
5. Leff, Lawrence S. (2000). Math Workbook for the SAT I. Образовательная серия Бэррона. п.360. ISBN  978-0-7641-0768-9.
6. Dudley, Underwood (1978). "Section 2: Unique factorization". Элементарная теория чисел (2-е изд.). W.H. Freeman and Co. стр.10. ISBN  978-0-7167-0076-0.
7. Sierpiński, Wacław (1988). Elementary Theory of Numbers. North-Holland Mathematical Library. 31 (2-е изд.). Эльзевир. п. 113. ISBN  978-0-08-096019-7.
8. Циглер, Гюнтер М. (2004). "The great prime number record races". Уведомления Американского математического общества. 51 (4): 414–416. МИСТЕР  2039814.
9. Стиллвелл, Джон (1997). Числа и геометрия. Тексты для бакалавриата по математике. Springer. п. 9. ISBN  978-0-387-98289-2.
10. Серпинский, Вацлав (1964). Подборка задач теории чисел. Нью-Йорк: Макмиллан. п.40. МИСТЕР  0170843.
11. Натансон, Мелвин Б. (2000). «Обозначения и условные обозначения». Элементарные методы в теории чисел. Тексты для выпускников по математике. 195. Springer. ISBN  978-0-387-22738-2. МИСТЕР  1732941.
12. Фатикони, Теодор Г. (2012). Математика бесконечности: руководство к великим идеям. Чистая и прикладная математика: серия текстов, монографий и трактатов Wiley. 111 (2-е изд.). Джон Вили и сыновья. п. 44. ISBN  978-1-118-24382-4.
13. Брюинз, Эверт Мари, обзор в Математические обзоры из Жиллингс, Р.Дж. (1974). «Лицевая сторона Математического Папируса Райнда. Как древнеегипетский писец подготовил его?». Архив истории точных наук. 12 (4): 291–298. Дои:10.1007 / BF01307175. МИСТЕР  0497458. S2CID  121046003.
14. Стиллвелл, Джон (2010). Математика и ее история. Тексты для бакалавриата по математике (3-е изд.). Springer. п. 40. ISBN  978-1-4419-6052-8.
15. Померанс, Карл (Декабрь 1982 г.). «Поиск простых чисел». Scientific American. 247 (6): 136–147. Bibcode:1982SciAm.247f.136P. Дои:10.1038 / scientificamerican1282-136. JSTOR  24966751.
16. Моллин, Ричард А. (2002). «Краткая история факторинга и тестирования на простоту Б.С. (до компьютеров)». Математический журнал. 75 (1): 18–29. Дои:10.2307/3219180. JSTOR  3219180. МИСТЕР  2107288.
17. О'Коннор, Джон Дж.; Робертсон, Эдмунд Ф. «Абу Али аль-Хасан ибн аль-Хайтам». Архив истории математики MacTutor. Сент-Эндрюсский университет..
18. Сандифер 2007, 8. Маленькая теорема Ферма (ноябрь 2003 г.), с. 45
19. Сандифер, К. Эдвард (2014). Как Эйлер сделал даже больше. Математическая ассоциация Америки. п. 42. ISBN  978-0-88385-584-3.
20. Коши, Томас (2002). Элементарная теория чисел с приложениями. Академическая пресса. п. 369. ISBN  978-0-12-421171-1.
21. Юань, Ван (2002). Гипотеза Гольдбаха. Серия по чистой математике. 4 (2-е изд.). World Scientific. п. 21. ISBN  978-981-4487-52-8.
22. Наркевич, Владислав (2000). «1.2 Сумма взаимных чисел». Развитие теории простых чисел: от Евклида до Харди и Литтлвуда. Монографии Спрингера по математике. Springer. п. 11. ISBN  978-3-540-66289-1.
23. Апостол, Том М. (2000). "Столетняя история теоремы о простых числах". In Bambah, R.P .; Dumir, V.C .; Ханс-Гилл, Р.Дж. (ред.). Теория чисел. Тенденции в математике. Базель: Биркхойзер. С. 1–14. МИСТЕР  1764793.
24. Апостол, Том М. (1976). «7. Теорема Дирихле о простых числах в арифметических прогрессиях». Введение в аналитическую теорию чисел. Нью-Йорк; Гейдельберг: Springer-Verlag. С. 146–156. МИСТЕР  0434929.
25. Шабер, Жан-Люк (2012). История алгоритмов: от гальки до микрочипа. Springer. п. 261. ISBN  978-3-642-18192-4.
26. Розен, Кеннет Х. (2000). «Теорема 9.20. Тест на простоту Прота». Элементарная теория чисел и ее приложения (4-е изд.). Эддисон-Уэсли. п. 342. ISBN  978-0-201-87073-2.
27. Купер, С. Барри; Ходжес, Эндрю (2016). Когда-то и будущее Тьюринга. Издательство Кембриджского университета. С. 37–38. ISBN  978-1-107-01083-3.
28. Розен 2000, п. 245.
29. Бейлер, Альберт Х. (1999) [1966]. Развлечение в теории чисел: королева математики развлекает. Дувр. п. 2. ISBN  978-0-486-21096-4. OCLC  444171535.
30. Кац, Шауль (2004). «Берлинские корни - сионистское воплощение: этос чистой математики и истоки Института математики Эйнштейна при Еврейском университете в Иерусалиме». Наука в контексте. 17 (1–2): 199–234. Дои:10.1017 / S0269889704000092. МИСТЕР  2089305.
31. Крафт, Джеймс С .; Вашингтон, Лоуренс К. (2014). Элементарная теория чисел. Учебники по математике. CRC Press. п. 7. ISBN  978-1-4987-0269-0.
32. Бауэр, Крейг П. (2013). Тайная история: история криптологии. Дискретная математика и ее приложения. CRC Press. п. 468. ISBN  978-1-4665-6186-1.
33. Клее, Виктор; Вагон, Стан (1991). Старые и новые нерешенные задачи плоской геометрии и теории чисел. Математические изложения Дольчиани. 11. Издательство Кембриджского университета. п. 224. ISBN  978-0-88385-315-3.
34. Нил 2017 С. 18, 47.
35. Колдуэлл, Крис К .; Реддик, Анджела; Сюн, Йенг; Келлер, Уилфрид (2012). «История первобытности одного: подборка источников». Журнал целочисленных последовательностей. 15 (9): Статья 12.9.8. МИСТЕР  3005523. Выборку цитат из позиций древних греков по этому вопросу и о них см., В частности, на стр. 3–4. Об исламских математиках см. Стр. 6.
36. Таран, Леонардо (1981). Спевсипп Афинский: критическое исследование со сборником родственных текстов и комментариями. Philosophia Antiqua: Серия монографий по античной философии. 39. Брилл. С. 35–38. ISBN  978-90-04-06505-5.
37. Caldwell et al. 2012 г. С. 7–13. См., В частности, записи для Стевина, Бранкера, Уоллиса и Престета.
38. Caldwell et al. 2012 г., п. 15.
39. Колдуэлл, Крис К .; Сюн, Йенг (2012). "Какое наименьшее простое число?" (PDF). Журнал целочисленных последовательностей. 15 (9): Статья 12.9.7. МИСТЕР  3005530.
40. Ризель, Ганс (1994). Простые числа и компьютерные методы факторизации (2-е изд.). Базель, Швейцария: Birkhäuser. п. 36. Дои:10.1007/978-1-4612-0251-6. ISBN  978-0-8176-3743-9. МИСТЕР  1292250.
41. Конвей, Джон Хортон; Гай, Ричард К. (1996). Книга чисел. Нью-Йорк: Коперник. стр.129–130. Дои:10.1007/978-1-4612-4072-3. ISBN  978-0-387-97993-9. МИСТЕР  1411676.
42. Для туалета см. Серпинский 1988, п. 245. О сумме делителей см. Сандифер, К. Эдвард (2007). Как это сделал Эйлер. MAA Spectrum. Математическая ассоциация Америки. п. 59. ISBN  978-0-88385-563-8.
43. Смит, Карл Дж. (2011). Природа математики (12-е изд.). Cengage Learning. п. 188. ISBN  978-0-538-73758-6.
44. Дадли 1978, Раздел 2, теорема 2, с. 16; Нил, Вики (2017). Устранение разрыва: поиски понимания простых чисел. Издательство Оксфордского университета. п. 107. ISBN  978-0-19-109243-5.
45. дю Сотуа, Маркус (2003). Музыка простых чисел: в поисках разгадки величайшей загадки математики. Харпер Коллинз. п.23. ISBN  978-0-06-093558-0.
46. Дадли 1978, Раздел 2, лемма 5, с. 15; Хиггинс, Питер М. (1998). Математика для любопытных. Издательство Оксфордского университета. С. 77–78. ISBN  978-0-19-150050-3.
47. Ротман, Джозеф Дж. (2000). Первый курс абстрактной алгебры (2-е изд.). Прентис Холл. Задача 1.40, с. 56. ISBN  978-0-13-011584-3.
48. Письмо в латинский от Гольдбаха до Эйлера, июль 1730 г.
49. Фюрстенберг, Гарри (1955). «О бесконечности простых чисел». Американский математический ежемесячный журнал. 62 (5): 353. Дои:10.2307/2307043. JSTOR  2307043. МИСТЕР  0068566.
50. Рибенбойм, Пауло (2004). Маленькая книга больших простых чисел. Берлин; Нью-Йорк: Springer-Verlag. п. 4. ISBN  978-0-387-20169-6.
51. Евклида Элементы, Книга IX, Предложение 20. См. Английский перевод доказательства Евклида Дэвидом Джойсом или же Уильямсон, Джеймс (1782). Элементы Евклида, с диссертациями. Оксфорд: Clarendon Press. п. 63. OCLC  642232959.
52. Варди, Илан (1991). Вычислительные развлечения в системе Mathematica. Эддисон-Уэсли. С. 82–89. ISBN  978-0-201-52989-0.
53. Матиясевич, Юрий В. (1999). «Формулы для простых чисел». В Табачников Серж (ред.). Квант Селекта: алгебра и анализ. II. Американское математическое общество. С. 13–24. ISBN  978-0-8218-1915-9.
54. Маккиннон, Ник (июнь 1987). «Формулы простых чисел». Математический вестник. 71 (456): 113–114. Дои:10.2307/3616496. JSTOR  3616496.
55. Райт, Э. (1951). «Представляющая простое число функция». Американский математический ежемесячный журнал. 58 (9): 616–618. Дои:10.2307/2306356. JSTOR  2306356.
56. Парень 2013, п. vii.
57. Парень 2013, C1 Гипотеза Гольдбаха, стр. 105–107..
58. Оливейра э Силва, Томас; Герцог, Зигфрид; Парди, Сильвио (2014). «Эмпирическая проверка четной гипотезы Гольдбаха и вычисление простых пробелов с точностью до ${\displaystyle 4\cdot 10^{18}}$". Математика вычислений. 83 (288): 2033–2060. Дои:10.1090 / S0025-5718-2013-02787-1. МИСТЕР  3194140.
59. Дао 2009, 3.1 Структура и случайность в простых числах, стр. 239–247.. См. Особенно стр. 239.
60. Парень 2013, п. 159.
61. Рамаре, Оливье (1995). "О постоянной Шнирельмана". Annali della Scuola Normale Superiore di Pisa. 22 (4): 645–706. МИСТЕР  1375315.
62. Рассиас, Майкл Ф. (2017). Проблема Гольдбаха: избранные темы. Чам: Спрингер. п. vii. Дои:10.1007/978-3-319-57914-6. ISBN  978-3-319-57912-2. МИСТЕР  3674356.
63. Коши 2002, Теорема 2.14, с. 109. Ризель 1994 дает аналогичный аргумент, используя первобытный вместо факториала.
64. Ризель 1994, "Большие промежутки между последовательными простыми числами ", стр. 78–79.
65. Слоан, Н. Дж. А. (ред.). «Последовательность A100964 (Наименьшее простое число, которое начинается с пробела не менее 2n)». В Он-лайн энциклопедия целочисленных последовательностей. Фонд OEIS.
66. Рибенбойм 2004, Разрывы между простыми числами, стр. 186–192.
67. Рибенбойм 2004, п. 183.
68. Чан, Джоэл (февраль 1996). "ПРАЙМ-тайм!". Математические горизонты. 3 (3): 23–25. Дои:10.1080/10724117.1996.11974965. JSTOR  25678057. Обратите внимание, что Чан называет гипотезу Лежандра «Постулатом Серпинского».
69. Рибенбойм 2004, Основной ${\displaystyle k}$-гипотеза о множествах, стр. 201–202.
70. Сандифер 2007, Глава 35, Оценка проблемы Базеля, стр. 205–208.
71. Огилви, К.; Андерсон, Дж. (1988). Экскурсии по теории чисел. Dover Publications Inc., стр. 29–35. ISBN  978-0-486-25778-5.
72. Апостол 1976 г., Раздел 1.6, теорема 1.13
73. Апостол 1976 г., Раздел 4.8, теорема 4.12
74. Миллер, Стивен Дж .; Таклоо-Бигхаш, Рамин (2006). Приглашение к современной теории чисел. Издательство Принстонского университета. С. 43–44. ISBN  978-0-691-12060-7.
75. Crandall & Pomerance 2005, п. 6.
76. Crandall & Pomerance 2005, Раздел 3.7, Подсчет простых чисел, стр. 152–162..
77. Crandall & Pomerance 2005, п. 10.
78. дю Сотуа, Маркус (2011). "Каковы шансы, что ваш телефонный номер простой?". Тайны чисел: математическая одиссея повседневной жизни. Пресса Св. Мартина. С. 50–52. ISBN  978-0-230-12028-0.
79. Апостол 1976 г., Раздел 4.6, теорема 4.7
80. Гельфанд, И.; Шен, Александр (2003). Алгебра. Springer. п. 37. ISBN  978-0-8176-3677-7.
81. Моллин, Ричард А. (1997). Фундаментальная теория чисел с приложениями. Дискретная математика и ее приложения. CRC Press. п. 76. ISBN  978-0-8493-3987-5.
82. Crandall & Pomerance 2005, Теорема 1.1.5, с. 12.
83. Грин, Бен; Тао, Теренс (2008). «Простые числа содержат произвольно длинные арифметические прогрессии». Анналы математики. 167 (2): 481–547. arXiv:math.NT / 0404188. Дои:10.4007 / летопись.2008.167.481. S2CID  1883951.
84. Хуа, Л. (2009) [1965]. Аддитивная теория простых чисел. Переводы математических монографий. 13. Провиденс, Род-Айленд: Американское математическое общество. С. 176–177. ISBN  978-0-8218-4942-2. МИСТЕР  0194404. OCLC  824812353.
85. Последовательность этих простых чисел, начиная с ${\displaystyle n=1}$ скорее, чем ${\displaystyle n=0}$, перечислено Лава, Паоло Пьетро; Бальзаротти, Джорджио (2010). «Глава 33. Формула удачи». 103 curiosità matematiche: Teoria dei numeri, delle cifre e delle relazioni nella matematica contemporanea (на итальянском). Ulrico Hoepli Editore S.p.A. стр. 133. ISBN  978-88-203-5804-4.
86. Чемберленд, Марк (2015). «Числа Хегнера». Одиночные цифры: похвала малых чисел. Издательство Принстонского университета. С. 213–215. ISBN  978-1-4008-6569-7.
87. Гай, Ричард (2013). «A1 Простые значения квадратичных функций». Нерешенные проблемы теории чисел. Проблемные книги по математике (3-е изд.). Springer. С. 7–10. ISBN  978-0-387-26677-0.
88. Паттерсон, С.Дж. (1988). Введение в теорию дзета-функции Римана. Кембриджские исследования в области высшей математики. 14. Издательство Кембриджского университета, Кембридж. п. 1. Дои:10.1017 / CBO9780511623707. ISBN  978-0-521-33535-5. МИСТЕР  0933558.
89. Борвейн, Питер; Чой, Стивен; Руни, Брендан; Вейратмюллер, Андреа (2008). Гипотеза Римана: ресурс для фанатов и виртуозов. CMS Книги по математике / Ouvrages de Mathématiques de la SMC. Нью-Йорк: Спрингер. С. 10–11. Дои:10.1007/978-0-387-72126-2. ISBN  978-0-387-72125-5. МИСТЕР  2463715.
90. Сандифер 2007, стр. 191–193.
91. Borwein et al. 2008 г., Гипотеза 2.7 (гипотеза Римана), с. 15.
92. Паттерсон 1988, п. 7.
93. Borwein et al. 2008 г., п. 18.
94. Натансон 2000, Глава 9, Теорема о простых числах, стр. 289–324..
95. Загир, Дон (1977). «Первые 50 миллионов простых чисел». Математический интеллект. 1 (S2): 7–19. Дои:10.1007 / bf03351556. S2CID  37866599. См. Особенно стр. 14–16.
96. Крафт и Вашингтон (2014), Предложение 5.3., п. 96.
97. Шахриари, Шахриар (2017). Алгебра в действии: курс групп, колец и полей. Чистые и прикладные тексты бакалавриата. 27. Американское математическое общество. С. 20–21. ISBN  978-1-4704-2849-5.
98. Дадли 1978, Теорема 3, с. 28.
99. Шахриари 2017, стр. 27–28.
100. Рибенбойм 2004, Малая теорема Ферма и первообразные корни по простому модулю, стр. 17–21.
101. Рибенбойм 2004, Собственность Джуги, стр. 21–22.
102. Рибенбойм 2004, Теорема Вильсона, с. 21.
103. Чайлдресс, Нэнси (2009). Теория поля классов. Universitext. Спрингер, Нью-Йорк. С. 8–11. Дои:10.1007/978-0-387-72490-4. ISBN  978-0-387-72489-8. МИСТЕР  2462595. Также стр. 64.
104. Эриксон, Марти; Ваззана, Энтони; Гарт, Дэвид (2016). Введение в теорию чисел. Учебники по математике (2-е изд.). Бока-Ратон, Флорида: CRC Press. п. 200. ISBN  978-1-4987-1749-6. МИСТЕР  3468748.
105. Вайль, Андре (1995). Основная теория чисел. Классика по математике. Берлин: Springer-Verlag. п.43. ISBN  978-3-540-58655-5. МИСТЕР  1344916. Однако обратите внимание, что некоторые авторы, такие как Чайлдресс (2009) вместо этого используйте слово «место» для обозначения класса эквивалентности норм.
106. Кох, Х. (1997). Алгебраическая теория чисел. Берлин: Springer-Verlag. п. 136. CiteSeerX  10.1.1.309.8812. Дои:10.1007/978-3-642-58095-6. ISBN  978-3-540-63003-6. МИСТЕР  1474965.
107. Лауритцен, Нильс (2003). Конкретная абстрактная алгебра: от чисел к базисам Грёбнера. Кембридж: Издательство Кембриджского университета. п. 127. Дои:10.1017 / CBO9780511804229. ISBN  978-0-521-53410-9. МИСТЕР  2014325.
108. Лауритцен 2003, Следствие 3.5.14, с. 133; Лемма 3.5.18, с. 136.
109. Крафт и Вашингтон 2014, Раздел 12.1, Суммы двух квадратов, стр. 297–301..
110. Эйзенбуд, Дэвид (1995). Коммутативная алгебра. Тексты для выпускников по математике. 150. Берлин; Нью-Йорк: Springer-Verlag. Раздел 3.3. Дои:10.1007/978-1-4612-5350-1. ISBN  978-0-387-94268-1. МИСТЕР  1322960.
111. Шафаревич, Игорь Р. (2013). "Значение ${\displaystyle \operatorname {Spec} A}$". Базовая алгебраическая геометрия 2: схемы и комплексные многообразия (3-е изд.). Спрингер, Гейдельберг. п. 5. Дои:10.1007/978-3-642-38010-5. ISBN  978-3-642-38009-9. МИСТЕР  3100288.
112. Нойкирх, Юрген (1999). Алгебраическая теория чисел. Grundlehren der Mathematischen Wissenschaften [Основные принципы математических наук]. 322. Берлин: Springer-Verlag. Раздел I.8, с. 50. Дои:10.1007/978-3-662-03983-0. ISBN  978-3-540-65399-8. МИСТЕР  1697859.
113. Нойкирх 1999, Раздел I.7, стр. 38
114. Stevenhagen, P .; Ленстра, Х.В., мл. (1996). «Чеботарев и его теорема плотности». Математический интеллект. 18 (2): 26–37. CiteSeerX  10.1.1.116.9409. Дои:10.1007 / BF03027290. МИСТЕР  1395088. S2CID  14089091.
115. Холл, Маршалл (2018). Теория групп. Дуврские книги по математике. Courier Dover Publications. ISBN  978-0-486-81690-6. По поводу теорем Силова см. Стр. 43; теорему Лагранжа см. на стр. 12; теорему Бернсайда см. на стр. 143.
116. Брайант, Джон; Сангвин, Кристофер Дж. (2008). Насколько круглый ваш круг? Где встречаются инженерия и математика. Издательство Принстонского университета. п. 178. ISBN  978-0-691-13118-4.
117. Харди, Годфри Гарольд (2012) [1940]. Извинения математика. Издательство Кембриджского университета. п.140. ISBN  978-0-521-42706-7. OCLC  922010634. Никто еще не открыл какой-либо военной цели, которой могла бы служить теория чисел или относительности, и кажется маловероятным, что кто-то будет делать это в течение многих лет.
118. Гиблин, Питер (1993). Простые числа и программирование. Издательство Кембриджского университета. п.39. ISBN  978-0-521-40988-9.
119. Гиблин 1993, п. 54
120. Ризель 1994, п. 220.
121. Буллинк, Маартен (2010). "История факторных таблиц с заметками о зарождении теории чисел 1657–1817 гг.". Revue d'Histoire des Mathématiques. 16 (2): 133–216.
122. Вагстафф, Сэмюэл С. мл. (2013). Радость факторинга. Студенческая математическая библиотека. 68. Американское математическое общество. п. 191. ISBN  978-1-4704-1048-3.
123. Крэндалл, Ричард; Померанс, Карл (2005). Простые числа: вычислительная перспектива (2-е изд.). Springer. п. 121. ISBN  978-0-387-25282-7.
124. Фарах-Колтон, Мартин; Цай, Мэн-Цунг (2015). «О сложности вычисления таблиц простых чисел». В Эльбассиони - Халед; Макино, Кадзухиса (ред.). Алгоритмы и вычисления: 26-й Международный симпозиум, ISAAC 2015, Нагоя, Япония, 9-11 декабря 2015 г., Труды. Конспект лекций по информатике. 9472. Springer. С. 677–688. arXiv:1504.05240. Дои:10.1007/978-3-662-48971-0_57.
125. Гривз, Джордж (2013). Решета в теории чисел. Ergebnisse der Mathematik и ихрер Гренцгебиете (3. Folge). 43. Springer. п. 1. ISBN  978-3-662-04658-6.
126. Громкович, Юрай (2001). «5.5 Библиографические примечания». Алгоритмика для сложных задач. Тексты по теоретической информатике. Серия EATCS. Шпрингер-Верлаг, Берлин. С. 383–385. Дои:10.1007/978-3-662-04616-6. ISBN  978-3-540-66860-2. МИСТЕР  1843669. S2CID  31159492.
127. Коблиц, Нил (1987). «Глава V. Примитивность и факторинг». Курс теории чисел и криптографии. Тексты для выпускников по математике. 114. Спрингер-Верлаг, Нью-Йорк. С. 112–149. Дои:10.1007/978-1-4684-0310-7_5. ISBN  978-0-387-96576-5. МИСТЕР  0910297.
128. Пиепшик, Йозеф; Hardjono, Thomas; Seberry, Дженнифер (2013). «2.3.9 Вероятностные вычисления». Основы компьютерной безопасности. Springer. С. 51–52. ISBN  978-3-662-07324-7.
129. Тао, Теренс (2010). «1.11 Тест простоты AKS». Эпсилон комнаты, II: страницы третьего курса математического блога. Аспирантура по математике. 117. Провиденс, Род-Айленд: Американское математическое общество. С. 82–86. Дои:10,1090 / г / м2 / 117. ISBN  978-0-8218-5280-4. МИСТЕР  2780010.
130. Аткин, А.; Морейн, Ф. (1993). «Эллиптические кривые и доказательство простоты» (PDF). Математика вычислений. 61 (203): 29–68. Дои:10.1090 / с0025-5718-1993-1199989-х. JSTOR  2152935. МИСТЕР  1199989.
131. Морейн, Ф. (2007). «Реализация асимптотически быстрой версии алгоритма доказательства простоты эллиптической кривой». Математика вычислений. 76 (257): 493–505. arXiv:математика / 0502097. Bibcode:2007MaCom..76..493M. Дои:10.1090 / S0025-5718-06-01890-4. МИСТЕР  2261033. S2CID  133193.
132. Lenstra, H. W. Jr.; Померанс, Карл (2019). «Проверка на примитивность с гауссовыми периодами» (PDF). Журнал Европейского математического общества. 21 (4): 1229–1269. Дои:10.4171 / JEMS / 861. МИСТЕР  3941463.
133. Карл Померанс; Джон Л. Селфридж; Сэмюэл С. Вагстафф-мл. (Июль 1980 г.). «Псевдопреступности до 25 · 10⁹" (PDF). Математика вычислений. 35 (151): 1003–1026. Дои:10.1090 / S0025-5718-1980-0572872-7. JSTOR  2006210.
134. Роберт Бэйли; Сэмюэл С. Вагстафф-мл. (Октябрь 1980 г.). "Лукас Псевдопримес" (PDF). Математика вычислений. 35 (152): 1391–1417. Дои:10.1090 / S0025-5718-1980-0583518-6. JSTOR  2006406. МИСТЕР  0583518.
135. Монье, Луи (1980). «Оценка и сравнение двух эффективных алгоритмов вероятностного тестирования простоты». Теоретическая информатика. 12 (1): 97–108. Дои:10.1016/0304-3975(80)90007-9. МИСТЕР  0582244.
136. Тао, Теренс (2009). "1.7 Тест Лукаса – Лемера для простых чисел Мерсенна". Наследие Пуанкаре, страницы второго года математического блога. Часть I. Провиденс, Род-Айленд: Американское математическое общество. С. 36–41. ISBN  978-0-8218-4883-8. МИСТЕР  2523047.
137. Крафт и Вашингтон 2014, п. 41 год.
138. Например, см. Парень 2013, Простые числа Мерсенна A3. Repunits. Числа Ферма. Простые формы ${\displaystyle k\cdot 2^{n}+1}$. стр. 13–21.
139. "Рекордное 12-миллионное простое число принесет приз в размере 100 000 долларов". Фонд электронных рубежей. 14 октября 2009 г.. Получено 2010-01-04.
140. "Награды EFF Cooperative Computing Awards". Фонд электронных рубежей. 2008-02-29. Получено 2010-01-04.
141. «Подпроект PrimeGrid Seventeen or Bust» (PDF). Получено 2017-01-03.
142. Колдуэлл, Крис К. «Двадцать лучших: наибольшие известные простые числа». Прайм Страницы. Получено 2017-01-03.
143. Колдуэлл, Крис К. «Двадцатка лучших: Факториал». Прайм Страницы. Получено 2017-01-03.
144. Рибенбойм 2004, п. 4.
145. Колдуэлл, Крис К. «Двадцатка лучших: Первобытный». Прайм Страницы. Получено 2017-01-03.
146. Колдуэлл, Крис К. «Двадцать лучших: простые числа-близнецы». Прайм Страницы. Получено 2017-01-03.
147. Крафт и Вашингтон 2014, п. 275.
148. Хоффштейн, Джеффри; Пайфер, Джилл; Сильверман, Джозеф Х. (2014). Введение в математическую криптографию. Тексты для бакалавриата по математике (2-е изд.). Springer. п. 329. ISBN  978-1-4939-1711-2.
149. Померанс, Карл (1996). «Сказка о двух ситах». Уведомления Американского математического общества. 43 (12): 1473–1485. МИСТЕР  1416721.
150. Эммануэль Томе, «795-битное разложение и дискретные логарифмы», 2 декабря 2019.
151. Риффель, Элеонора Г.; Полак, Вольфганг Х. (2011). «Глава 8. Алгоритм Шора». Квантовые вычисления: краткое введение. MIT Press. С. 163–176. ISBN  978-0-262-01506-6.
152. Мартин-Лопес, Энрике; Лэйнг, Энтони; Лоусон, Томас; Альварес, Роберто; Чжоу, Сяо-Ци; О'Брайен, Джереми Л. (12 октября 2012 г.). «Экспериментальная реализация квантового алгоритма факторизации Шора с использованием рециклинга кубитов». Природа Фотоника. 6 (11): 773–776. arXiv:1111.4147. Bibcode:2012НаФо ... 6..773M. Дои:10.1038 / nphoton.2012.259. S2CID  46546101.
153. Чиргвин, Ричард (9 октября 2016 г.). «Крипто требует большей прозрачности, - предупреждают исследователи». Реестр.
154. Хоффштейн, Пайфер и Сильверман 2014, Раздел 2.3, Обмен ключами Диффи – Хеллмана, стр. 65–67.
155. Кормен, Томас Х.; Лейзерсон, Чарльз Э.; Ривест, Рональд Л.; Штейн, Клиффорд (2001) [1990]. «11.3 Универсальное хеширование». Введение в алгоритмы (2-е изд.). MIT Press и McGraw-Hill. С. 232–236. ISBN  0-262-03293-7. За ${\displaystyle k}$-независимое хеширование см. задачу 11–4, с. 251. Благодарность Картеру и Вегману см. В примечаниях к главе, с. 252.
156. Гудрич, Майкл Т.; Тамассия, Роберто (2006). Структуры данных и алгоритмы в Java (4-е изд.). Джон Вили и сыновья. ISBN  978-0-471-73884-8. См. «Квадратичное измерение» с. 382, и упражнение C – 9.9, p. 415.
157. Киртланд, Джозеф (2001). Идентификационные номера и схемы контрольных цифр. Учебные материалы. 18. Математическая ассоциация Америки. С. 43–44. ISBN  978-0-88385-720-5.
158. Дойч, П. (1996). Спецификация формата сжатых данных ZLIB версия 3.3. Запрос комментариев. 1950. Сетевая рабочая группа.
159. Кнут, Дональд Э. (1998). «3.2.1 Линейная конгруэнтная модель». Искусство программирования, Vol. 2: получисловые алгоритмы (3-е изд.). Эддисон-Уэсли. С. 10–26. ISBN  978-0-201-89684-8.
160. Мацумото, Макото; Нисимура, Такудзи (1998). "Мерсенн Твистер: 623-мерный равнораспределенный однородный генератор псевдослучайных чисел". Транзакции ACM по моделированию и компьютерному моделированию. 8 (1): 3–30. CiteSeerX  10.1.1.215.1141. Дои:10.1145/272991.272995. S2CID  3332028.
161. Рот, К.Ф. (1951). «О проблеме Хайльбронна». Журнал Лондонского математического общества. Вторая серия. 26 (3): 198–204. Дои:10.1112 / jlms / s1-26.3.198. МИСТЕР  0041889.
162. Кокс, Дэвид А. (2011). «Почему Эйзенштейн доказал критерий Эйзенштейна и почему Шёнеман открыл его первым» (PDF). Американский математический ежемесячный журнал. 118 (1): 3–31. CiteSeerX  10.1.1.398.3440. Дои:10.4169 / amer.math.monthly.118.01.003. S2CID  15978494.
163. Ланг, Серж (2002). Алгебра. Тексты для выпускников по математике. 211. Берлин; Нью-Йорк: Springer-Verlag. Дои:10.1007/978-1-4613-0041-0. ISBN  978-0-387-95385-4. МИСТЕР  1878556., Раздел II.1, стр. 90
164. Шуберт, Хорст (1949). "Die eindeutige Zerlegbarkeit eines Knotens in Primknoten". S.-B Heidelberger Akad. Wiss. Math.-Nat. Kl. 1949 (3): 57–104. МИСТЕР  0031733.
165. Милнор, Дж. (1962). «Единственная теорема о разложении для 3-многообразий». Американский журнал математики. 84 (1): 1–7. Дои:10.2307/2372800. JSTOR  2372800. МИСТЕР  0142125.
166. Боклан и Конвей (2017) также включать ${\displaystyle 2^{0}+1=2}$, который не имеет такой формы.
167. Кржижек, Михал; Лука, Флориан; Сомер, Лоуренс (2001). 17 лекций о числах Ферма: от теории чисел к геометрии. CMS Книги по математике. 9. Нью-Йорк: Springer-Verlag. С. 1–2. Дои:10.1007/978-0-387-21850-2. ISBN  978-0-387-95332-8. МИСТЕР  1866957.
168. Boklan, Kent D .; Конвей, Джон Х. (Январь 2017 г.). "Ожидайте не более одной миллиардной доли новой Fermaт основной!". Математический интеллект. 39 (1): 3–5. arXiv:1605.01371. Дои:10.1007 / s00283-016-9644-3. S2CID  119165671.
169. Глисон, Эндрю М. (1988). «Трисечение угла, семиугольник и трехугольник». Американский математический ежемесячный журнал. 95 (3): 185–194. Дои:10.2307/2323624. JSTOR  2323624. МИСТЕР  0935432.
170. Циглер, Гюнтер М. (2015). «Пушки по воробьям». Информационный бюллетень Европейского математического общества (95): 25–31. МИСТЕР  3330472.
171. Петерсон, Иварс (28 июня 1999 г.). "Возвращение Зеты". MAA Online. Архивировано из оригинал 20 октября 2007 г.. Получено 2008-03-14.
172. Хейс, Брайан (2003). «Информатика: спектр римания». Американский ученый. 91 (4): 296–300. Дои:10.1511/2003.26.3349. JSTOR  27858239.
173. Бенгтссон, Ингемар; Cyczkowski, Karol (2017). Геометрия квантовых состояний: введение в квантовую запутанность (Второе изд.). Кембридж: Издательство Кембриджского университета. С. 313–354. ISBN  978-1-107-02625-4. OCLC  967938939.
174. Чжу, Хуанцзюнь (2010). «SIC POVM и группы Клиффорда в простых измерениях». Журнал физики A: математический и теоретический. 43 (30): 305305. arXiv:1003.3591. Bibcode:2010JPhA ... 43D5305Z. Дои:10.1088/1751-8113/43/30/305305. S2CID  118363843.
175. Goles, E .; Schulz, O .; Маркус, М. (2001). «Выбор простого числа циклов в модели хищник-жертва». Сложность. 6 (4): 33–38. Bibcode:2001Cmplx ... 6d..33G. Дои:10.1002 / cplx.1040.
176. Campos, Paulo R.A .; де Оливейра, Вивиан М .; Джиро, Роналду; Гальвао, Дуглас С. (2004). «Возникновение простых чисел в результате эволюционной стратегии». Письма с физическими проверками. 93 (9): 098107. arXiv:q-bio / 0406017. Bibcode:2004PhRvL..93i8107C. Дои:10.1103 / PhysRevLett.93.098107. PMID  15447148. S2CID  88332.
177. "Нашествие выводка". Экономист. 6 мая 2004 г.. Получено 2006-11-26.
178. Циммер, Карл (15 мая 2015 г.). «Бамбуковые математики». Феномены: ткацкий станок. Национальная география. Получено 22 февраля, 2018.
179. Хилл, Питер Дженсен, изд. (1995). Спутник Мессиана. Портленд, Орегон: Amadeus Press. Бывший. 13,2 Messe de la Pentecôte 1 Entrée. ISBN  978-0-931340-95-6.
180. Померанс, Карл (2004). «Простые числа и поиски внеземного разума» (PDF). В Hayes, Дэвид Ф .; Росс, Питер (ред.). Математические приключения для студентов и любителей. MAA Spectrum. Вашингтон, округ Колумбия: Математическая ассоциация Америки. С. 3–6. ISBN  978-0-88385-548-5. МИСТЕР  2085842.
181. GrrlScientist (16 сентября 2010 г.). "Любопытный случай с собакой в ​​ночное время". Наука. Хранитель. Получено 22 февраля, 2010.
182. Шиллингер, Лизл (9 апреля 2010 г.). "Рассчитывать друг на друга". Воскресное обозрение книги. Нью-Йорк Таймс.

внешняя ссылка

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

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

• Проверка простых чисел определяет наименьший простой делитель числа.
• Быстрый онлайн-тест на простоту с факторизацией использует метод эллиптической кривой (числа до тысячи цифр, требуется Java).
• Огромная база простых чисел
• Простые числа до 1 триллиона