Простое число (или простое ) представляет собой натуральное число , большее 1 , который не является продуктом двух меньше натуральных чисел. Натуральное число больше 1, которое не является простым, называется составным числом . Например, число 5 является простым, потому что единственные способы записать его как продукт, 1 × 5 или 5 × 1 , включают само число 5. Однако число 4 составное, потому что это произведение ( 2 × 2 ), в котором оба числа меньше 4. Простые числа занимают центральное место в теории чисел в силу фундаментальной арифметической теоремы : каждое натуральное число больше 1 либо само простое, либо можно разложить на множителикак произведение простых чисел, уникальное в соответствии с их порядком.
Свойство быть простым называется первичностью . Простой, но медленный метод проверки простоты заданного числа, называется пробным отделением , проверяет, кратно любому целому числу от 2 до . Более быстрые алгоритмы включают тест простоты Миллера – Рабина , который является быстрым, но имеет небольшую вероятность ошибки, и тест простоты AKS , который всегда дает правильный ответ за полиномиальное время, но слишком медленный, чтобы быть практичным. Особенно быстрые методы доступны для чисел в специальных формах, таких как числа Мерсенна . По состоянию на декабрь 2018 года [Обновить]самым большим известным простым числом является простое число Мерсенна с 24 862 048 десятичными знаками . [1]
Есть бесконечно много простых чисел, так как свидетельствуют Евклид около 300 г. до н. Нет известной простой формулы, отделяющей простые числа от составных. Однако распределение простых чисел в натуральных числах в большом можно смоделировать статистически. Первым результатом в этом направлении является теорема о простых числах , доказанная в конце XIX века, которая гласит, что вероятность того, что случайно выбранное число будет простым, обратно пропорциональна его количеству цифр, то есть его логарифму .
Некоторые исторические вопросы, касающиеся простых чисел, до сих пор не решены. К ним относятся гипотеза Гольдбаха о том , что каждое четное целое число больше 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 являются составными.
В делители натурального числа натуральные числа, которые делят равномерно. Каждое натуральное число имеет как 1, так и само себя в качестве делителя. Если у него есть другой делитель, он не может быть простым. Эта идея приводит к другому, но эквивалентному определению простых чисел: это числа с ровно двумя положительными делителями , 1 и само число. [6] Еще один способ выразить то же самое - число является простым, если оно больше единицы и если ни одно из чисел разделяет равномерно. [7]
Первые 25 простых чисел (все простые числа меньше 100): [8]
- 2 , 3 , 5 , 7 , 11 , 13 , 17 , 19 , 23 , 29 , 31 , 37 , 41 , 43 , 47 , 53 , 59 , 61 , 67 , 71 , 73 , 79 , 83 , 89 , 97 ( последовательность A000040 в OEIS ).
Нет четного числа больше 2 является простым, потому что любое такое число может быть выражено как произведение . Следовательно, каждое простое число, кроме 2, является нечетным числом и называется нечетным простым числом . [9] Аналогичным образом, при записи в обычной десятичной системе все простые числа больше 5 оканчиваются на 1, 3, 7 или 9. Числа, заканчивающиеся другими цифрами, являются составными: десятичные числа, заканчивающиеся на 0, 2, 4, 6 или 8 четные, а десятичные числа, оканчивающиеся на 0 или 5, делятся на 5. [10]
Множество всех простых чисел , иногда обозначается( жирная заглавная P ) [11] или(на доске жирная заглавная буква P). [12]
История
Папирус Ахмес , от около 1550 г. до н.э., имеет египетские дроби разложение различных форм для простых и составных чисел. [13] Однако самые ранние сохранившиеся записи явного изучения простых чисел относятся к древнегреческой математике . Euclid «s элементов (с. 300 до н.э.) доказывает беспредельность простых чисел и основной теоремы арифметики , и показывает , как построить совершенное число от штрихом Mersenne . [14] Другое греческое изобретение, Сито Эратосфена , до сих пор используется для построения списков простых чисел. [15] [16]
Примерно в 1000 году нашей эры исламский математик Ибн аль-Хайтам (Альхазен) нашел теорему Вильсона , охарактеризовав простые числа как числа которые равномерно делят . Он также предположил, что все четные совершенные числа происходят из конструкции Евклида с использованием простых чисел Мерсенна, но не смог это доказать. [17] Другой исламский математик, Ибн аль-Банна аль-Марракуши , заметил, что сито Эратосфена можно ускорить, проверяя только делители до квадратного корня из наибольшего числа, подлежащего проверке. Фибоначчи вернул в Европу нововведения исламской математики. Его книга Liber Abaci (1202) была первой, в которой было описано пробное деление для проверки простоты, опять же с использованием делителей только до квадратного корня. [16]
В 1640 году Пьер де Ферма сформулировал (без доказательства) малую теорему Ферма (позже доказанную Лейбницем и Эйлером ). [18] Ферма также исследовал простоту чисел Ферма. , [19] и Марин Мерсенн изучали простые числа Мерсенна , простые числа вида с участием сам по себе премьер. [20] Кристиан Гольдбах сформулировал гипотезу Гольдбаха , что каждое четное число является суммой двух простых чисел, в письме к Эйлеру 1742 года. [21] Эйлер доказал гипотезу Альхазена (теперь теорема Евклида – Эйлера ) о том, что все четные совершенные числа могут быть построены из простых чисел Мерсенна. [14] Он ввел методы математического анализа в эту область в своих доказательствах бесконечности простых чисел и расходимости суммы обратных простых чисел. . [22] В начале XIX века Лежандр и Гаусс предположили, что как стремится к бесконечности, количество простых чисел до является асимптотическим к, где это натуральный логарифм из. Более слабым следствием такой высокой плотности простых чисел был постулат Бертрана , что для каждого между а также , доказанный в 1852 году Пафнутым Чебышевым . [23] Идеи Бернхарда Римана в его статье 1859 года о дзета-функции набросали схему доказательства гипотезы Лежандра и Гаусса. Хотя тесно связанная гипотеза Римана остается недоказанной, набросок Римана был завершен в 1896 году Адамаром и де ла Валле Пуссенами , и теперь результат известен как теорема о простых числах . [24] Другим важным результатом XIX века была теорема Дирихле об арифметических прогрессиях , согласно которой некоторые арифметические прогрессии содержат бесконечно много простых чисел. [25]
Многие математики работали над тестами на простоту для чисел, больших, чем те, где пробное деление практически применимо. Методы, которые ограничены конкретное число форм включают тест Пипина для чисел Ферма (1877 г.), [26] Proth по теореме (с. 1878), [27] тест на простоту Lucas-Лехмер (возник в 1856), а также обобщенный тест простоты Лукаса . [16]
С 1951 года с помощью этих тестов на компьютерах были найдены все самые большие известные простые числа . [a] Поиск все более крупных простых чисел вызвал интерес за пределами математических кругов благодаря Великому Интернету Mersenne Prime Search и другим проектам распределенных вычислений . [8] [29] Идея о том, что простые числа имеют мало приложений за пределами чистой математики [b], была разрушена в 1970-х годах, когда были изобретены криптография с открытым ключом и криптосистема RSA, взяв за основу простые числа. [32]
Возросшее практическое значение компьютеризированной проверки простоты и факторизации привело к разработке улучшенных методов, способных обрабатывать большое количество неограниченных форм. [15] [33] [34] Математическая теория простых чисел также продвинулась вперед с теоремой Грина – Тао (2004) о том, что существуют сколь угодно длинные арифметические прогрессии простых чисел, и доказательством Итан Чжана 2013 года, что существует бесконечно много простые промежутки ограниченного размера. [35]
Первобытность одного
Большинство ранних греков даже не считали 1 числом [36] [37], поэтому они не могли рассматривать его первичность. Некоторые математики того времени также считали простые числа делением нечетных чисел, поэтому они также не считали 2 простыми. Однако Евклид и большинство других греческих математиков считали 2 простым числом. В средневековые исламские математики в основном следовали за греками при просмотре 1 не является числом. [36] В средние века и в эпоху Возрождения математики начали рассматривать 1 как число, а некоторые из них включили его как первое простое число. [38] В середине 18 века Кристиан Гольдбах в своей переписке с Леонардом Эйлером указал 1 как простое число ; однако сам Эйлер не считал 1 простым. [39] В 19 веке многие математики все еще считали 1 простым [40], а списки простых чисел, в которые входила 1, продолжали публиковаться только в 1956 году. [41] [42]
Если бы определение простого числа было изменено так, чтобы называть 1 простым, многие операторы, включающие простые числа, пришлось бы перефразировать более неудобным образом. Например, основную теорему арифметики нужно перефразировать в терминах факторизации на простые числа больше 1, потому что каждое число будет иметь несколько факторизаций с разным числом копий 1. [40] Точно так же решето Эратосфена не будет работать. правильно, если бы он обрабатывал 1 как простое число, потому что он исключил бы все числа, кратные 1 (то есть все другие числа), и выдал бы только одно число 1. [42] Некоторые другие более технические свойства простых чисел также не выполняются для числа номер 1: например, формулы для тотализирующей функции Эйлера или для функции суммы делителей отличаются для простых чисел, чем для 1. [43] К началу 20-го века математики начали соглашаться с тем, что 1 не следует указывать как премьер, а скорее в своей особой категории как « единица ». [40]
Элементарные свойства
Уникальная факторизация
Запись числа как произведения простых чисел называется факторизацией числа на простые множители . Например:
Термины в продукте называются простыми факторами . Один и тот же простой множитель может встречаться более одного раза; в этом примере есть две копии простого множителяКогда простое число встречается несколько раз, возведение в степень можно использовать для группировки нескольких копий одного и того же простого числа: например, во втором способе записи произведения выше,обозначает квадрат или вторую степень
Центральное значение простых чисел для теории чисел и математики в целом проистекает из фундаментальной теоремы арифметики . [44] Эта теорема утверждает, что каждое целое число больше 1 может быть записано как произведение одного или нескольких простых чисел. Более того, этот продукт уникален в том смысле, что любые две простые факторизации одного и того же числа будут иметь одинаковое количество копий одних и тех же простых чисел, хотя их порядок может отличаться. [45] Итак, хотя существует много разных способов нахождения факторизации с использованием алгоритма целочисленной факторизации , все они должны давать одинаковый результат. Таким образом, простые числа можно рассматривать как «основные строительные блоки» натуральных чисел. [46]
Некоторые доказательства единственности разложения на простые множители основаны на лемме Евклида : если простое число и делит продукт целых чисел а также тогда разделяет или же разделяет (или оба). [47] И наоборот, если число обладает тем свойством, что при делении продукта он всегда делит хотя бы один фактор продукта, тогда должно быть первичным. [48]
Бесконечность
Есть бесконечно много простых чисел. Другими словами, последовательность
- 2, 3, 5, 7, 11, 13, ...
простых чисел никогда не заканчивается. Это утверждение называется теоремой Евклида в честь древнегреческого математика Евклида , поскольку первое известное доказательство этого утверждения приписывается ему. Многие другие доказательства бесконечности простых чисел известны, в том числе аналитического доказательства по Эйлеру , Гольдбах доказательства на основе чисел Ферма , [49] Фюрстенберг доказательство , используя общую топологию , [50] и Куммер элегантного доказательства. [51]
Доказательство Евклида [52] показывает, что любой конечный список простых чисел неполон. Ключевая идея состоит в том, чтобы перемножить простые числа в любом заданном списке и сложить Если список состоит из простых чисел это дает номер
По основной теореме имеет разложение на простые множители
с одним или несколькими основными факторами. делится без остатка на каждый из этих факторов, но имеет остаток единицы при делении на любое из простых чисел в данном списке, поэтому ни один из простых делителей может быть в данном списке. Поскольку не существует конечного списка всех простых чисел, должно быть бесконечно много простых чисел.
Числа, образованные добавлением единицы к произведению наименьших простых чисел, называются числами Евклида . [53] Первые пять из них простые, а шестой -
составное число.
Формулы для простых чисел
Нет известной эффективной формулы для простых чисел. Например, не существует непостоянного многочлена даже от нескольких переменных, принимающего только простые значения. [54] Однако существует множество выражений, которые кодируют все простые числа или только простые числа. Одна из возможных формул основана на теореме Вильсона и генерирует число 2 много раз, а все остальные простые числа - ровно один раз. [55] Существует также набор диофантовых уравнений с девятью переменными и одним параметром со следующим свойством: параметр является простым тогда и только тогда, когда полученная система уравнений имеет решение над натуральными числами. Это можно использовать для получения единой формулы со свойством, что все ее положительные значения являются простыми. [54]
Другие примеры формул, порождающих простые числа, взяты из теорем Миллса и Райта . Они утверждают, что существуют реальные константы а также такой, что
просты для любого натурального числа в первой формуле и любое количество показателей во второй формуле. [56] Здесьпредставляет функцию пола , наибольшее целое число, меньшее или равное рассматриваемому числу. Однако они бесполезны для генерации простых чисел, так как простые числа должны быть сгенерированы первыми, чтобы вычислить значения или же [54]
Открытые вопросы
Было высказано много предположений о простых числах. Часто имея элементарную формулировку, многие из этих гипотез выдерживали доказательство в течение десятилетий: все четыре проблемы Ландау с 1912 года до сих пор не решены . [57] Одна из них - это гипотеза Гольдбаха , которая утверждает, что каждое четное целое числобольше 2 можно записать как сумму двух простых чисел. [58] По состоянию на 2014 г.[Обновить], эта гипотеза проверена для всех чисел до [59] Были доказаны более слабые утверждения, чем это, например, теорема Виноградова утверждает, что каждое достаточно большое нечетное целое число может быть записано как сумма трех простых чисел. [60] Теорема Чена гласит, что каждое достаточно большое четное число может быть выражено как сумма простого и полупростого числа (произведение двух простых чисел). [61] Кроме того, любое четное целое число больше 10 можно записать как сумму шести простых чисел. [62] Раздел теории чисел, изучающий такие вопросы, называется аддитивной теорией чисел . [63]
Другой тип проблем касается пробелов между простыми числами, разницы между последовательными простыми числами. Существование сколь угодно больших промежутков между простыми числами можно увидеть, заметив, что последовательность состоит из составные числа для любого натурального числа [64] Однако большие промежутки между простыми числами возникают намного раньше, чем показывает этот аргумент. [65] Например, первый пробел длины 8 находится между простыми числами 89 и 97, [66] намного меньше, чемПредполагается, что существует бесконечно много простых чисел-близнецов , пар простых чисел с разностью 2; это гипотеза простого близнеца . Гипотеза Полиньяка в более общем плане утверждает, что для каждого положительного целого числа существует бесконечно много пар последовательных простых чисел, различающихся на [67] Гипотеза Андрицы , [67] Гипотеза Брокара , [68] Гипотеза Лежандра , [69] и Гипперман [68] предполагают, что наибольшие промежутки между простыми числами из к должно быть самое большее приблизительно результат, который, как известно, следует из гипотезы Римана, в то время как гораздо более сильная гипотеза Крамера устанавливает наибольший размер щели на[67] Промежутки между простыми числами можно обобщить на простые k {\ displaystyle k} -кортежи , образцы различий между более чем двумя простыми числами. Их бесконечность и плотность являются предметом первой гипотезы Харди – Литтлвуда , которая может быть мотивирована эвристикой , согласно которой простые числа ведут себя аналогично случайной последовательности чисел с плотностью, заданной теоремой о простых числах. [70]
Аналитические свойства
Аналитическая теория чисел изучает теорию чисел через призму непрерывных функций , пределов , бесконечных рядов и связанную с ними математику бесконечного и бесконечно малого .
Эта область исследований началась с Леонарда Эйлера и его первого крупного результата - решения Базельской проблемы . Задача требовала значения бесконечной суммы что сегодня можно признать ценностью о дзета - функция Римана . Эта функция тесно связана с простыми числами и одной из наиболее важных нерешенных проблем математики - гипотезой Римана . Эйлер показал, что. [71] Величина, обратная этому числу,, является предельной вероятностью того, что два случайных числа, выбранных одинаково из большого диапазона, являются относительно простыми (не имеют общих множителей). [72]
Распределение простых чисел в большом, например, вопрос, сколько простых чисел меньше заданного большого порога, описывается теоремой о простых числах , но нет эффективной формулы для п {\ displaystyle n} -е простое число известно. Теорема Дирихле об арифметических прогрессиях в своей основной форме утверждает, что линейные многочлены
с относительно простыми целыми числами а также принимать бесконечно много простых значений. Более сильные формы теоремы утверждают, что сумма обратных величин этих простых значений расходится, и что разные линейные многочлены с одинаковымиимеют примерно одинаковые пропорции простых чисел. Хотя были сформулированы предположения о пропорциях простых чисел в многочленах более высокой степени, они остались недоказанными, и неизвестно, существует ли квадратичный многочлен, который (для целочисленных аргументов) является простым бесконечно часто.
Аналитическое доказательство теоремы Евклида
Доказательство Эйлера, что существует бесконечно много простых чисел, рассматривает суммы обратных простых чисел,
Эйлер показал, что для любого произвольного действительного числа , существует простое число для которых эта сумма больше, чем . [73] Это показывает, что существует бесконечно много простых чисел, потому что, если бы было конечное число простых чисел, сумма достигла бы своего максимального значения при наибольшем простом числе, а не вырастала бы через каждые. Скорость роста этой суммы более точно описывается второй теоремой Мертенса . [74] Для сравнения, сумма
не растет до бесконечности, как уходит в бесконечность (см. Базельскую задачу ). В этом смысле простые числа встречаются чаще, чем квадраты натуральных чисел, хотя оба набора бесконечны. [75] Теорема Бруна утверждает, что сумма обратных двойных простых чисел ,
конечно. Из-за теоремы Бруна невозможно использовать метод Эйлера для решения гипотезы о простых числах-близнецах о том , что существует бесконечно много простых чисел-близнецов. [75]
Количество простых чисел ниже заданной границы
Функция подсчета простых чисел определяется как количество простых чисел, не превышающих . [76] Например,, поскольку имеется пять простых чисел, меньших или равных 11. Такие методы, как алгоритм Мейселя – Лемера, могут вычислять точные значения быстрее, чем можно было бы перечислить каждое простое число до . [77] Теорема о простых числах утверждает, что асимптотичен , который обозначается как
и означает, что соотношение в правую дробь стремится к 1 прирастет до бесконечности. [78] Это означает, что вероятность того, что случайно выбранное число меньше, чем простое число (приблизительно) обратно пропорционально количеству цифр в . [79] Это также означает, чтоое простое число пропорционально [80] и, следовательно, средний размер промежутка между простыми числами пропорционален. [65] Более точная оценкадается логарифмическим интегралом смещения [78]
Арифметические прогрессии
Арифметическая прогрессия является конечной или бесконечной последовательностью чисел таким образом, что последовательные числа в последовательности все имеют одинаковые значения. [81] Эта разница называется модулем прогрессии. [82] Например,
- 3, 12, 21, 30, 39, ...,
представляет собой бесконечную арифметическую прогрессию с модулем 9. В арифметической прогрессии все числа имеют одинаковый остаток при делении на модуль; в этом примере остаток равен 3. Поскольку и модуль 9, и остаток 3 кратны 3, то же самое и с каждым элементом в последовательности. Следовательно, эта прогрессия содержит только одно простое число, само 3. В общем, бесконечная прогрессия
может иметь более одного простого числа только тогда, когда его остаток и модуль относительно просты. Если они взаимно просты, теорема Дирихле об арифметических прогрессиях утверждает, что прогрессия содержит бесконечно много простых чисел. [83]
Теорема Грина – Тао показывает, что существуют сколь угодно длинные конечные арифметические прогрессии, состоящие только из простых чисел. [35] [84]
Простые значения квадратичных многочленов
Эйлер заметил, что функция
дает простые числа для , хотя составные числа появляются среди его более поздних значений. [85] [86] Поиски объяснения этого явления привело к глубокой теории алгебраических чисел из чисел Хегнера и проблема номера класса . [87] Гипотеза Харди-Литтлвуда F предсказывает плотность простых чисел среди значений квадратичных многочленов с целыми коэффициентами в терминах логарифмического интеграла и полиномиальных коэффициентов. Доказано, что ни один квадратичный многочлен не принимает бесконечно много простых значений. [88]
Улама спираль упорядочивает натуральных чисел в двумерной сетке, спиралевидные в виде концентрических квадратов , окружающих начало координат с простыми числами подсвечивается. Визуально кажется, что простые числа группируются на определенных диагоналях, а не на других, что говорит о том, что некоторые квадратичные многочлены принимают простые значения чаще, чем другие. [88]
Дзета-функция и гипотеза Римана
Один из самых известных нерешенных вопросов в области математики, начиная с 1859 года , и одна из задач премии тысячелетия , является гипотеза Римана , которая спрашивает , где нули о дзета - функции Римана расположены. Эта функция является аналитической функцией на комплексных числах . Для комплексных чиселс действительной частью больше единицы он равен как бесконечной сумме по всем целым числам, так и бесконечному произведению по простым числам,
Это равенство между суммой и произведением, обнаруженное Эйлером, называется эйлеровым произведением . [89] Произведение Эйлера может быть получено из фундаментальной теоремы арифметики и показывает тесную связь между дзета-функцией и простыми числами. [90] Это приводит к другому доказательству того, что существует бесконечно много простых чисел: если бы их было только конечное, то равенство сумм-произведений также было бы справедливо при, но сумма расходится (это гармонический ряд ), а произведение было бы конечным; противоречие. [91]
Гипотеза Римана утверждает, что все нули дзета-функции являются либо отрицательными четными числами, либо комплексными числами с действительной частью, равной 1/2. [92] Первоначальное доказательство теоремы о простых числах было основано на слабой форме этой гипотезы, что не существует нулей с вещественной частью, равной 1, [93] [94], хотя были найдены и другие, более элементарные доказательства. [95] Функция подсчета простых чисел может быть выражена явной формулой Римана как сумма, в которой каждый член происходит от одного из нулей дзета-функции; главный член этой суммы - логарифмический интеграл, а остальные члены заставляют сумму колебаться выше и ниже основного члена. [96] В этом смысле нули определяют, насколько регулярно распределяются простые числа. Если гипотеза Римана верна, эти флуктуации будут небольшими, и асимптотическое распределение простых чисел, заданное теоремой о простых числах, также будет сохраняться на гораздо более коротких интервалах (длиной около квадратного корня из для интервалов около числа ). [94]
Абстрактная алгебра
Модульная арифметика и конечные поля
Модульная арифметика изменяет обычную арифметику, используя только числа , для натурального числа называется модулем. Любое другое натуральное число можно отобразить в этой системе, заменив его остатком после деления на. [97] Модульные суммы, разности и произведения вычисляются путем такой же замены остатком результата обычной суммы, разницы или произведения целых чисел. [98] Равенство целых чисел соответствует сравнению в модульной арифметике: а также конгруэнтны (написано мод ), когда они имеют одинаковый остаток после деления на . [99] Однако в этой системе чисел деление на все ненулевые числа возможно тогда и только тогда, когда модуль простой. Например, с простым числом как модуль, деление на возможно: , потому что очистка знаменателя путем умножения обеих частей на дает правильную формулу . Однако с составным модулем упругости, деление на невозможно. Нет действительного решения для: очистка знаменателей умножением на заставляет левую сторону становиться в то время как правая часть становится либо или же . В терминологии абстрактной алгебры способность выполнять деление означает, что модульная арифметика по модулю простого числа образует поле или, более конкретно, конечное поле , в то время как другие модули дают только кольцо, но не поле. [100]
Некоторые теоремы о простых числах можно сформулировать с помощью модульной арифметики. Например, маленькая теорема Ферма утверждает, что если (мод ), тогда (мод ). [101] Подводя итог всему выбору дает уравнение
действительно всякий раз, когда простое. Гипотеза Джуги гласит, что это уравнение также является достаточным условием длябыть первоклассным. [102] Теорема Вильсона гласит, что целое числопрост тогда и только тогда, когда факториал соответствует мод . Для составного числаэто не может иметь место, так как один из его факторов делит как n, так и, и другие невозможно. [103]
p -адические числа
В п {\ displaystyle p} -адический порядок целого числа количество копий в разложении на простые множители . Эту же концепцию можно распространить с целых на рациональные числа, определив-адический порядок дроби быть . В-адическое абсолютное значение любого рационального числа тогда определяется как . Умножение целого числа на его-адическая абсолютная величина исключает факторы в его факторизации, оставив только другие простые числа. Точно так же, как расстояние между двумя действительными числами можно измерить абсолютной величиной их расстояния, расстояние между двумя рациональными числами можно измерить их величиной.-адическое расстояние, -адическая абсолютная величина их разницы. Для этого определения расстояния два числа находятся близко друг к другу (они имеют небольшое расстояние), когда их разница делится на большую степень. Точно так же, как действительные числа могут быть образованы из рациональных чисел и их расстояний, путем добавления дополнительных предельных значений для формирования полного поля рациональные числа с-адическое расстояние может быть расширено до другого полного поля, п {\ displaystyle p} -адические числа . [104] [105]
Эта картина порядка, абсолютного значения и полного поля, полученного из них, может быть обобщена на поля алгебраических чисел и их оценки (определенные отображения из мультипликативной группы поля в полностью упорядоченную аддитивную группу , также называемую порядками), абсолютные значения ( определенные мультипликативные отображения из поля в действительные числа, также называемые нормами), [104] и местами (расширения до полных полей, в которых данное поле является плотным множеством , также называемые пополнениями). [106] Расширение от рациональных чисел к действительным числам , например, - это место, в котором расстояние между числами является обычным абсолютным значением их разности. Соответствующее отображение в аддитивную группу было бы логарифмом абсолютного значения, хотя это не отвечает всем требованиям оценки. Согласно теореме Островского , с точностью до естественного понятия эквивалентности, действительные числа и-адические числа с их порядками и абсолютными значениями являются единственными оценками, абсолютными значениями и местами в рациональных числах. [104] локально глобальный принцип позволяет определенные проблемы над рациональными числами, решаемые склеиванием решений от каждого из своих мест, вновь подчеркивая важность простых чисел в теории чисел. [107]
Первичные элементы в кольцах
Коммутативное кольцо представляет собой алгебраическую структуру , где сложение, вычитание и умножение определены. Целые числа представляют собой кольцо, а простые числа в целых числах были обобщены на кольца двумя различными способами: простые элементы и неприводимые элементы . Элемент кольца называется простым, если он не равен нулю, не имеет обратного мультипликативного числа (то есть не является единицей ) и удовлетворяет следующему требованию: всякий раз, когда делит продукт двух элементов , он также делит хотя бы одно из или же . Элемент является неприводимым, если он не является ни единицей, ни продуктом двух других неединичных элементов. В кольце целых чисел простой и неприводимый элементы образуют одно и то же множество,
В произвольном кольце все простые элементы неприводимы. Обратное неверно в общем случае, но верно для уникальных областей факторизации . [108]
Основная теорема арифметики продолжает выполняться (по определению) в областях единственной факторизации. Примером такой области являются гауссовские целые числа , кольцо комплексных чисел вида где обозначает мнимую единицу, а а также - произвольные целые числа. Его простые элементы известны как простые числа Гаусса . Не каждое число, которое является простым среди целых, остается простым в гауссовых целых числах; например, число 2 может быть записано как произведение двух гауссовских простых чисел а также . Рациональные простые числа (простые элементы в целых числах), конгруэнтные 3 по модулю 4, являются гауссовскими простыми числами, но рациональные простые числа, конгруэнтные 1 по модулю 4, - нет. [109] Это следствие теоремы Ферма о суммах двух квадратов , которая утверждает, что нечетное простое число выражается как сумма двух квадратов, , и поэтому факторизуемый как , когда именно равен 1 по модулю 4. [110]
Основные идеалы
Не каждое кольцо является уникальной областью факторизации. Например, в круге цифр (для целых чисел а также ) номер имеет две факторизации , где ни один из четырех факторов не может быть уменьшен дальше, поэтому он не имеет уникальной факторизации. Чтобы расширить уникальную факторизацию на более широкий класс колец, понятие числа можно заменить понятием идеала , подмножества элементов кольца, которое содержит все суммы пар его элементов, и все произведения его элементы с кольцевыми элементами. Простые идеалы , которые обобщают простые элементы в том смысле, что главный идеал, порожденный простым элементом, является простым идеалом, являются важным инструментом и объектом изучения в коммутативной алгебре , алгебраической теории чисел и алгебраической геометрии . Первичные идеалы кольца целых чисел - это идеалы (0), (2), (3), (5), (7), (11), ... Основная теорема арифметики обобщается на теорему Ласкера – Нётер. , который выражает каждый идеал в нетеровом коммутативном кольце как пересечение первичных идеалов , которые являются подходящими обобщениями простых степеней . [111]
Спектр кольца является геометрическим пространством, точки которого являются простыми идеалами кольца. [112] Арифметическая геометрия также выигрывает от этого понятия, и многие концепции существуют как в геометрии, так и в теории чисел. Например, факторизация или разветвление простых идеалов при поднятии их в поле расширения , основная проблема алгебраической теории чисел, имеет некоторое сходство с ветвлением в геометрии . Эти концепции могут помочь даже в вопросах теории чисел, связанных исключительно с целыми числами. Так , например, простые идеалы в кольце целых чисел от квадратичных числовых полей могут быть использованы для доказательства квадратичной взаимности , утверждения , что касается существования квадратных корней по модулю целого числа простых чисел. [113] Ранние попытки доказать Великую теорему Ферма привели к введению Куммером регулярных простых чисел , целых простых чисел, связанных с неудачей уникальной факторизации в круговых целых числах . [114] Вопрос о том, сколько целых простых чисел входит в произведение нескольких простых идеалов в поле алгебраических чисел, решается теоремой Чеботарева о плотности , которая (в применении к круговым целым числам) имеет теорему Дирихле о простых числах в арифметических прогрессиях как особый случай. [115]
Теория групп
В теории конечных групп из теорем Силова следует, что если степень простого числаделит порядок группы , то в группе есть подгруппа порядка. По теореме Лагранжа любая группа простого порядка является циклической группой , а по теореме Бернсайда любая группа, порядок которой делится только на два простых числа, разрешима . [116]
Вычислительные методы
Долгое время теория чисел в целом и изучение простых чисел в частности рассматривались как канонический пример чистой математики без каких-либо приложений за пределами математики [b], кроме использования зубьев шестерен с простыми номерами для распределения износа. равномерно. [117] В частности, теоретики чисел, такие как британский математик Дж. Х. Харди, гордились своей работой, не имевшей абсолютно никакого военного значения. [118]
Это видение чистоты теории чисел было разрушено в 1970-х годах, когда было публично объявлено, что простые числа могут использоваться в качестве основы для создания алгоритмов криптографии с открытым ключом . [32] Эти приложения привели к значительному изучению алгоритмов вычислений с простыми числами, и, в частности, проверки простоты , методов определения того, является ли данное число простым. Самая простая процедура проверки простоты, пробное деление, слишком медленная, чтобы быть полезной для больших чисел. Одна группа современных тестов простоты применима к произвольным числам, тогда как более эффективные тесты доступны для чисел особых типов. Большинство тестов на простоту говорят только о том, является ли их аргумент простым или нет. Подпрограммы, которые также предоставляют простой множитель составных аргументов (или все его простые множители), называются алгоритмами факторизации . Простые числа также используются в вычислениях для контрольных сумм , хэш-таблиц и генераторов псевдослучайных чисел .
Судебное отделение
Самый простой метод проверки простоты заданного целого числа называется пробным делением . Этот метод делитна каждое целое число от 2 до квадратного корня из. Любое такое целочисленное деление равномерно устанавливает как композит; в противном случае он прост. Целые числа больше квадратного корня не нужно проверять, потому что всякий раз, когда, один из двух факторов а также меньше или равен квадратному корню из. Другая оптимизация заключается в проверке только простых чисел в качестве факторов в этом диапазоне. [119] Например, чтобы проверить, является ли число 37 простым, этот метод делит его на простые числа в диапазоне от 2 до, которые равны 2, 3 и 5. Каждое деление дает ненулевой остаток, поэтому 37 действительно простое число.
Хотя этот метод просто описать, он непрактичен для проверки простоты больших целых чисел, поскольку количество выполняемых им тестов растет экспоненциально в зависимости от количества цифр этих целых чисел. [120] Тем не менее, пробное деление все еще используется с меньшим пределом, чем квадратный корень из размера делителя, чтобы быстро обнаружить составные числа с небольшими множителями, прежде чем использовать более сложные методы для чисел, которые проходят этот фильтр. [121]
Сита
До компьютеров обычно печатались математические таблицы, в которых перечислялись все простые числа или простые множители до заданного предела. [122] Самый старый метод создания списка простых чисел называется решето Эратосфена. [123] На анимации показан оптимизированный вариант этого метода. [124] Другой более асимптотически эффективный метод просеивания для той же проблемы - сито Аткина . [125] В продвинутой математике теория решет применяет аналогичные методы к другим задачам. [126]
Тестирование на первичность в сравнении с доказательством первичности
Некоторые из самых быстрых современных тестов для определения того, является ли произвольное заданное число is prime - вероятностные алгоритмы (или алгоритмы Монте-Карло ), что означает, что у них есть небольшой случайный шанс дать неправильный ответ. [127] Например, критерий простоты Соловея – Штрассена для заданного числа. выбирает номер случайно из через и использует модульное возведение в степень, чтобы проверить, делится на . [c] Если да, он отвечает «да», в противном случае - «нет». Если действительно простое, он всегда ответит "да", но если является составным, то он отвечает да с вероятностью не более 1/2 и нет с вероятностью не менее 1/2. [128] Если этот тест повторяется раз на одном и том же числе, вероятность того, что составное число сможет каждый раз пройти тест, не превышает . Поскольку это число уменьшается экспоненциально с количеством тестов, это обеспечивает высокую уверенность (хотя и не уверенность) в том, что число, прошедшее повторный тест, является простым. С другой стороны, если тест не удался, то число определенно составное. [129] Составное число, которое проходит такую проверку, называется псевдопростом . [128]
Напротив, некоторые другие алгоритмы гарантируют, что их ответ всегда будет правильным: простые числа всегда будут определяться как простые, а составные числа всегда будут определяться как составные. Например, это касается пробного деления. Алгоритмы с гарантированной-правильного вывода включают в себя как детерминированных (неслучайных) алгоритмы, такие как тест AKS на простоту , [130] и рандомизированы в Лас - Вегас , алгоритмы , где случайные выборы , сделанные с помощью алгоритма не влияют на его окончательный ответ, например, некоторые вариации доказательства простоты эллиптической кривой . [127] Когда метод эллиптической кривой приходит к выводу, что число является простым, он предоставляет сертификат простоты, который можно быстро проверить. [131] Тест на простоту эллиптической кривой является самым быстрым на практике из всех тестов на простоту, но его анализ во время выполнения основан на эвристических аргументах, а не на строгих доказательствах. Тест на простоту AKS математически доказал временную сложность, но медленнее, чем проверка простоты эллиптической кривой на практике. [132] Эти методы могут использоваться для генерации больших случайных простых чисел путем генерации и тестирования случайных чисел до тех пор, пока не будет найдено одно простое; при этом более быстрый вероятностный тест может быстро исключить большинство составных чисел до того, как будет использован гарантированно правильный алгоритм для проверки того, что остальные числа являются простыми. [d]
В следующей таблице перечислены некоторые из этих тестов. Их время работы указано в, число для тестирования и, для вероятностных алгоритмов, число проведенных тестов. Более того,- произвольно малое положительное число, а log - логарифм с неопределенным основанием. В большом выводе обозначение означает , что каждый раз , когда неизбежно должны быть умножено на фактор постоянная , чтобы преобразовать его из безразмерных единиц в единицах времени; этот фактор зависит от деталей реализации, таких как тип компьютера, на котором выполняется алгоритм, но не от входных параметров. а также .
Контрольная работа | Разработано в | Тип | Продолжительность | Заметки | Рекомендации |
---|---|---|---|---|---|
Тест на простоту AKS | 2002 г. | детерминированный | [130] [133] | ||
Доказательство простоты эллиптической кривой | 1986 г. | Лас Вегас | эвристически | [132] | |
Тест на простоту Baillie-PSW | 1980 г. | Монте-Карло | [134] [135] | ||
Тест на простоту Миллера – Рабина | 1980 г. | Монте-Карло | вероятность ошибки | [136] | |
Тест на простоту Соловея – Штрассена. | 1977 г. | Монте-Карло | вероятность ошибки | [136] |
Специальные алгоритмы и наибольшее известное простое число
В дополнение к вышеупомянутым тестам, применимым к любому натуральному числу, некоторые числа особой формы можно быстрее проверить на простоту. Например, тест на простоту Лукаса-Лемера может детерминированно определить, является ли число Мерсенна (на единицу меньше степени двойки ) простым, за то же время, что и одна итерация теста Миллера-Рабина. [137] Поэтому с 1992 г. (по состоянию на декабрь 2018 г.[Обновить]) самым большим известным простым числом всегда было простое число Мерсенна. [138] Предполагается, что существует бесконечно много простых чисел Мерсенна. [139]
В следующей таблице приведены самые большие известные простые числа различных типов. Некоторые из этих простых чисел были найдены с помощью распределенных вычислений . В 2009 году проект Great Internet Mersenne Prime Search был удостоен приза в размере 100 000 долларов США за первое открытие простого числа, содержащего не менее 10 миллионов цифр. [140] Организация Electronic Frontier Foundation также предлагает $ 150 000 и $ 250 000 для простых чисел, по крайней мере , 100 миллионов цифр и 1 млрд цифр, соответственно. [141]
Тип | основной | Количество десятичных цифр | Дата | Найдено |
---|---|---|---|---|
Мерсенн прайм | 2 82 589 933 - 1 | 24 862 048 | 7 декабря 2018 г. [1] | Патрик Ларош, Great Internet Mersenne Prime Search |
Proth Prime | 10,223 × 2 31,172,165 + 1 | 9 383 761 | 31 октября 2016 г. [142] | Петер Сабольч, PrimeGrid [143] |
факториальное простое число | 208 003! - 1 | 1 015 843 | Июль 2016 г. | Соу-Фукуи [144] |
изначальное простое число [e] | 1 098 133 # - 1 | 476 311 | Март 2012 г. | Джеймс П. Берт, PrimeGrid [146] |
простые числа-близнецы | 2,996,863,034,895 × 2 1,290,000 ± 1 | 388 342 | Сентябрь 2016 г. | Том Грир, PrimeGrid [147] |
Целочисленная факторизация
Учитывая составное целое число , Задача обеспечения одного (или все) простые множители называют факторизацией из. Это значительно сложнее, чем проверка на простоту [148], и, хотя известно множество алгоритмов факторизации, они медленнее, чем самые быстрые методы проверки на простоту. Пробное деление и алгоритм ро Полларда можно использовать для поиска очень малых факторов, [121] и факторизация эллиптической кривой может быть эффективной, когдаимеет факторы умеренного размера. [149] Методы, подходящие для произвольных больших чисел, которые не зависят от размера его факторов, включают квадратное решето и решето общего числового поля . Как и в случае с проверкой простоты, существуют также алгоритмы факторизации, требующие, чтобы их ввод имел особую форму, включая решето специального числового поля . [150] По состоянию на декабрь 2019 г.[Обновить]Самое большое число, которое, как известно, было вычислено с помощью универсального алгоритма, - это RSA-240 , который имеет 240 десятичных цифр (795 бит) и является произведением двух больших простых чисел. [151]
Алгоритм Шора может разложить любое целое число на полиномиальное количество шагов на квантовом компьютере . [152] Однако современные технологии позволяют запускать этот алгоритм только для очень небольшого числа людей. По состоянию на октябрь 2012 г.[Обновить]наибольшее число, которое было разложено на квантовый компьютер, на котором запущен алгоритм Шора, равно 21. [153]
Другие вычислительные приложения
Некоторые алгоритмы шифрования с открытым ключом , такие как RSA и обмен ключами Диффи – Хеллмана , основаны на больших простых числах ( обычно 2048- битные простые числа). [154] RSA полагается на предположение, что намного проще (то есть более эффективно) выполнять умножение двух (больших) чисел. а также чем рассчитывать а также (предполагается взаимно простой ), если только продуктизвестен. [32] Обмен ключами Диффи-Хеллмана основан на том факте, что существуют эффективные алгоритмы модульного возведения в степень (вычисление), в то время как обратная операция ( дискретный логарифм ) считается сложной проблемой. [155]
Простые числа часто используются для хеш-таблиц . Например, оригинальный метод Картера и Вегмана для универсального хеширования был основан на вычислении хеш-функций путем выбора случайных линейных функций по модулю больших простых чисел. Картер и Вегман обобщили этот метод на k {\ displaystyle k} -независимое хеширование с использованием многочленов более высокой степени, опять же по модулю больших простых чисел. [156] Так же, как в хеш-функции, простые числа используются для размера хеш-таблицы в хеш-таблицах на основе квадратичного зондирования, чтобы гарантировать, что тестовая последовательность охватывает всю таблицу. [157]
Некоторые методы контрольной суммы основаны на математике простых чисел. Например, контрольные суммы, используемые в Международных стандартных книжных номерах , определяются путем взятия оставшейся части числа по модулю 11, простого числа. Поскольку число 11 является простым, этот метод может обнаруживать как однозначные ошибки, так и перестановки соседних цифр. [158] Другой метод контрольной суммы, Adler-32 , использует арифметику по модулю 65521, наибольшее простое число меньше. [159] Простые числа также используются в генераторах псевдослучайных чисел, включая линейные конгруэнтные генераторы [160] и Twister Мерсенна . [161]
Другие приложения
Простые числа имеют центральное значение для теории чисел, но также имеют много приложений в других областях математики, включая абстрактную алгебру и элементарную геометрию. Например, можно разместить простые числа точек в двумерной сетке так, чтобы не было трех на линии , или так, чтобы каждый треугольник, образованный тремя точками, имел большую площадь . [162] Другим примером является критерий Эйзенштейна , проверка того, является ли многочлен неприводимым, на основе делимости его коэффициентов на простое число и его квадрат. [163]
Понятие простого числа настолько важно, что оно по-разному обобщалось в различных областях математики. Как правило, «штрих» указывает на минимальность или неразложимость в соответствующем смысле. Например, простое поле данного поля - это его наименьшее подполе, которое содержит как 0, так и 1. Это либо поле рациональных чисел, либо конечное поле с простым числом элементов, отсюда и название. [164] Часто второе, дополнительное значение подразумевается с помощью слова «простое число», а именно, что любой объект может быть, по существу, однозначно разложен на его основные компоненты. Например, в теории узлов , простой узел является узлом , который неразложимый в том смысле , что она не может быть записана как связная сумма два нетривиальных узлов. Любой узел можно однозначно выразить как связную сумму простых узлов. [165] простое разложение 3-многообразий является еще одним примером этого типа. [166]
Помимо математики и вычислений, простые числа потенциально связаны с квантовой механикой и метафорически используются в искусстве и литературе. Они также использовались в эволюционной биологии для объяснения жизненных циклов цикад .
Конструируемые многоугольники и многоугольные разбиения
Простые числа Ферма - это простые числа вида
с участием неотрицательное целое число . [167] Они названы в честь Пьера де Ферма , который предположил, что все такие числа простые. Первые пять из этих чисел - 3, 5, 17, 257 и 65 537 - простые, [168] ноКомпозиционно и так все остальные числа Ферма , которые были проверены по состоянию на 2017. [169] А регулярной п {\ displaystyle n} -gon можно построить с помощью линейки и циркуля тогда и только тогда, когда нечетные простые множители(если есть) - различные простые числа Ферма. [168] Аналогичным образом, обычный-угольник может быть построен с использованием линейки, циркуля и трисектора угла тогда и только тогда, когда простые множители п {\ displaystyle n} являются любым количеством копий 2 или 3 вместе с (возможно, пустым) набором различных простых чисел Пирпонта, простых чисел формы. [170]
Любой выпуклый многоугольник можно разбить на меньшие выпуклые многоугольники равной площади и равного периметра, когда является степенью простого числа , но это неизвестно для других значений. [171]
Квантовая механика
Начиная с работ Хью Монтгомери и Фримена Дайсона в 1970-х годах, математики и физики предположили, что нули дзета-функции Римана связаны с энергетическими уровнями квантовых систем . [172] [173] Простые числа также важны в квантовой информатике благодаря таким математическим структурам, как взаимно несмещенные базисы и симметричные информационно полные положительные операторнозначные меры . [174] [175]
Биология
В эволюционной стратегии цикад из рода Magicicada используются простые числа. [176] Эти насекомые проводят большую часть своей жизни как личинки под землей. Они окукливаются и выходят из нор только через 7, 13 или 17 лет, после чего летают, размножаются и умирают самое большее через несколько недель. Биологи предполагают, что эти продолжительности цикла размножения с простыми числами эволюционировали, чтобы не дать хищникам синхронизироваться с этими циклами. [177] [178] Напротив, многолетние периоды между цветением у бамбуковых растений, как предполагается, являются плавными числами , имея только небольшие простые числа в их факторизации. [179]
Искусство и литература
Простые числа повлияли на многих художников и писателей. Французский композитор Оливье Мессиан использовал простые числа для создания аметрической музыки через «природные явления». В таких работах, как La Nativité du Seigneur (1935) и Quatre études de rythme (1949–50), он одновременно использует мотивы с длиной, заданной разными простыми числами, для создания непредсказуемых ритмов: простые числа 41, 43, 47 и 53 появляются в третий этюд "Neumes rythmiques". По словам Мессиана, этот способ сочинения был «вдохновлен движениями природы, движениями свободной и неравной продолжительности». [180]
В своем научно-фантастическом романе « Контакт» ученый Карл Саган предположил, что разложение на простые множители можно использовать как средство установления плоскостей двумерных изображений при общении с инопланетянами, идея, которую он впервые неофициально развил с американским астрономом Фрэнком Дрейком в 1975 году [181 ] В романе Марка Хэддона «Забавный инцидент с собакой в ночное время » рассказчик выстраивает части рассказа последовательными простыми числами, чтобы передать психическое состояние его главного героя, математически одаренного подростка с синдромом Аспергера. синдром . [182] Простые числа используются как метафора одиночества и изоляции в романе Паоло Джордано «Одиночество простых чисел» , в котором они изображены как «чужаки» среди целых чисел. [183]
Заметки
- ^ 44-значное простое число, найденное в 1951 году Эме Феррье с помощью механического калькулятора, остается самым большим простым числом, которое не было найдено с помощью электронных компьютеров. [28]
- ^ a b Например, Бейлер пишет, что теоретик чисел Эрнст Куммер любил свои идеальные числа , тесно связанные с простыми числами, «потому что они не запятнали себя никакими практическими применениями» [30], а Кац пишет, что Эдмунд Ландау , известный своим Работая над распределением простых чисел, «ненавидел практические приложения математики» и по этой причине избегал таких предметов, как геометрия , которые уже показали себя полезными. [31]
- ^ В этом тесте срок отрицательный, если квадрат по модулю заданного (предполагаемого) простого числа , и положительный в противном случае. В более общем плане для непростых ценностей, то терм является (отрицательным) символом Якоби , который может быть вычислен с использованием квадратичной взаимности .
- ^ Действительно, большая часть анализа доказательства простоты эллиптической кривой основана на предположении, что входные данные алгоритма уже прошли вероятностную проверку. [131]
- ^ Primorial функция, обозначаемый , дает произведение простых чисел с точностью до , а простое число - простое число одной из форм. [145]
Рекомендации
- ^ a b «Проект GIMPS обнаруживает наибольшее известное простое число: 2 82 589 933 -1» . Мерсенна Research, Inc . 21 декабря 2018 . Проверено 21 декабря 2018 .
- ^ Гардинер, Энтони (1997). Справочник по математической олимпиаде: введение в решение задач на основе первых 32 британских математических олимпиад 1965–1996 гг . Издательство Оксфордского университета. п. 26 . ISBN 978-0-19-850105-3.
- ^ Хендерсон, Энн (2014). Дислексия, дискалькулия и математика: Практическое руководство (2-е изд.). Рутледж. п. 62. ISBN 978-1-136-63662-2.
- ^ Адлер, Ирвинг (1960). Гигантская золотая книга математики: исследование мира чисел и пространства . Золотая пресса. п. 16 . OCLC 6975809 .
- ^ Лефф, Лоуренс С. (2000). Математика Учебное пособие для SAT I . Образовательная серия Бэррона. п. 360 . ISBN 978-0-7641-0768-9.
- ^ Дадли, Андервуд (1978). «Раздел 2: Уникальная факторизация» . Элементарная теория чисел (2-е изд.). WH Freeman and Co. стр. 10 . ISBN 978-0-7167-0076-0.
- ^ Серпинский, Вацлав (1988). Элементарная теория чисел . Математическая библиотека Северной Голландии. 31 (2-е изд.). Эльзевир. п. 113. ISBN 978-0-08-096019-7.
- ^ а б Циглер, Гюнтер М. (2004). «Рекордные гонки на большое простое число». Уведомления Американского математического общества . 51 (4): 414–416. Руководство по ремонту 2039814 .
- ^ Стиллвелл, Джон (1997). Числа и геометрия . Тексты для бакалавриата по математике. Springer. п. 9. ISBN 978-0-387-98289-2.
- ^ Серпинский, Вацлав (1964). Подборка задач теории чисел . Нью-Йорк: Макмиллан. п. 40 . Руководство по ремонту 0170843 .
- ^ Натансон, Мелвин Б. (2000). «Обозначения и условные обозначения» . Элементарные методы теории чисел . Тексты для выпускников по математике. 195 . Springer. ISBN 978-0-387-22738-2. Руководство по ремонту 1732941 .
- ^ Фатикони, Теодор Г. (2012). Математика бесконечности: руководство к великим идеям . Чистая и прикладная математика: серия текстов, монографий и трактатов Wiley. 111 (2-е изд.). Джон Вили и сыновья. п. 44. ISBN 978-1-118-24382-4.
- ^ Брюинз, Эверт Мари, обзор в Mathematical Reviews of Gillings, RJ (1974). «Лицевая сторона Математического папируса Райнда. Как древнеегипетский писец подготовил его?». Архив истории точных наук . 12 (4): 291–298. DOI : 10.1007 / BF01307175 . Руководство по ремонту 0497458 . S2CID 121046003 .
- ^ а б Стиллвелл, Джон (2010). Математика и ее история . Тексты для бакалавриата по математике (3-е изд.). Springer. п. 40. ISBN 978-1-4419-6052-8.
- ^ а б Померанс, Карл (декабрь 1982). «Поиск простых чисел». Scientific American . 247 (6): 136–147. Bibcode : 1982SciAm.247f.136P . DOI : 10.1038 / Scientificamerican1282-136 . JSTOR 24966751 .
- ^ а б в Моллин, Ричард А. (2002). «Краткая история факторинга и тестирования на простоту BC (до компьютеров)». Математический журнал . 75 (1): 18–29. DOI : 10.2307 / 3219180 . JSTOR 3219180 . Руководство по ремонту 2107288 .
- ^ О'Коннор, Джон Дж .; Робертсон, Эдмунд Ф. «Абу Али аль-Хасан ибн аль-Хайтам» . Архив истории математики MacTutor . Сент-Эндрюсский университет ..
- ^ Сандифер 2007 , 8. Ферма малая теорема (ноябрь 2003), стр. 45
- ^ Сандифер, К. Эдвард (2014). Как Эйлер сделал даже больше . Математическая ассоциация Америки. п. 42. ISBN 978-0-88385-584-3.
- ^ Коши, Томас (2002). Элементарная теория чисел с приложениями . Академическая пресса. п. 369. ISBN. 978-0-12-421171-1.
- ^ Юань, Ван (2002). Гипотеза Гольдбаха . Серия по чистой математике. 4 (2-е изд.). World Scientific. п. 21. ISBN 978-981-4487-52-8.
- ^ Наркевич, Владислав (2000). «1.2 Сумма взаимных чисел» . Развитие теории простых чисел: от Евклида до Харди и Литтлвуда . Монографии Спрингера по математике. Springer. п. 11. ISBN 978-3-540-66289-1.
- ^ Чебычев, П. (1852). "Mémoire sur les nombres premiers" (PDF) . Journal de mathématiques pures et appliquées . Серия 1 (на французском языке): 366–390.. (Доказательство постулата: 371-382). См. Также Mémoires de l'Académie Impériale des Sciences de Saint Pétersbourg, vol. 7, стр. 15-33, 1854 г.
- ^ Апостол, Том М. (2000). «Столетняя история теоремы о простых числах» . In Bambah, RP; Dumir, VC; Hans-Gill, RJ (ред.). Теория чисел . Тенденции в математике. Базель: Биркхойзер. С. 1–14. Руководство по ремонту 1764793 .
- ^ Апостол, Том М. (1976). «7. Теорема Дирихле о простых числах в арифметических прогрессиях» . Введение в аналитическую теорию чисел . Нью-Йорк; Гейдельберг: Springer-Verlag. С. 146–156. Руководство по ремонту 0434929 .
- ^ Шабер, Жан-Люк (2012). История алгоритмов: от гальки до микрочипа . Springer. п. 261. ISBN. 978-3-642-18192-4.
- ^ Розен, Кеннет Х. (2000). «Теорема 9.20. Тест простоты Прота». Элементарная теория чисел и ее приложения (4-е изд.). Эддисон-Уэсли. п. 342. ISBN. 978-0-201-87073-2.
- ^ Купер, С. Барри; Ходжес, Эндрю (2016). Когда-то и будущее Тьюринга . Издательство Кембриджского университета. С. 37–38. ISBN 978-1-107-01083-3.
- Перейти ↑ Rosen 2000 , p. 245.
- ^ Бейлер, Альберт Х. (1999) [1966]. Развлечения в теории чисел: королева математики развлекает . Дувр. п. 2. ISBN 978-0-486-21096-4. OCLC 444171535 .
- ^ Кац, Шауль (2004). «Берлинские корни - сионистское воплощение: этос чистой математики и истоки Института математики Эйнштейна при Еврейском университете в Иерусалиме». Наука в контексте . 17 (1–2): 199–234. DOI : 10.1017 / S0269889704000092 . Руководство по ремонту 2089305 .
- ^ а б в Крафт, Джеймс С .; Вашингтон, Лоуренс К. (2014). Элементарная теория чисел . Учебники по математике. CRC Press. п. 7. ISBN 978-1-4987-0269-0.
- ^ Бауэр, Крейг П. (2013). Тайная история: история криптологии . Дискретная математика и ее приложения. CRC Press. п. 468. ISBN 978-1-4665-6186-1.
- ^ Клее, Виктор ; Вагон, Стэн (1991). Старые и новые нерешенные проблемы плоской геометрии и теории чисел . Математические изложения Дольчани. 11 . Издательство Кембриджского университета. п. 224. ISBN 978-0-88385-315-3.
- ↑ a b Neale, 2017 , с. 18, 47.
- ^ а б Колдуэлл, Крис К .; Реддик, Анджела; Сюн, Йенг; Келлер, Уилфрид (2012). «История первобытности одного: подборка источников» . Журнал целочисленных последовательностей . 15 (9): Статья 12.9.8. Руководство по ремонту 3005523 .Подборку цитат из позиций древних греков по этому вопросу и о них см., В частности, на стр. 3–4. Информацию об исламских математиках см. На стр. 6.
- ^ Таран, Леонардо (1981). Спевсипп Афинский: критическое исследование с собранием связанных текстов и комментариев . Philosophia Antiqua: Серия монографий по античной философии. 39 . Брилл. С. 35–38. ISBN 978-90-04-06505-5.
- ^ Caldwell et al. 2012 , с. 7–13. См., В частности, записи для Стевина, Бранкера, Уоллиса и Престета.
- ^ Caldwell et al. 2012 , стр. 15.
- ^ а б в Колдуэлл, Крис К .; Сюн, Йенг (2012). "Какое наименьшее простое число?" (PDF) . Журнал целочисленных последовательностей . 15 (9): Статья 12.9.7. Руководство по ремонту 3005530 .
- ^ Ризель, Ганс (1994). Простые числа и компьютерные методы факторизации (2-е изд.). Базель, Швейцария: Birkhäuser. п. 36. DOI : 10.1007 / 978-1-4612-0251-6 . ISBN 978-0-8176-3743-9. Руководство по ремонту 1292250 .
- ^ а б Конвей, Джон Хортон ; Гай, Ричард К. (1996). Книга чисел . Нью-Йорк: Коперник. С. 129–130 . DOI : 10.1007 / 978-1-4612-4072-3 . ISBN 978-0-387-97993-9. Руководство по ремонту 1411676 .
- ^ Относительно totient см. Sierpiński 1988 , p. 245 . О сумме делителей см. Сандифер, К. Эдвард (2007). Как это сделал Эйлер . MAA Spectrum. Математическая ассоциация Америки. п. 59. ISBN 978-0-88385-563-8.
- ^ Смит, Карл Дж. (2011). Природа математики (12-е изд.). Cengage Learning. п. 188. ISBN 978-0-538-73758-6.
- ^ Дадли 1978 , раздел 2, теорема 2, с. 16 ; Нил, Вики (2017). Закрытие разрыва: поиски понимания простых чисел . Издательство Оксфордского университета. п. 107 . ISBN 978-0-19-109243-5.
- ^ дю Сотуа, Маркус (2003). Музыка простых чисел: поиски разгадки величайшей тайны математики . Харпер Коллинз. п. 23 . ISBN 978-0-06-093558-0.
- ↑ Дадли 1978 , раздел 2, лемма 5, с. 15 ; Хиггинс, Питер М. (1998). Математика для любознательных . Издательство Оксфордского университета. С. 77–78. ISBN 978-0-19-150050-3.
- ^ Ротман, Джозеф Дж. (2000). Первый курс абстрактной алгебры (2-е изд.). Прентис Холл. Задача 1.40, с. 56. ISBN 978-0-13-011584-3.
- ↑ Письмо Гольдбаха Эйлеруна латыни , июль 1730 г.
- ^ Фюрстенберг, Гарри (1955). «О бесконечности простых чисел». Американский математический ежемесячник . 62 (5): 353. DOI : 10,2307 / 2307043 . JSTOR 2307043 . Руководство по ремонту 0068566 .
- ^ Рибенбойм, Пауло (2004). Маленькая книга больших простых чисел . Берлин; Нью-Йорк: Springer-Verlag. п. 4. ISBN 978-0-387-20169-6.
- ^ Евклида элементы , Книга IX, предложение 20. Знакомства Дэвида Джойса английский перевод доказательства Евклида или Уильямсон, Джеймс (1782). Элементы Евклида, с диссертациями . Оксфорд: Clarendon Press . п. 63. OCLC 642232959 .
- ^ Варди, Илан (1991). Вычислительные развлечения в системе Mathematica . Эддисон-Уэсли. С. 82–89. ISBN 978-0-201-52989-0.
- ^ а б в Матиясевич, Юрий В. (1999). «Формулы для простых чисел» . В Табачников, Серж (ред.). Квант Селекта: Алгебра и анализ . II . Американское математическое общество . С. 13–24. ISBN 978-0-8218-1915-9.
- ^ Маккиннон, Ник (июнь 1987). «Формулы простых чисел». Математический вестник . 71 (456): 113–114. DOI : 10.2307 / 3616496 . JSTOR 3616496 .
- ^ Райт, Э.М. (1951). «Функция, представляющая простое число». Американский математический ежемесячник . 58 (9): 616–618. DOI : 10.2307 / 2306356 . JSTOR 2306356 .
- Перейти ↑ Guy 2013 , p. vii .
- ↑ Гай, 2013 , гипотеза С1 Гольдбаха, стр. 105–107 .
- ^ Оливейра э Силва, Томас; Герцог, Зигфрид; Парди, Сильвио (2014). «Эмпирическая проверка гипотезы Гольдбаха и вычисление простых пробелов с точностью до 4 ⋅ 10 18 {\ displaystyle 4 \ cdot 10 ^ {18}} " . Математика вычислений . 83 (288):. 2033-2060 DOI : 10,1090 / S0025-5718-2013-02787-1 . MR 3194140 .
- ^ Тао 2009 , 3.1 Структура и случайность в простых числах, стр. 239–247 . См. Особенно стр. 239.
- Перейти ↑ Guy 2013 , p. 159.
- ^ Рамаре, Оливье (1995). «О постоянной Шнирельмана» . Annali della Scuola Normale Superiore di Pisa . 22 (4): 645–706. Руководство по ремонту 1375315 .
- ^ Рассиас, Майкл Ф. (2017). Проблема Гольдбаха: избранные темы . Чам: Спрингер. п. vii. DOI : 10.1007 / 978-3-319-57914-6 . ISBN 978-3-319-57912-2. Руководство по ремонту 3674356 .
- ^ Koshy 2002 , теорема 2.14, стр. 109 . Ризель 1994 приводит аналогичный аргумент, используя примориал вместо факториала.
- ^ a b Ризель 1994 , " Большие промежутки между последовательными простыми числами ", стр. 78–79.
- ^ Слоан, Н. Дж. А. (ред.). «Последовательность A100964 (наименьшее простое число, которое начинается с пробела не менее 2n)» . Он -лайн энциклопедия целочисленных последовательностей . Фонд OEIS.
- ^ a b c Рибенбойм 2004 , Разрывы между простыми числами, стр. 186–192.
- ^ а б Рибенбойм 2004 , стр. 183.
- ^ Чан, Джоэл (февраль 1996). "ПРАЙМ-тайм!". Математические горизонты . 3 (3): 23–25. DOI : 10.1080 / 10724117.1996.11974965 . JSTOR 25678057 . Обратите внимание, что Чан называет гипотезу Лежандра «Постулатом Серпинского».
- ^ Рибенбойм 2004 , Prime-гипотеза о двойниках, стр. 201–202.
- ^ Сандифер 2007 , Глава 35, Оценка проблемы Базель, стр. 205-208 .
- ^ Огилви, CS ; Андерсон, Дж. Т. (1988). Экскурсии по теории чисел . Dover Publications Inc., стр. 29–35. ISBN 978-0-486-25778-5.
- ^ Апостол 1976 , раздел 1.6, теорема 1.13
- ^ Апостол 1976 , раздел 4.8, теорема 4.12
- ^ а б Миллер, Стивен Дж .; Таклоо-Бигхаш, Рамин (2006). Приглашение к современной теории чисел . Издательство Принстонского университета. С. 43–44. ISBN 978-0-691-12060-7.
- ^ Crandall & Pomerance 2005 , стр. 6 .
- ^ Crandall & Pomerance 2005 , раздел 3.7, Подсчет простых чисел, стр. 152–162 .
- ^ a b Crandall & Pomerance 2005 , стр. 10 .
- ^ дю Сотуа, Маркус (2011). "Каковы шансы, что ваш номер телефона простой?" . Числовые тайны: математическая одиссея через повседневную жизнь . Пресса Св. Мартина. С. 50–52. ISBN 978-0-230-12028-0.
- ^ Апостол 1976 , раздел 4.6, теорема 4.7
- ^ Гельфанд И.М .; Шен, Александр (2003). Алгебра . Springer. п. 37. ISBN 978-0-8176-3677-7.
- ^ Моллин, Ричард А. (1997). Фундаментальная теория чисел с приложениями . Дискретная математика и ее приложения. CRC Press. п. 76. ISBN 978-0-8493-3987-5.
- ^ Crandall & Pomerance 2005 , теорема 1.1.5, с. 12 .
- ^ Грин, Бен ; Тао, Теренс (2008). «Простые числа содержат произвольно длинные арифметические прогрессии». Анналы математики . 167 (2): 481–547. arXiv : math.NT / 0404188 . DOI : 10.4007 / анналы.2008.167.481 . S2CID 1883951 .
- ^ Хуа, Л.К. (2009) [1965]. Аддитивная теория простых чисел . Переводы математических монографий. 13 . Провиденс, Род-Айленд: Американское математическое общество. С. 176–177. ISBN 978-0-8218-4942-2. Руководство по ремонту 0194404 . OCLC 824812353 .
- ^ Последовательность этих простых чисел, начиная с скорее, чем , перечислено Лава, Паоло Пьетро; Бальзаротти, Джорджио (2010). «Глава 33. Формула удачи» . 103 curiosità matematiche: Teoria dei numeri, delle cifre e delle relazioni nella matematica contemporanea (на итальянском языке). Ulrico Hoepli Editore SpA стр. 133. ISBN. 978-88-203-5804-4.
- ^ Чемберленд, Марк (2015). «Числа Хегнера» . Одиночные цифры: хвала маленьким числам . Издательство Принстонского университета. С. 213–215. ISBN 978-1-4008-6569-7.
- ^ а б Гай, Ричард (2013). «A1 Простые значения квадратичных функций» . Нерешенные проблемы теории чисел . Проблемные книги по математике (3-е изд.). Springer. С. 7–10. ISBN 978-0-387-26677-0.
- ^ Паттерсон, SJ (1988). Введение в теорию дзета-функции Римана . Кембриджские исследования в области высшей математики. 14 . Издательство Кембриджского университета, Кембридж. п. 1. DOI : 10.1017 / CBO9780511623707 . ISBN 978-0-521-33535-5. Руководство по ремонту 0933558 .
- ^ Борвейн, Питер ; Чой, Стивен; Руни, Брендан; Вейратмюллер, Андреа (2008). Гипотеза Римана: ресурс для поклонников и виртуозов . CMS Книги по математике / Ouvrages de Mathématiques de la SMC. Нью-Йорк: Спрингер. С. 10–11. DOI : 10.1007 / 978-0-387-72126-2 . ISBN 978-0-387-72125-5. Руководство по ремонту 2463715 .
- ^ Сандифер 2007 , стр. 191-193 .
- ^ Borwein et al. 2008 , Гипотеза 2.7 (гипотеза Римана), с. 15 .
- Перейти ↑ Patterson 1988 , p. 7.
- ^ а б Borwein et al. 2008 , стр. 18.
- ↑ Натансон, 2000 , Глава 9, Теорема о простых числах, стр. 289–324 .
- ^ Загир, Дон (1977). «Первые 50 миллионов простых чисел». Математический интеллигент . 1 (S2): 7–19. DOI : 10.1007 / bf03351556 . S2CID 37866599 . См. Особенно стр. 14–16.
- Перейти ↑ Kraft & Washington (2014) , Proposition 5.3 , p. 96.
- ^ Шахриари, Шахриар (2017). Алгебра в действии: курс групп, колец и полей . Чистые и прикладные тексты бакалавриата. 27 . Американское математическое общество. С. 20–21. ISBN 978-1-4704-2849-5.
- ^ Дадли 1978 , теорема 3, стр. 28 .
- ^ Shahriari 2017 , стр. 27-28 .
- ^ Ribenboim 2004 , малая теорема Ферма и примитивные корнимодулю простого, стр. 17-21.
- ^ Ribenboim 2004 , Свойство Giuga, стр. 21-22.
- ^ Рибенбойм 2004 , Теорема Вильсона, стр. 21.
- ^ а б в Чайлдресс, Нэнси (2009). Теория поля классов . Universitext. Спрингер, Нью-Йорк. С. 8–11. DOI : 10.1007 / 978-0-387-72490-4 . ISBN 978-0-387-72489-8. Руководство по ремонту 2462595 .См. Также стр. 64.
- ^ Эриксон, Марти; Ваззана, Энтони; Гарт, Дэвид (2016). Введение в теорию чисел . Учебники по математике (2-е изд.). Бока-Ратон, Флорида: CRC Press. п. 200. ISBN 978-1-4987-1749-6. Руководство по ремонту 3468748 .
- ^ Вайль, Андре (1995). Основная теория чисел . Классика по математике. Берлин: Springer-Verlag. п. 43 . ISBN 978-3-540-58655-5. Руководство по ремонту 1344916 .Обратите внимание, однако, что некоторые авторы, такие как Чайлдресс (2009), вместо этого используют слово «место» для обозначения класса эквивалентности норм.
- ^ Кох, Х. (1997). Алгебраическая теория чисел . Берлин: Springer-Verlag. п. 136. CiteSeerX 10.1.1.309.8812 . DOI : 10.1007 / 978-3-642-58095-6 . ISBN 978-3-540-63003-6. Руководство по ремонту 1474965 .
- ^ Лауритцен, Нильс (2003). Конкретная абстрактная алгебра: от чисел к базисам Грёбнера . Кембридж: Издательство Кембриджского университета. п. 127. DOI : 10.1017 / CBO9780511804229 . ISBN 978-0-521-53410-9. Руководство по ремонту 2014 г. 325 .
- ^ Lauritzen 2003 , следствие 3.5.14, п. 133; Лемма 3.5.18, с. 136.
- ↑ Kraft & Washington, 2014 , Раздел 12.1, Суммы двух квадратов, стр. 297–301 .
- ^ Эйзенбуд, Дэвид (1995). Коммутативная алгебра . Тексты для выпускников по математике. 150 . Берлин; Нью-Йорк: Springer-Verlag. Раздел 3.3. DOI : 10.1007 / 978-1-4612-5350-1 . ISBN 978-0-387-94268-1. Руководство по ремонту 1322960 .
- ^ Шафаревич, Игорь Р. (2013). "Значение Спецификация А {\ displaystyle \ operatorname {Spec} A} " . Базовая алгебраическая геометрия 2: схемы и комплексные многообразия (3-е изд.). Springer, Heidelberg. Стр. 5. doi : 10.1007 / 978-3-642-38010-5 . ISBN 978-3-642-38009-9. Руководство по ремонту 3100288 .
- ^ Нойкирх, Юрген (1999). Алгебраическая теория чисел . Grundlehren der Mathematischen Wissenschaften [Основные принципы математических наук]. 322 . Берлин: Springer-Verlag. Раздел I.8, п. 50. DOI : 10.1007 / 978-3-662-03983-0 . ISBN 978-3-540-65399-8. Руководство по ремонту 1697859 .
- ^ Neukirch 1999 , раздел I.7, стр. 38
- ^ Stevenhagen, P .; Ленстра, HW, младший (1996). «Чеботарев и его теорема плотности». Математический интеллигент . 18 (2): 26–37. CiteSeerX 10.1.1.116.9409 . DOI : 10.1007 / BF03027290 . Руководство по ремонту 1395088 . S2CID 14089091 .
- ^ Холл, Маршалл (2018). Теория групп . Дуврские книги по математике. Courier Dover Publications. ISBN 978-0-486-81690-6.По поводу теорем Силова см. Стр. 43; теорему Лагранжа см. на стр. 12; теорему Бернсайда см. на стр. 143.
- ^ Брайант, Джон; Сангвин, Кристофер Дж. (2008). Насколько круглый ваш круг? Где встречаются инженерия и математика . Издательство Принстонского университета. п. 178 . ISBN 978-0-691-13118-4.
- ^ Харди, Годфри Гарольд (2012) [1940]. Извинения математика . Издательство Кембриджского университета. п. 140 . ISBN 978-0-521-42706-7. OCLC 922010634 .
Никто еще не открыл какой-либо военной цели, которой могла бы служить теория чисел или относительности, и кажется маловероятным, что кто-то будет делать это в течение многих лет.
- ^ Гиблин, Питер (1993). Простые числа и программирование . Издательство Кембриджского университета. п. 39 . ISBN 978-0-521-40988-9.
- ^ Giblin 1993 , стр. 54
- ^ а б Ризель 1994 , стр. 220 .
- ^ Буллинк, Маартен (2010). «История факторных таблиц с заметками о зарождении теории чисел 1657–1817» . Revue d'Histoire des Mathématiques . 16 (2): 133–216.
- ^ Вагстафф, Сэмюэл С. Младший (2013). Радость факторинга . Студенческая математическая библиотека. 68 . Американское математическое общество. п. 191. ISBN. 978-1-4704-1048-3.
- ^ Крэндалл, Ричард ; Померанс, Карл (2005). Простые числа: вычислительная перспектива (2-е изд.). Springer. п. 121. ISBN. 978-0-387-25282-7.
- ^ Фарач-Колтон, Мартин ; Цай, Мэн-Цунг (2015). «О сложности вычисления таблиц простых чисел». В Эльбассиони - Халед; Макино, Кадзухиса (ред.). Алгоритмы и вычисления: 26-й Международный симпозиум, ISAAC 2015, Нагоя, Япония, 9-11 декабря 2015 г., Материалы . Конспект лекций по информатике. 9472 . Springer. С. 677–688. arXiv : 1504.05240 . DOI : 10.1007 / 978-3-662-48971-0_57 .
- ^ Гривз, Джордж (2013). Решета в теории чисел . Ergebnisse der Mathematik и ихрер Гренцгебиете (3. Folge). 43 . Springer. п. 1. ISBN 978-3-662-04658-6.
- ^ а б Громкович, Юрай (2001). «5.5 Библиографические примечания» . Алгоритмика сложных задач . Тексты по теоретической информатике. Серия EATCS. Springer-Verlag, Берлин. С. 383–385. DOI : 10.1007 / 978-3-662-04616-6 . ISBN 978-3-540-66860-2. Руководство по ремонту 1843669 . S2CID 31159492 .
- ^ а б Коблиц, Нил (1987). «Глава V. Примитивность и факторинг». Курс теории чисел и криптографии . Тексты для выпускников по математике. 114 . Спрингер-Верлаг, Нью-Йорк. С. 112–149. DOI : 10.1007 / 978-1-4684-0310-7_5 . ISBN 978-0-387-96576-5. Руководство по ремонту 0910297 .
- ^ Пиепшик, Йозеф; Hardjono, Томас; Себери, Дженнифер (2013). «2.3.9 Вероятностные вычисления» . Основы компьютерной безопасности . Springer. С. 51–52. ISBN 978-3-662-07324-7.
- ^ а б Тао, Теренс (2010). «1.11 Тест на простоту AKS» . Эпсилон комнаты, II: страницы третьего года математического блога . Аспирантура по математике. 117 . Провиденс, Род-Айленд: Американское математическое общество. С. 82–86. DOI : 10,1090 / г / м2 / 117 . ISBN 978-0-8218-5280-4. Руководство по ремонту 2780010 .
- ^ а б Аткин А.Л .; Морейн, Ф. (1993). «Эллиптические кривые и доказательство простоты» (PDF) . Математика вычислений . 61 (203): 29–68. Bibcode : 1993MaCom..61 ... 29A . DOI : 10.1090 / s0025-5718-1993-1199989-х . JSTOR 2152935 . Руководство по ремонту 1199989 .
- ^ а б Морейн, Ф. (2007). «Реализация асимптотически быстрой версии алгоритма доказательства простоты эллиптической кривой». Математика вычислений . 76 (257): 493–505. arXiv : math / 0502097 . Bibcode : 2007MaCom..76..493M . DOI : 10.1090 / S0025-5718-06-01890-4 . Руководство по ремонту 2261033 . S2CID 133193 .
- ^ Ленстра, HW младший ; Померанс, Карл (2019). «Проверка на простоту с гауссовскими периодами» (PDF) . Журнал Европейского математического общества . 21 (4): 1229–1269. DOI : 10.4171 / Jems / 861 . Руководство по ремонту 3941463 .
- ^ Карл Померанс ; Джон Л. Селфридж ; Сэмюэл С. Вагстафф младший (июль 1980 г.). «Псевдопреступности до 25 · 10 9 » (PDF) . Математика вычислений . 35 (151): 1003–1026. DOI : 10.1090 / S0025-5718-1980-0572872-7 . JSTOR 2006 210 .
- ^ Роберт Бэйли; Сэмюэл С. Вагстафф-младший (октябрь 1980 г.). "Лукас Псевдопреступления" (PDF) . Математика вычислений . 35 (152): 1391–1417. DOI : 10.1090 / S0025-5718-1980-0583518-6 . JSTOR 2006 406 . Руководство по ремонту 0583518 .
- ^ а б Монье, Луи (1980). «Оценка и сравнение двух эффективных алгоритмов вероятностного тестирования простоты». Теоретическая информатика . 12 (1): 97–108. DOI : 10.1016 / 0304-3975 (80) 90007-9 . Руководство по ремонту 0582244 .
- ^ Тао, Теренс (2009). «1.7. Тест Лукаса – Лемера для простых чисел Мерсенна» . Наследие Пуанкаре, страницы второго года математического блога. Часть I . Провиденс, Род-Айленд: Американское математическое общество. С. 36–41. ISBN 978-0-8218-4883-8. Руководство по ремонту 2523047 .
- ^ Крафт и Вашингтон 2014 , стр. 41 .
- ^ Например, см. Guy 2013 , Простые числа Мерсенна A3. Repunits. Числа Ферма. Простые формы k ⋅ 2 п + 1 {\ Displaystyle к \ cdot 2 ^ {п} +1} . С. 13–21 .
- ^ «Рекордное простое число из 12 миллионов цифр принесет приз в размере 100 000 долларов США» . Electronic Frontier Foundation. 14 октября 2009 . Проверено 4 января 2010 .
- ^ «Награды EFF Cooperative Computing Awards» . Electronic Frontier Foundation. 2008-02-29 . Проверено 4 января 2010 .
- ^ «Подпроект« Семнадцать или крах PrimeGrid »» (PDF) . Проверено 3 января 2017 .
- ^ Колдуэлл, Крис К. «Двадцать лучших: наибольшие известные простые числа» . Основные страницы . Проверено 3 января 2017 .
- ^ Колдуэлл, Крис К. «Двадцать лучших: Факториал» . Основные страницы . Проверено 3 января 2017 .
- ^ Ribenboim 2004 , стр. 4.
- ^ Колдуэлл, Крис К. «Двадцатка лучших: Первобытный» . Основные страницы . Проверено 3 января 2017 .
- ^ Колдуэлл, Крис К. «Двадцать лучших: простые числа-близнецы» . Основные страницы . Проверено 3 января 2017 .
- ^ Крафт и Вашингтон 2014 , стр. 275 .
- ^ Хоффштейн, Джеффри; Пайфер, Джилл ; Сильверман, Джозеф Х. (2014). Введение в математическую криптографию . Тексты для бакалавриата по математике (2-е изд.). Springer. п. 329. ISBN. 978-1-4939-1711-2.
- ^ Померанс, Карл (1996). «Сказка о двух ситах». Уведомления Американского математического общества . 43 (12): 1473–1485. Руководство по ремонту 1416721 .
- ^ Эммануэль Thomé, «795-битный факторинг и дискретные логарифмы,» 2 декабря 2019.
- ^ Риффель, Элеонора Г .; Полак, Вольфганг Х. (2011). «Глава 8. Алгоритм Шора» . Квантовые вычисления: мягкое введение . MIT Press. С. 163–176. ISBN 978-0-262-01506-6.
- ^ Мартин-Лопес, Энрике; Лэйнг, Энтони; Лоусон, Томас; Альварес, Роберто; Чжоу, Сяо-Ци; О'Брайен, Джереми Л. (12 октября 2012 г.). «Экспериментальная реализация алгоритма квантового разложения Шора с использованием рециклинга кубитов». Природа Фотоника . 6 (11): 773–776. arXiv : 1111.4147 . Bibcode : 2012NaPho ... 6..773M . DOI : 10.1038 / nphoton.2012.259 . S2CID 46546101 .
- ^ Чиргвин, Ричард (9 октября 2016 г.). «Крипто требует большей прозрачности, - предупреждают исследователи» . Реестр .
- ^ Hoffstein, Pipher & Silverman 2014 , раздел 2.3, Диффи-Хеллмана обмена ключами, стр. 65-67.
- ^ Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Стейн, Клиффорд (2001) [1990]. «11.3 Универсальное хеширование». Введение в алгоритмы (2-е изд.). MIT Press и McGraw-Hill. С. 232–236. ISBN 0-262-03293-7. Для -независимое хеширование см. задачу 11–4, с. 251. Благодарность Картеру и Вегману см. В примечаниях к главе, с. 252.
- ^ Гудрич, Майкл Т .; Тамассия, Роберто (2006). Структуры данных и алгоритмы в Java (4-е изд.). Джон Вили и сыновья. ISBN 978-0-471-73884-8.См. «Квадратичное зондирование» с. 382, и упражнение C – 9.9, p. 415.
- ^ Киртланд, Джозеф (2001). Идентификационные номера и схемы контрольных цифр . Учебные материалы. 18 . Математическая ассоциация Америки. С. 43–44. ISBN 978-0-88385-720-5.
- ^ Дойч, П. (1996). Спецификация формата сжатых данных ZLIB версии 3.3 . Запрос комментариев . 1950 . Сетевая рабочая группа.
- ^ Кнут, Дональд Э. (1998). «3.2.1 Линейная конгруэнтная модель». Искусство программирования, Vol. 2: получисленные алгоритмы (3-е изд.). Эддисон-Уэсли. С. 10–26. ISBN 978-0-201-89684-8.
- ^ Мацумото, Макото; Нисимура, Такудзи (1998). "Мерсенн Твистер: 623-мерный равномерно распределенный генератор псевдослучайных чисел". Транзакции ACM по моделированию и компьютерному моделированию . 8 (1): 3–30. CiteSeerX 10.1.1.215.1141 . DOI : 10.1145 / 272991.272995 . S2CID 3332028 .
- ^ Рот, KF (1951). «О проблеме Хайльбронна». Журнал Лондонского математического общества . Вторая серия. 26 (3): 198–204. DOI : 10,1112 / jlms / s1-26.3.198 . Руководство по ремонту 0041889 .
- ^ Кокс, Дэвид А. (2011). «Почему Эйзенштейн доказал критерий Эйзенштейна и почему Шенеман открыл его первым» (PDF) . Американский математический ежемесячник . 118 (1): 3–31. CiteSeerX 10.1.1.398.3440 . DOI : 10,4169 / amer.math.monthly.118.01.003 . S2CID 15978494 .
- ^ Ланг, Серж (2002). Алгебра . Тексты для выпускников по математике. 211 . Берлин; Нью-Йорк: Springer-Verlag . DOI : 10.1007 / 978-1-4613-0041-0 . ISBN 978-0-387-95385-4. Руководство по ремонту 1878556 ., Раздел II.1, стр. 90
- ^ Шуберт, Хорст (1949). "Die eindeutige Zerlegbarkeit eines Knotens in Primknoten". S.-B Heidelberger Akad. Wiss. Math.-Nat. Kl . 1949 (3): 57–104. Руководство по ремонту 0031733 .
- ^ Милнор, Дж. (1962). «Единственная теорема о разложении для трехмерных многообразий». Американский журнал математики . 84 (1): 1–7. DOI : 10.2307 / 2372800 . JSTOR 2372800 . Руководство по ремонту 0142125 .
- ^ Боклан и Конвей (2017) также включают, который не имеет такой формы.
- ^ а б Кржижек, Михал; Лука, Флориан; Сомер, Лоуренс (2001). 17 лекций о числах Ферма: от теории чисел к геометрии . CMS Книги по математике. 9 . Нью-Йорк: Springer-Verlag. С. 1–2. DOI : 10.1007 / 978-0-387-21850-2 . ISBN 978-0-387-95332-8. Руководство по ремонту 1866957 .
- ^ Boklan, Kent D .; Конвей, Джон Х. (январь 2017 г.). «Ожидать более одной миллиардной нового Ferma т штрихом!». Математический интеллигент . 39 (1): 3–5. arXiv : 1605.01371 . DOI : 10.1007 / s00283-016-9644-3 . S2CID 119165671 .
- ^ Глисон, Эндрю М. (1988). «Трисечение угла, семиугольник и трехугольник». Американский математический ежемесячник . 95 (3): 185–194. DOI : 10.2307 / 2323624 . JSTOR 2323624 . Руководство по ремонту 0935432 .
- ^ Циглер, Гюнтер М. (2015). «Пушки по воробьям». Информационный бюллетень Европейского математического общества (95): 25–31. Руководство по ремонту 3330472 .
- ^ Петерсон, Иварс (28 июня 1999 г.). «Возвращение Зеты» . MAA Online . Архивировано из оригинального 20 октября 2007 года . Проверено 14 марта 2008 .
- ^ Хейс, Брайан (2003). «Информатика: спектр римания». Американский ученый . 91 (4): 296–300. DOI : 10.1511 / 2003.26.3349 . JSTOR 27858239 .
- ^ Бенгтссон, Ингемар; Cyczkowski, Кароль (2017). Геометрия квантовых состояний: введение в квантовую запутанность (второе изд.). Кембридж: Издательство Кембриджского университета . С. 313–354. ISBN 978-1-107-02625-4. OCLC 967938939 .
- ^ Чжу, Хуанцзюнь (2010). «SIC POVM и группы Клиффорда в простых измерениях» . Журнал физики A: математический и теоретический . 43 (30): 305305. arXiv : 1003.3591 . Bibcode : 2010JPhA ... 43D5305Z . DOI : 10.1088 / 1751-8113 / 43/30/305305 . S2CID 118363843 .
- ^ Goles, E .; Schulz, O .; Маркус, М. (2001). «Выбор простого числа циклов в модели хищник-жертва». Сложность . 6 (4): 33–38. Bibcode : 2001Cmplx ... 6d..33G . DOI : 10.1002 / cplx.1040 .
- ^ Кампос, Пауло, РА; де Оливейра, Вивиан М .; Джиро, Роналду; Гальвао, Дуглас С. (2004). «Возникновение простых чисел в результате эволюционной стратегии». Письма с физическим обзором . 93 (9): 098107. arXiv : q-bio / 0406017 . Bibcode : 2004PhRvL..93i8107C . DOI : 10.1103 / PhysRevLett.93.098107 . PMID 15447148 . S2CID 88332 .
- ^ «Нашествие выводка» . Экономист . 6 мая 2004 . Проверено 26 ноября 2006 .
- ^ Циммер, Карл (15 мая 2015 г.). «Бамбуковые математики» . Феномены: ткацкий станок. National Geographic . Проверено 22 февраля 2018 года .
- ^ Хилл, Питер Дженсен, изд. (1995). Спутник Мессиана . Портленд, Орегон: Amadeus Press. Бывший. 13.2 Messe de la Pentecôte 1 Entrée. ISBN 978-0-931340-95-6.
- ^ Померанс, Карл (2004). «Простые числа и поиск внеземного разума» (PDF) . В Hayes, Дэвид Ф .; Росс, Питер (ред.). Математические приключения для студентов и любителей . MAA Spectrum. Вашингтон, округ Колумбия: Математическая ассоциация Америки. С. 3–6. ISBN 978-0-88385-548-5. Руководство по ремонту 2085842 .
- ^ GrrlScientist (16 сентября 2010 г.). «Любопытный случай с собакой в ночное время» . Наука. Хранитель . Проверено 22 февраля 2010 года .
- ^ Шиллингер, Лизл (9 апреля 2010 г.). «Рассчитывать друг на друга» . Воскресное книжное обозрение. Нью-Йорк Таймс .
Внешние ссылки
- «Простое число» . Энциклопедия математики . EMS Press . 2001 [1994].
- Колдуэлл, Крис, The Prime Pages на primes.utm.edu .
- Простые числа в наше время на BBC
- Пакет Plus для учителей и учеников: простые числа из Plus, бесплатного онлайн-журнала по математике, выпускаемого Millennium Mathematics Project в Кембриджском университете.
Генераторы и калькуляторы
- Программа проверки простых чисел определяет наименьший простой множитель числа.
- Быстрый онлайн-тест на простоту с факторизацией использует метод эллиптической кривой (до тысячных цифр, требуется Java).
- Огромная база простых чисел
- Простые числа до 1 триллиона