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

«Прайм» перенаправляется сюда. Чтобы узнать о других значениях, см. Прайм (значения) .

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

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

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

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

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

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

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

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

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

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

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

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

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

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

История

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

$p(n)=a+bn$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Основные статьи: теорема Дирихле об арифметических прогрессиях и теорема Грина – Тао.

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

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

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

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

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

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

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

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

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

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

$n^{2}-n+41$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Теория групп

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

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

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

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

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

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

Основная статья: Пробное подразделение

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

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

Сита

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

Основная статья: Решето Эратосфена

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Биология

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

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

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

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

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

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

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

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