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

Число, делящееся только на 1 или само на себя

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

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

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

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

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

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

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

Демонстрация с помощью палочек Кюизенера того, что число 7 является простым, поскольку ни одно из чисел 2, 3, 4, 5 или 6 не делит его без остатка.

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

Первые 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 ).

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

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

История

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

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

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle {\begin{aligned}50&=2\times 5\times 5\\&=2\times 5^{2}.\end{aligned}}}$

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

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

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

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

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

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

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

Доказательство Евклида ^[54] показывает, что любой конечный список простых чисел неполон. Основная идея состоит в том, чтобы перемножить простые числа в любом заданном списке и добавить Если список состоит из простых чисел, это дает число ${\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}$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Распределение простых чисел в большом, например, вопрос о том, сколько простых чисел меньше заданного большого порога, описывается теоремой о простых числах , но эффективная формула для -го простого числа ${\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}}.}$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Один из самых известных нерешенных вопросов математики, датируемый 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}}}.}$

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

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

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

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

Модульная арифметика изменяет обычную арифметику, используя только числа , для натурального числа, называемого модулем. Любое другое натуральное число может быть отображено в эту систему, заменив его остатком после деления на . ^[99] Модульные суммы, разности и произведения вычисляются путем выполнения той же замены остатком на результат обычной суммы, разности или произведения целых чисел. ^[100] Равенство целых чисел соответствует конгруэнтности в модульной арифметике: и конгруэнтны (записываются mod ), когда они имеют одинаковый остаток после деления на . ^[101] Однако в этой системе чисел деление на все ненулевые числа возможно тогда и только тогда, когда модуль является простым числом. Например, с простым числом в качестве модуля возможно деление на , поскольку очистка знаменателей путем умножения обеих сторон на дает действительную формулу . Однако с составным модулем деление на невозможно. Не существует допустимого решения для : очистка знаменателей путем умножения на приводит к тому, что левая часть становится , а правая часть становится либо , либо . В терминологии абстрактной алгебры способность выполнять деление означает, что модульная арифметика по модулю простого числа образует поле или, более конкретно, конечное поле , тогда как другие модули дают только кольцо , но не поле. ^[102] ${\displaystyle \{0,1,2,\dots ,n-1\}}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle x\equiv y}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\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}$

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

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

справедливо, когда является простым. Гипотеза Джуги гласит, что это уравнение также является достаточным условием для того, чтобы быть простым. ^[104] Теорема Уилсона гласит, что целое число является простым тогда и только тогда, когда факториал сравним с mod . Для составного числа это не может быть выполнено, поскольку один из его множителей делит и n , и , и поэтому это невозможно. ^[105] ${\displaystyle p}$ ${\displaystyle p}$ ${\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}}}$

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

-адический порядок целого числа — это количество копий в разложении на простые множители . Эту же концепцию можно распространить с целых чисел на рациональные числа, определив -адический порядок дроби как . -адическое абсолютное значение любого рационального числа тогда определяется как . Умножение целого числа на его -адическое абсолютное значение отменяет множители в его разложении, оставляя только другие простые числа. Так же, как расстояние между двумя действительными числами можно измерить абсолютным значением их расстояния, расстояние между двумя рациональными числами можно измерить их -адическим расстоянием, -адическим абсолютным значением их разности. Для этого определения расстояния два числа близки друг к другу (они имеют небольшое расстояние), когда их разность делится на большую степень . Точно так же, как действительные числа могут быть образованы из рациональных чисел и их расстояний, путем добавления дополнительных предельных значений для формирования полного поля , рациональные числа с -адическим расстоянием могут быть расширены до другого полного поля, -адических чисел . ^{[106] [107]} ${\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}$

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

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

Гауссовские простые числа с нормой меньше 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 \}\,.}$

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

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

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

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

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

Теория групп

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

Методы расчета

Малая шестерня в этом сельскохозяйственном оборудовании имеет 13 зубьев, что является простым числом, а средняя шестерня имеет 21 зуб, что является взаимно простым числом с 13.

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

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

Судебное отделение

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

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

Сита

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

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

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

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

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

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

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

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

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

Факторизация целых чисел

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

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

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

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

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

Некоторые методы контрольных сумм основаны на математике простых чисел. Например, контрольные суммы, используемые в International Standard Book Numbers, определяются путем взятия остатка числа по модулю 11, простого числа. Поскольку 11 является простым числом, этот метод может обнаруживать как однозначные ошибки, так и перестановки соседних цифр. ^[160] Другой метод контрольных сумм, Adler-32 , использует арифметику по модулю 65521, наибольшего простого числа, меньшего . ^[161] Простые числа также используются в генераторах псевдослучайных чисел , включая линейные конгруэнтные генераторы ^[162] и Mersenne Twister . ^[163] ${\displaystyle 2^{16}}$

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

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

Связная сумма двух простых узлов

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

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

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

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

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

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

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

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

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

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

Биология

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

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

Простые числа оказали влияние на многих художников и писателей. Французский композитор Оливье Мессиан использовал простые числа для создания аметрической музыки посредством «природных явлений». В таких работах, как La Nativité du Seigneur (1935) и Quatre études de rythme (1949–50), он одновременно использует мотивы с длинами, заданными разными простыми числами, для создания непредсказуемых ритмов: простые числа 41, 43, 47 и 53 появляются в третьем этюде, «Neumes rythmiques». По словам Мессиана, этот способ сочинения был «вдохновлен движениями природы, движениями свободной и неравной длительности». ^[182]

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

Примечания

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

Ссылки

1. "Проект GIMPS обнаружил самое большое известное простое число: 282,589,933-1". Mersenne Research, Inc. 21 декабря 2018 г. Получено 21 декабря 2018 г.
2. Гардинер, Энтони (1997). Справочник по математической олимпиаде: Введение в решение задач на основе первых 32 британских математических олимпиад 1965–1996 гг . Oxford University Press. стр. 26. ISBN 978-0-19-850105-3.
3. Хендерсон, Энн (2014). Дислексия, дискалькулия и математика: практическое руководство (2-е изд.). Routledge. стр. 62. ISBN 978-1-136-63662-2.
4. Адлер, Ирвинг (1960). Гигантская золотая книга математики: исследование мира чисел и пространства . Golden Press. стр. 16. OCLC  6975809.
5. Лефф, Лоуренс С. (2000). Математическая рабочая тетрадь для SAT I. Образовательная серия Barron's. стр. 360. ISBN 978-0-7641-0768-9.
6. Дадли, Андервуд (1978). "Раздел 2: Уникальная факторизация". Элементарная теория чисел (2-е изд.). WH Freeman and Co. стр. 10. ISBN 978-0-7167-0076-0.
7. Серпинский, Вацлав (1988). Элементарная теория чисел. Математическая библиотека Северной Голландии. Т. 31 (2-е изд.). Elsevier. С. 113. ISBN 978-0-08-096019-7.
8. Ziegler, Günter M. (2004). «Великие гонки за рекордами простых чисел». Notices of the American Mathematical Society . 51 (4): 414–416. MR  2039814.
9. Стиллвелл, Джон (1997). Числа и геометрия. Бакалаврские тексты по математике. Springer. стр. 9. ISBN 978-0-387-98289-2.
10. Серпинский, Вацлав (1964). Выборка проблем по теории чисел . Нью-Йорк: Macmillan. С. 40. MR  0170843.
11. Натансон, Мелвин Б. (2000). «Обозначения и соглашения». Элементарные методы в теории чисел . Выпускные тексты по математике. Том 195. Springer. ISBN 978-0-387-22738-2. МР  1732941.
12. Фатикони, Теодор Г. (2012). Математика бесконечности: Путеводитель по великим идеям. Чистая и прикладная математика: серия текстов, монографий и трактатов издательства Wiley. Т. 111 (2-е изд.). John Wiley & Sons. стр. 44. ISBN 978-1-118-24382-4.
13. Bruins, Evert Marie, обзор в Mathematical Reviews of Gillings, RJ (1974). «The recto of Rhind Mathematical Papyrus. How did the ancient Egyptian scribe preparation it?». Архив для History of Exact Sciences . 12 (4): 291–298. doi :10.1007/BF01307175. MR  0497458. S2CID  121046003.
14. Stillwell, John (2010). Математика и ее история. Бакалаврские тексты по математике (3-е изд.). Springer. стр. 40. ISBN 978-1-4419-6052-8.
15. Pomerance, Carl (декабрь 1982 г.). «Поиск простых чисел». Scientific American . 247 (6): 136–147. Bibcode : 1982SciAm.247f.136P. doi : 10.1038/scientificamerican1282-136. JSTOR  24966751.
16. Mollin, Richard A. (2002). "Краткая история факторизации и проверки простоты до н. э. (до компьютеров)". Mathematics Magazine . 75 (1): 18–29. doi :10.2307/3219180. JSTOR  3219180. MR  2107288.
17. О'Коннор, Джон Дж.; Робертсон, Эдмунд Ф. «Абу Али аль-Хасан ибн аль-Хайсам». MacTutor Архив истории математики . Университет Сент-Эндрюс .
18. Sandifer 2007, 8. Малая теорема Ферма (ноябрь 2003 г.), стр. 45
19. Сандифер, К. Эдвард (2014). Как Эйлер сделал даже больше. Математическая ассоциация Америки. стр. 42. ISBN 978-0-88385-584-3.
20. Коши, Томас (2002). Элементарная теория чисел с приложениями. Academic Press. стр. 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 Monographs in Mathematics. Springer. стр. 11. ISBN 978-3-540-66289-1.
23. Чебычев, П. (1852). «Мемуар о премьерных именах» (PDF) . Журнал чистой и прикладной математики . Серия 1 (на французском языке): 366–390.. (Доказательство постулата: 371–382). См. также Mémoires de l'Académie Impériale des Sciences de St. Pétersbourg, vol. 7, стр. 15–33, 1854 г.
24. Апостол, Том М. (2000). «Столетняя история теоремы о простых числах». В Bambah, RP; Dumir, VC; Hans-Gill, RJ (ред.). Теория чисел . Тенденции в математике. Базель: Birkhäuser. стр. 1–14. MR  1764793.
25. Апостол, Том М. (1976). "7. Теорема Дирихле о простых числах в арифметических прогрессиях". Введение в аналитическую теорию чисел . Нью-Йорк; Гейдельберг: Springer-Verlag. С. 146–156. MR  0434929.
26. Шабер, Жан-Люк (2012). История алгоритмов: от Pebble до Microchip. Springer. стр. 261. ISBN 978-3-642-18192-4.
27. Розен, Кеннет Х. (2000). "Теорема 9.20. Тест Прота на простоту". Элементарная теория чисел и ее приложения (4-е изд.). Эддисон-Уэсли. стр. 342. ISBN 978-0-201-87073-2.
28. Купер, С. Барри; Ходжес, Эндрю (2016). Былое и будущее Тьюринга. Cambridge University Press. С. 37–38. ISBN 978-1-107-01083-3.
29. Розен 2000, стр. 245.
30. Бейлер, Альберт Х. (1999) [1966]. Развлечения в теории чисел: Королева математики развлекает. Дувр. стр. 2. ISBN 978-0-486-21096-4. OCLC  444171535.
31. Кац, Шауль (2004). «Берлинские корни – воплощение сионизма: этос чистой математики и начало Института математики Эйнштейна в Еврейском университете в Иерусалиме». Наука в контексте . 17 (1–2): 199–234. doi :10.1017/S0269889704000092. MR  2089305. S2CID  145575536.
32. Kraft, James S.; Washington, Lawrence C. (2014). Элементарная теория чисел. Учебники по математике. CRC Press. стр. 7. ISBN 978-1-4987-0269-0.
33. Бауэр, Крейг П. (2013). Секретная история: История криптологии. Дискретная математика и ее приложения. CRC Press. стр. 468. ISBN 978-1-4665-6186-1.
34. Клее, Виктор ; Вагон, Стэн (1991). Старые и новые нерешенные проблемы в плоской геометрии и теории чисел. Математические изложения Дольчиани. Т. 11. Cambridge University Press. С. 224. ISBN 978-0-88385-315-3.
35. Neale 2017, стр. 18, 47.
36. Колдуэлл, Крис К.; Реддик, Анджела; Сюн, Йенг; Келлер, Уилфрид (2012). «История простоты числа один: выборка источников». Журнал целочисленных последовательностей . 15 (9): Статья 12.9.8. MR  3005523.Для подборки цитат из и о древнегреческих позициях относительно статуса 1 и 2 см., в частности, стр. 3–4. Для исламских математиков см. стр. 6.
37. Таран, Леонардо (1981). Спевсипп Афинский: Критическое исследование с подборкой связанных текстов и комментариев. Philosophia Antiqua: Серия монографий по античной философии. Т. 39. Brill. С. 35–38. ISBN 978-90-04-06505-5.
38. Колдуэлл и др. 2012, стр. 7–13. См., в частности, записи о Стевине, Бранкере, Уоллисе и Престете.
39. Колдуэлл и др. 2012, стр. 6-7.
40. Колдуэлл и др. 2012, стр. 15.
41. Колдуэлл, Крис К.; Сюн, Йенг (2012). «Какое наименьшее простое число?» (PDF) . Журнал целочисленных последовательностей . 15 (9): Статья 12.9.7. MR  3005530.
42. Конвей и Гай 1996, стр. 130.
43. Ризель, Ганс (1994). Простые числа и компьютерные методы факторизации (2-е изд.). Базель, Швейцария: Birkhäuser. стр. 36. doi :10.1007/978-1-4612-0251-6. ISBN 978-0-8176-3743-9. МР  1292250.
44. Conway, John Horton ; Guy, Richard K. (1996). Книга чисел . Нью-Йорк: Copernicus. стр. 129–130. doi :10.1007/978-1-4612-4072-3. ISBN 978-0-387-97993-9. МР  1411676.
45. Подробности см. Серпинский 1988, с. 245. О сумме делителей см. Sandifer, C. Edward (2007). Как Эйлер это сделал. МАА Спектр. Математическая ассоциация Америки. п. 59. ИСБН 978-0-88385-563-8.
46. Смит, Карл Дж. (2011). Природа математики (12-е изд.). Cengage Learning. стр. 188. ISBN 978-0-538-73758-6.
47. Дадли 1978, Раздел 2, Теорема 2, стр. 16; Нил, Вики (2017). Закрытие разрыва: Поиски понимания простых чисел . Oxford University Press. стр. 107. ISBN 978-0-19-109243-5.
48. du Sautoy, Marcus (2003). Музыка простых чисел: поиск решения величайшей тайны математики . Harper Collins. стр. 23. ISBN 978-0-06-093558-0.
49. Дадли 1978, Раздел 2, Лемма 5, стр. 15; Хиггинс, Питер М. (1998). Математика для любознательных. Oxford University Press. стр. 77–78. ISBN 978-0-19-150050-3.
50. Ротман, Джозеф Дж. (2000). Первый курс абстрактной алгебры (2-е изд.). Prentice Hall. Задача 1.40, стр. 56. ISBN 978-0-13-011584-3.
51. Письмо на латыни от Гольдбаха Эйлеру, июль 1730 г.
52. Фюрстенберг, Гарри (1955). «О бесконечности простых чисел». American Mathematical Monthly . 62 (5): 353. doi :10.2307/2307043. JSTOR  2307043. MR  0068566.
53. Рибенбойм, Пауло (2004). Маленькая книга больших простых чисел. Берлин; Нью-Йорк: Springer-Verlag. стр. 4. ISBN 978-0-387-20169-6.
54. Элементы Евклида , Книга IX, Предложение 20. См. английский перевод доказательства Евклида Дэвида Джойса или Уильямсон, Джеймс (1782). Элементы Евклида, с диссертациями. Оксфорд: Clarendon Press . С. 63. OCLC  642232959.
55. Варди, Илан (1991). Вычислительные развлечения в Mathematica . Addison-Wesley. стр. 82–89. ISBN 978-0-201-52989-0.
56. Матиясевич, Юрий В. (1999). «Формулы простых чисел». Табачников , Серж (ред.). Квант Селекта: Алгебра и анализ . Том. II. Американское математическое общество . стр. 13–24. ISBN 978-0-8218-1915-9.
57. Mackinnon, Nick (июнь 1987). «Формулы простых чисел». The Mathematical Gazette . 71 (456): 113–114. doi :10.2307/3616496. JSTOR  3616496. S2CID  171537609.
58. Райт, Э. М. (1951). «Функция, представляющая простое число». American Mathematical Monthly . 58 (9): 616–618. doi :10.2307/2306356. JSTOR  2306356.
59. Гай 2013, стр. vii.
60. Гай 2013, C1 Гипотеза Гольдбаха, стр. 105–107.
61. Оливейра и Силва, Томас; Герцог, Зигфрид; Парди, Сильвио (2014). «Эмпирическая проверка гипотезы даже Гольдбаха и вычисление простых промежутков до 4 ⋅ 10 18 {\displaystyle 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). «О константе Шнирельмана». Annali della Scuola Normale Superiore di Pisa . 22 (4): 645–706. MR  1375315. Архивировано из оригинала 09 февраля 2022 г. Проверено 23 января 2018 г.
65. Rassias, Michael Th. (2017). Проблема Гольдбаха: Избранные темы. Cham: Springer. стр. vii. doi :10.1007/978-3-319-57914-6. ISBN 978-3-319-57912-2. МР  3674356.
66. Коши 2002, Теорема 2.14, стр. 109. Ризель 1994 приводит похожий аргумент, используя праймориал вместо факториала.
67. Riesel 1994, «Большие разрывы между последовательными простыми числами», стр. 78–79.
68. Слоан, Н. Дж. А. (ред.). «Последовательность A100964 (Наименьшее простое число, которое начинает простой промежуток не менее 2n)». Онлайновая энциклопедия целочисленных последовательностей . Фонд OEIS.
69. Ribenboim 2004, Промежутки между простыми числами, стр. 186–192.
70. Ribenboim 2004, стр. 183.
71. Чан, Джоэл (февраль 1996 г.). «Prime time!». Math Horizons . 3 (3): 23–25. doi :10.1080/10724117.1996.11974965. JSTOR  25678057.Обратите внимание, что Чан называет гипотезу Лежандра «постулатом Серпинского».
72. Рибенбойм 2004, Гипотеза простых кортежей, стр. 201–202. ${\displaystyle k}$
73. Сандифер 2007, Глава 35, Оценка Базельской проблемы, стр. 205–208.
74. Огилви, CS ; Андерсон, JT (1988). Экскурсии в теорию чисел. Dover Publications Inc., стр. 29–35. ISBN 978-0-486-25778-5.
75. Апостол 1976, Раздел 1.6, Теорема 1.13
76. Апостол 1976, Раздел 4.8, Теорема 4.12
77. Miller, Steven J.; Takloo-Bighash, Ramin (2006). Приглашение в современную теорию чисел. Princeton University Press. С. 43–44. ISBN 978-0-691-12060-7.
78. Крэндалл и Померанс 2005, стр. 6.
79. Crandall & Pomerance 2005, Раздел 3.7, Подсчет простых чисел, стр. 152–162.
80. Crandall & Pomerance 2005, стр. 10.
81. du Sautoy, Marcus (2011). «Каковы шансы, что ваш номер телефона — простое число?». Загадки чисел: математическая одиссея через повседневную жизнь . St. Martin's Press. стр. 50–52. ISBN 978-0-230-12028-0.
82. Апостол 1976, Раздел 4.6, Теорема 4.7
83. Гельфанд, ИМ ; Шен, Александр (2003). Алгебра. Springer. стр. 37. ISBN 978-0-8176-3677-7.
84. Моллин, Ричард А. (1997). Фундаментальная теория чисел с приложениями. Дискретная математика и ее приложения. CRC Press. стр. 76. ISBN 978-0-8493-3987-5.
85. Crandall & Pomerance 2005, Теорема 1.1.5, стр. 12.
86. Грин, Бен ; Тао, Теренс (2008). «Простые числа содержат произвольно длинные арифметические прогрессии». Annals of Mathematics . 167 (2): 481–547. arXiv : math.NT/0404188 . doi :10.4007/annals.2008.167.481. S2CID  1883951.
87. Хуа, ЛК (2009) [1965]. Аддитивная теория простых чисел . Переводы математических монографий. Том 13. Провиденс, Род-Айленд: Американское математическое общество. С. 176–177. ISBN 978-0-8218-4942-2. MR  0194404. OCLC  824812353.
88. Последовательность этих простых чисел, начиная с , указана Лавой, Паоло Пьетро; Бальзаротти, Джорджо (2010). «Глава 33. Формула удачи». 103 математических любопытства: Teoria dei numeri, delle cifre e delle relazioni nella matematica contemporanea (на итальянском языке). Ulrico Hoepli Editore SpA с. 133. ИСБН ${\displaystyle n=1}$ ${\displaystyle n=0}$ 978-88-203-5804-4.
89. Чемберленд, Марк (2015). «Числа Хегнера». Single Digits: In Praise of Small Numbers . Princeton University Press. С. 213–215. ISBN 978-1-4008-6569-7.
90. Guy, Richard (2013). "A1 Простые значения квадратичных функций". Нерешенные задачи по теории чисел . Задачники по математике (3-е изд.). Springer. стр. 7–10. ISBN 978-0-387-26677-0.
91. Паттерсон, С. Дж. (1988). Введение в теорию дзета-функции Римана. Cambridge Studies in Advanced Mathematics. Том 14. Cambridge University Press, Кембридж. стр. 1. doi : 10.1017/CBO9780511623707. ISBN 978-0-521-33535-5. МР  0933558.
92. Борвейн, Питер ; Чой, Стивен; Руни, Брендан; Вайратмюллер, Андреа (2008). Гипотеза Римана: Ресурс для любителей и виртуозов. CMS Books in Mathematics/Ouvrages de Mathématiques de la SMC. Нью-Йорк: Springer. С. 10–11. doi :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.
96. Борвейн и др. 2008, с. 18.
97. Натансон 2000, Глава 9, Теорема о простых числах, стр. 289–324.
98. Загир, Дон (1977). «Первые 50 миллионов простых чисел». The Mathematical Intelligencer . 1 (S2): 7–19. doi :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.
106. Чайлдресс, Нэнси (2009). Теория полей классов. Universitext. Springer, Нью-Йорк. С. 8–11. doi :10.1007/978-0-387-72490-4. ISBN 978-0-387-72489-8. МР  2462595.См. также стр. 64.
107. Эриксон, Марти; Ваззана, Энтони; Гарт, Дэвид (2016). Введение в теорию чисел. Учебники по математике (2-е изд.). Бока-Ратон, Флорида: CRC Press. стр. 200. ISBN 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). Конкретная абстрактная алгебра: от чисел до базисов Грёбнера. Кембридж: Cambridge University Press. стр. 127. doi :10.1017/CBO9780511804229. ISBN 978-0-521-53410-9. МР  2014325.
111. Лауритцен 2003, следствие 3.5.14, с. 133; Лемма 3.5.18, с. 136.
112. Крафт и Вашингтон 2014, Раздел 12.1, Суммы двух квадратов, стр. 297–301.
113. Eisenbud, David (1995). Коммутативная алгебра . Graduate Texts in Mathematics. Vol. 150. Berlin; New York: Springer-Verlag. Раздел 3.3. doi :10.1007/978-1-4612-5350-1. ISBN 978-0-387-94268-1. МР  1322960.
114. Шафаревич, Игорь Р. (2013). "Определение Spec ⁡ A {\displaystyle \operatorname {Spec} A}". Basic Algebraic Geometry 2: Schemes and Complex Manifolds (3-е изд.). Springer, Heidelberg. стр. 5. doi :10.1007/978-3-642-38010-5. ISBN 978-3-642-38009-9. МР  3100288.
115. Нойкирх, Юрген (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.
116. Нойкирх 1999, Раздел I.7, стр. 38
117. Стивенхаген, П.; Ленстра, Х. В. младший (1996). «Чеботарев и его теорема о плотности». The Mathematical Intelligencer . 18 (2): 26–37. CiteSeerX 10.1.1.116.9409 . doi :10.1007/BF03027290. MR  1395088. S2CID  14089091. 
118. Холл, Маршалл (2018). Теория групп. Dover Books on Mathematics. Courier Dover Publications. ISBN 978-0-486-81690-6.О теоремах Силова см. стр. 43; о теореме Лагранжа см. стр. 12; о теореме Бернсайда см. стр. 143.
119. Брайант, Джон; Сангвин, Кристофер Дж. (2008). Насколько круглый ваш круг?: Где встречаются инженерия и математика . Princeton University Press. стр. 178. ISBN 978-0-691-13118-4.
120. Харди, Годфри Гарольд (2012) [1940]. Апология математика . Cambridge University Press. стр. 140. ISBN 978-0-521-42706-7OCLC  922010634. Никто еще не обнаружил какой-либо военной цели, которой могла бы служить теория чисел или теория относительности, и маловероятно, что кто-то сделает это в течение многих лет .
121. Гиблин, Питер (1993). Простые числа и программирование . Cambridge University Press. стр. 39. ISBN 978-0-521-40988-9.
122. Гиблин 1993, стр. 54
123. Riesel 1994, стр. 220.
124. Буллинк, Маартен (2010). «История таблиц множителей с примечаниями о рождении теории чисел 1657–1817». Revue d'Histoire des Mathématiques . 16 (2): 133–216.
125. Вагстафф, Сэмюэл С. младший (2013). Радость факторизации. Студенческая математическая библиотека. Том 68. Американское математическое общество. стр. 191. ISBN 978-1-4704-1048-3.
126. Крэндалл, Ричард ; Померанс, Карл (2005). Простые числа: вычислительная перспектива (2-е изд.). Springer. стр. 121. ISBN 978-0-387-25282-7.
127. Farach-Colton, Martín ; Tsai, Meng-Tsung (2015). «О сложности вычисления таблиц простых чисел». В Elbassioni, Khaled; Makino, Kazuhisa (ред.). Algorithms and Computation: 26th International Symposium, ISAAC 2015, Nagoya, Japan, December 9-11, 2015, Proceedings . Lecture Notes in Computer Science. Vol. 9472. Springer. pp. 677–688. arXiv : 1504.05240 . doi :10.1007/978-3-662-48971-0_57. ISBN 978-3-662-48970-3.
128. Гривз, Джордж (2013). Сита в теории чисел. Ergebnisse der Mathematik und ihrer Grenzgebiete (3. Folge). Том. 43. Спрингер. п. 1. ISBN 978-3-662-04658-6.
129. Hromkovič, Juraj (2001). "5.5 Библиографические замечания". Алгоритмика для сложных проблем . Тексты по теоретической информатике. Серия EATCS. ​​Springer-Verlag, Берлин. стр. 383–385. doi :10.1007/978-3-662-04616-6. ISBN 978-3-540-66860-2. MR  1843669. S2CID  31159492.
130. Koblitz, Neal (1987). "Глава V. Простота и факторизация". Курс теории чисел и криптографии . Graduate Texts in Mathematics. Том 114. Springer-Verlag, Нью-Йорк. С. 112–149. doi :10.1007/978-1-4684-0310-7_5. ISBN 978-0-387-96576-5. МР  0910297.
131. Pieprzyk, Josef; Hardjono, Thomas; Seberry, Jennifer (2013). "2.3.9 Вероятностные вычисления". Основы компьютерной безопасности . Springer. стр. 51–52. ISBN 978-3-662-07324-7.
132. Tao, Terence (2010). "1.11 Тест на простоту AKS". Эпсилон комнаты, II: Страницы третьего года математического блога . Аспирантура по математике. Том 117. Провиденс, Род-Айленд: Американское математическое общество. стр. 82–86. doi :10.1090/gsm/117. ISBN 978-0-8218-5280-4. МР  2780010.
133. Atkin, A OL ; Morain, F. (1993). "Эллиптические кривые и доказательство простоты" (PDF) . Mathematics of Computation . 61 (203): 29–68. Bibcode :1993MaCom..61...29A. doi : 10.1090/s0025-5718-1993-1199989-x . JSTOR  2152935. MR  1199989.
134. Morain, F. (2007). «Реализация асимптотически быстрой версии алгоритма доказательства простоты эллиптической кривой». Mathematics of Computation . 76 (257): 493–505. arXiv : math/0502097 . Bibcode :2007MaCom..76..493M. doi :10.1090/S0025-5718-06-01890-4. MR  2261033. S2CID  133193.
135. Lenstra, HW Jr. ; Pomerance, Carl (2019). "Проверка простоты с гауссовыми периодами" (PDF) . Журнал Европейского математического общества . 21 (4): 1229–1269. doi :10.4171/JEMS/861. hdl :21.11116/0000-0005-717D-0. MR  3941463. S2CID  127807021.
136. Карл Померанс ; Джон Л. Селфридж ; Сэмюэл С. Вагстафф-младший (июль 1980 г.). «Псевдопростые числа до 25·109» (PDF) . Математика вычислений . 35 (151): 1003–1026. doi : 10.1090/S0025-5718-1980-0572872-7 . JSTOR  2006210.
137. Роберт Бейли; Сэмюэл С. Вагстафф, младший (октябрь 1980 г.). «Псевдопростые числа Лукаса» (PDF) . Математика вычислений . 35 (152): 1391–1417. doi : 10.1090/S0025-5718-1980-0583518-6 . JSTOR  2006406. MR  0583518.
138. Monier, Louis (1980). «Оценка и сравнение двух эффективных вероятностных алгоритмов проверки простоты». Теоретическая информатика . 12 (1): 97–108. doi : 10.1016/0304-3975(80)90007-9 . MR  0582244.
139. Тао, Теренс (2009). "1.7 Тест Люка-Лемера для простых чисел Мерсенна". Наследие Пуанкаре, страницы второго года математического блога. Часть I. Провиденс, Род-Айленд: Американское математическое общество. стр. 36–41. ISBN 978-0-8218-4883-8. МР  2523047.
140. Крафт и Вашингтон 2014, стр. 41.
141. Например, см. Guy 2013, A3 Mersenne simples. Repunits. Fermat numbers. Простые числа формы k ⋅ 2 n + 1 {\displaystyle k\cdot 2^{n}+1} . стр. 13–21.
142. "Рекордное простое число из 12 миллионов цифр принесло приз в размере 100 000 долларов". Electronic Frontier Foundation. 14 октября 2009 г. Получено 04.01.2010 г.
143. "EFF Cooperative Computing Awards". Electronic Frontier Foundation. 29-02-2008 . Получено 04-01-2010 .
144. "PrimeGrid's Seventeen or Bust Subproject" (PDF) . Получено 2017-01-03 .
145. Колдуэлл, Крис К. "Двадцатка лучших: самые большие известные простые числа". The Prime Pages . Получено 03.01.2017 .
146. Колдуэлл, Крис К. "The Top Twenty: Factorial". The Prime Pages . Получено 2017-01-03 .
147. Рибенбойм 2004, стр. 4.
148. Колдуэлл, Крис К. "The Top Twenty: Primorial". The Prime Pages . Получено 2017-01-03 .
149. Колдуэлл, Крис К. "The Top Twenty: Twin Primes". The Prime Pages . Получено 2017-01-03 .
150. Крафт и Вашингтон 2014, стр. 275.
151. Хоффштейн, Джеффри; Пайфер, Джилл ; Сильверман, Джозеф Х. (2014). Введение в математическую криптографию. Бакалаврские тексты по математике (2-е изд.). Springer. стр. 329. ISBN 978-1-4939-1711-2.
152. Померанс, Карл (1996). «Сказка о двух ситах». Notices of the American Mathematical Society . 43 (12): 1473–1485. MR  1416721.
153. Эммануэль Томе, «795-битная факторизация и дискретные логарифмы», 2 декабря 2019 г.
154. Риффель, Элеанор Г .; Полак, Вольфганг Х. (2011). «Глава 8. Алгоритм Шора». Квантовые вычисления: нежное введение . MIT Press. стр. 163–176. ISBN 978-0-262-01506-6.
155. Мартин-Лопес, Энрике; Лэйнг, Энтони; Лоусон, Томас; Альварес, Роберто; Чжоу, Сяо-Ци; О'Брайен, Джереми Л. (12 октября 2012 г.). «Экспериментальная реализация алгоритма квантовой факторизации Шора с использованием рециркуляции кубитов». Nature Photonics . 6 (11): 773–776. arXiv : 1111.4147 . Bibcode :2012NaPho...6..773M. doi :10.1038/nphoton.2012.259. S2CID  46546101.
156. Чиргвин, Ричард (9 октября 2016 г.). «Исследователи предупреждают, что криптовалютам нужно больше прозрачности». The Register .
157. Хоффштейн, Пайфер и Сильверман 2014, Раздел 2.3, Обмен ключами Диффи–Хеллмана, стр. 65–67.
158. Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л.; Стайн , Клиффорд (2001) [1990]. "11.3 Универсальное хеширование". Введение в алгоритмы (2-е изд.). MIT Press и McGraw-Hill. стр. 232–236. ISBN 0-262-03293-7.Для -независимого хеширования см. задачу 11–4, стр. 251. О заслугах Картера и Вегмана см. примечания к главе, стр. 252. ${\displaystyle k}$
159. Гудрич, Майкл Т.; Тамассиа , Роберто (2006). Структуры данных и алгоритмы в Java (4-е изд.). John Wiley & Sons. ISBN 978-0-471-73884-8.См. «Квадратичное зондирование», стр. 382 и упражнение C–9.9, стр. 415.
160. Киртланд, Джозеф (2001). Идентификационные номера и схемы контрольных цифр. Материалы для занятий в классе. Том 18. Математическая ассоциация Америки. С. 43–44. ISBN 978-0-88385-720-5.
161. Deutsch, P. (май 1996 г.). Спецификация формата сжатых данных ZLIB версии 3.3. Сетевая рабочая группа. doi : 10.17487/RFC1950 . RFC 1950.
162. Кнут, Дональд Э. (1998). "3.2.1 Линейная конгруэнтная модель". Искусство программирования, т. 2: Получисленные алгоритмы (3-е изд.). Эддисон-Уэсли. стр. 10–26. ISBN 978-0-201-89684-8.
163. Мацумото, Макото; Нисимура, Такудзи (1998). «Вихрь Мерсенна: 623-мерно равнораспределенный равномерный генератор псевдослучайных чисел». Труды ACM по моделированию и компьютерному моделированию . 8 (1): 3–30. CiteSeerX 10.1.1.215.1141 . doi :10.1145/272991.272995. S2CID  3332028. 
164. Рот, К. Ф. (1951). «О проблеме Хейльбронна». Журнал Лондонского математического общества . Вторая серия. 26 (3): 198–204. doi :10.1112/jlms/s1-26.3.198. MR  0041889.
165. Кокс, Дэвид А. (2011). «Почему Эйзенштейн доказал критерий Эйзенштейна и почему Шёнеман открыл его первым» (PDF) . American Mathematical Monthly . 118 (1): 3–31. CiteSeerX 10.1.1.398.3440 . doi :10.4169/amer.math.monthly.118.01.003. S2CID  15978494. Архивировано из оригинала (PDF) 2023-03-26 . Получено 2018-01-25 . 
166. Ланг, Серж (2002). Алгебра . Выпускные тексты по математике. Том 211. Берлин; Нью-Йорк: Springer-Verlag . doi :10.1007/978-1-4613-0041-0. ISBN 978-0-387-95385-4. МР  1878556., Раздел II.1, стр. 90
167. Шуберт, Хорст (1949). «Die eindeutige Zerlegbarkeit eines Knotens in Primknoten». С.-Б Гейдельбергер Акад. Висс. Матем.-Нат. кл . 1949 (3): 57–104. МР  0031733.
168. Милнор, Дж. (1962). «Уникальная теорема разложения для 3-многообразий». American Journal of Mathematics . 84 (1): 1–7. doi :10.2307/2372800. JSTOR  2372800. MR  0142125.
169. Боклан и Конвей (2017) также включают , который не имеет этой формы. ${\displaystyle 2^{0}+1=2}$
170. Křížek, Michal; Luca, Florian; Somer, Lawrence (2001). 17 лекций по числам Ферма: от теории чисел к геометрии. CMS Books in Mathematics. Том 9. Нью-Йорк: Springer-Verlag. С. 1–2. doi :10.1007/978-0-387-21850-2. ISBN 978-0-387-95332-8. МР  1866957.
171. Боклан, Кент Д.; Конвей, Джон Х. (январь 2017 г.). «Ожидайте не более одной миллиардной от нового простого числа Ферма t !». The Mathematical Intelligencer . 39 (1): 3–5. arXiv : 1605.01371 . doi : 10.1007/s00283-016-9644-3. S2CID  119165671.
172. Глисон, Эндрю М. (1988). «Трисекция угла, семиугольник и трискайдекагон». American Mathematical Monthly . 95 (3): 185–194. doi :10.2307/2323624. JSTOR  2323624. MR  0935432.
173. Циглер, Гюнтер М. (2015). «Пушки по воробьям». Информационный бюллетень Европейского математического общества (95): 25–31. MR  3330472.
174. Петерсон, Иварс (28 июня 1999 г.). «Возвращение Зеты». MAA Online . Архивировано из оригинала 20 октября 2007 г. Получено 14 марта 2008 г.
175. Хейс, Брайан (2003). «Вычислительная наука: спектр Римания». American Scientist . 91 (4): 296–300. doi :10.1511/2003.26.3349. JSTOR  27858239. S2CID  16785858.
176. Бенгтссон, Ингемар; Жычковский, Кароль (2017). Геометрия квантовых состояний: введение в квантовую запутанность (Второе изд.). Кембридж: Cambridge University Press . С. 313–354. ISBN 978-1-107-02625-4. OCLC  967938939.
177. Чжу, Хуанцзюнь (2010). «SIC POVM и группы Клиффорда в простых измерениях». Журнал физики A: Математическое и теоретическое . 43 (30): 305305. arXiv : 1003.3591 . Bibcode :2010JPhA...43D5305Z. doi :10.1088/1751-8113/43/30/305305. S2CID  118363843.
178. Goles, E.; Schulz, O.; Markus, M. (2001). «Выбор простых чисел циклов в модели хищник-жертва». Сложность . 6 (4): 33–38. Bibcode : 2001Cmplx...6d..33G. doi : 10.1002/cplx.1040.
179. Кампос, Пауло РА; де Оливейра, Вивиан М.; Джиро, Роналду; Гальвао, Дуглас С. (2004). «Появление простых чисел как результат эволюционной стратегии». Письма о физических отзывах . 93 (9): 098107. arXiv : q-bio/0406017 . Бибкод : 2004PhRvL..93i8107C. doi : 10.1103/PhysRevLett.93.098107. PMID  15447148. S2CID  88332.
180. "Вторжение выводка". The Economist . 6 мая 2004 г. Получено 26 ноября 2006 г.
181. Циммер, Карл (15 мая 2015 г.). «Бамбуковые математики». Феномены: Ткацкий станок. National Geographic . Получено 22 февраля 2018 г.
182. Хилл, Питер Дженсен, изд. (1995). Спутник Мессиана. Портленд, Орегон: Amadeus Press. Бывший. 13.2 Messe de la Pentecôte 1 «Вход». ISBN 978-0-931340-95-6.
183. Pomerance, Carl (2004). «Простые числа и поиск внеземного разума» (PDF) . В Hayes, David F.; Ross, Peter (ред.). Математические приключения для студентов и любителей . MAA Spectrum. Вашингтон, округ Колумбия: Математическая ассоциация Америки. стр. 3–6. ISBN 978-0-88385-548-5. МР  2085842.
184. GrrlScientist (16 сентября 2010 г.). «Загадочное ночное происшествие с собакой». Наука. The Guardian . Получено 22 февраля 2010 г.
185. Шиллингер, Лизл (9 апреля 2010 г.). «Рассчитывая друг на друга». Воскресный обзор книги. The New York Times .

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

• «Простое число». Энциклопедия математики . Издательство EMS . 2001 [1994].
• Колдуэлл, Крис, The Prime Pages на primes.utm.edu.
• Простые числа в программе In Our Time на BBC
• Пакет Plus для учителей и учеников: простые числа из Plus, бесплатного онлайн-журнала по математике, выпускаемого в рамках проекта «Математика тысячелетия» Кембриджского университета.

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

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