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

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

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

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

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

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

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

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

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

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

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

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

Множество всех простых чисел иногда обозначается (а полужирным капитала P ) , либо (в доске жирным шрифтом буквы П).

История

Папирус Ахмес , от около 1550 г. до н.э., имеет египетские дроби разложение различных форм для простых и составных чисел. Однако самые ранние сохранившиеся записи о явном изучении простых чисел относятся к древнегреческой математике . Euclid «s элементов (с. 300 до н.э.) доказывает беспредельность простых чисел и основной теоремы арифметики , и показывает , как построить совершенное число от штрихом Mersenne . Другое греческое изобретение, Сито Эратосфена , до сих пор используется для построения списков простых чисел.

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

В 1640 году Пьер де Ферма сформулировал (без доказательства) малую теорему Ферма (позже доказанную Лейбницем и Эйлером ). Ферма также исследовал простоту чисел Ферма , а Марин Мерсенн изучал простые числа Мерсенна , простые числа формы с самим простым числом . Христиан Гольдбах сформулировал гипотезу Гольдбаха о том , что каждое четное число является суммой двух простых чисел, в письме к Эйлеру 1742 года. Эйлер доказал гипотезу Альхазена (теперь теорема Евклида – Эйлера ) о том, что все четные совершенные числа могут быть построены из простых чисел Мерсенна. Он ввел методы математического анализа в эту область в своих доказательствах бесконечности простых чисел и расходимости суммы обратных простых чисел . В начале 19 - го века, Лежандр и Гаусс высказали предположение , что , как стремится к бесконечности, число простых чисел до является асимптотическим к , где это натуральный логарифм от . Более слабым следствием такой высокой плотности простых чисел был постулат Бертрана о том , что для каждого существует простое число между и , доказанный в 1852 году Пафнутым Чебышевым . Идеи Бернхарда Римана в его статье 1859 года о дзета-функции набросали схему доказательства гипотезы Лежандра и Гаусса. Хотя тесно связанная гипотеза Римана остается недоказанной, набросок Римана был завершен в 1896 году Адамаром и де ла Валле Пуссенами , и теперь результат известен как теорема о простых числах . Другим важным результатом XIX века была теорема Дирихле об арифметических прогрессиях , согласно которой некоторые арифметические прогрессии содержат бесконечно много простых чисел.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

По основной теореме имеет разложение на простые множители

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

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

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

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

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

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

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

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

Было высказано много предположений о простых числах. Часто имея элементарную формулировку, многие из этих гипотез выдерживали доказательство в течение десятилетий: все четыре проблемы Ландау с 1912 года до сих пор не решены . Одна из них - это гипотеза Гольдбаха , которая утверждает, что каждое четное целое число больше 2 может быть записано как сумма двух простых чисел. По состоянию на 2014 год эта гипотеза была проверена для всех чисел вплоть до более слабых утверждений, чем это было доказано, например, теорема Виноградова гласит, что каждое достаточно большое нечетное целое число может быть записано как сумма трех простых чисел. Теорема Чена гласит, что каждое достаточно большое четное число может быть выражено как сумма простого и полупростого числа (произведение двух простых чисел). Кроме того, любое четное целое число больше 10 можно записать как сумму шести простых чисел. Раздел теории чисел, изучающий такие вопросы, называется аддитивной теорией чисел .

Другой тип проблем касается пробелов между простыми числами, то есть различий между последовательными простыми числами. Существование произвольно больших промежутков между простыми числами можно увидеть, отметив, что последовательность состоит из составных чисел для любого натурального числа. Однако большие промежутки между простыми числами возникают намного раньше, чем показывает этот аргумент. Например, первый пробел длины 8 находится между простыми числами 89 и 97, что намного меньше, чем Предполагается, что существует бесконечно много простых чисел-близнецов , пар простых чисел с разностью 2; это гипотеза простого близнеца . Гипотеза полиньяка государства в более общем смысле, что для любого натурального числа существует бесконечное множество пар последовательных простых чисел , которые отличаются по гипотезе Andrica в , гипотеза брокара , гипотеза Лежандра , и гипотеза Oppermann по всем предположить , что самые большие промежутки между штрихами от до должно быть не более приблизительно результат это, как известно, следует из гипотезы Римана, в то время как гораздо более сильная гипотеза Крамера устанавливает наибольший размер разрыва в разрядах простых чисел , может быть обобщена на простые числа , шаблоны в различиях между более чем двумя простыми числами. Их бесконечность и плотность являются предметом первой гипотезы Харди – Литтлвуда , которая может быть мотивирована эвристикой , согласно которой простые числа ведут себя аналогично случайной последовательности чисел с плотностью, заданной теоремой о простых числах.

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

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

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

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

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

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

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

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

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

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

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

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

Функция подсчета простых чисел определяется как количество простых чисел, не превышающих . Например, поскольку существует пять простых чисел, меньших или равных 11. Такие методы, как алгоритм Мейселя – Лемера, могут вычислять точные значения быстрее, чем было бы возможно перечислить каждое простое число до . Теорема о простых числах утверждает, что это асимптотическое значение , которое обозначается как

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

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

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

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

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

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

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

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

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

Спираль Улама
Улама спираль . Простые числа (красные) кластеризуются на одних диагоналях, а на других нет. Простые значения показаны синим цветом.

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

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

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

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

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

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

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

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

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

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

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

Некоторые теоремы о простых числах можно сформулировать с помощью модульной арифметики. Например, маленькая теорема Ферма утверждает, что если (mod ), то (mod ). Суммируя это по всем вариантам, получаем уравнение

действительно, когда простое число. Гипотеза Джуги гласит, что это уравнение также является достаточным условием для простоты . Теорема Вильсона гласит, что целое число является простым тогда и только тогда, когда факториал конгруэнтен mod . Для составного числа это не может быть выполнено, так как один из его факторов водоразделов и п и , и так невозможно.

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

-Адическая порядок целого числа есть число копий в первичном разложении . Та же концепция может быть расширена от целых до рациональных чисел, определив -адический порядок фракции быть . -Адическое абсолютное значение любого рационального числа затем определяются как . Умножение целого числа на его -адическое абсолютное значение отменяет множители в его факторизации, оставляя только другие простые числа. Так же, как расстояние между двумя действительными числами можно измерить абсолютным значением их расстояния, расстояние между двумя рациональными числами можно измерить их -адическим расстоянием, -адическим абсолютным значением их разности. Для этого определения расстояния два числа находятся близко друг к другу (они имеют небольшое расстояние), когда их разница кратна большой степени . Точно так же, как действительные числа могут быть сформированы из рациональных чисел и их расстояний, путем добавления дополнительных предельных значений для формирования полного поля , рациональные числа с -адическим расстоянием могут быть расширены до другого полного поля, -адического числа .

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

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

Gaussian простых чисел с нормой менее 500

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

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

Основная теорема арифметики продолжает выполняться (по определению) в областях единственной факторизации. Примером такой области являются гауссовы целые числа , кольцо комплексных чисел в форме где обозначает мнимую единицу, а и - произвольные целые числа. Его простые элементы известны как простые числа Гаусса . Не каждое число, которое является простым среди целых чисел, остается простым в целых числах Гаусса; например, число 2 можно записать как произведение двух гауссовских простых чисел и . Рациональные простые числа (простые элементы в целых числах), конгруэнтные 3 по модулю 4, являются гауссовскими простыми числами, но рациональные простые числа, конгруэнтные 1 по модулю 4, - нет. Это следствие теоремы Ферма о суммах двух квадратов , которая гласит, что нечетное простое число выражается как сумма двух квадратов , и, следовательно, факторизуется как , когда точно равно 1 по модулю 4.

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

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

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

Теория групп

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

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

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

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

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

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

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

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

Сита

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

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

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

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

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

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

Контрольная работа Разработано в Тип Продолжительность Примечания использованная литература
Тест на простоту AKS 2002 г. детерминированный
Доказательство простоты эллиптической кривой 1986 г. Лас Вегас эвристически
Тест на простоту Baillie – PSW 1980 г. Монте-Карло
Тест на простоту Миллера – Рабина 1980 г. Монте-Карло вероятность ошибки
Тест на простоту Соловея – Штрассена. 1977 г. Монте-Карло вероятность ошибки

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

В дополнение к вышеупомянутым тестам, применимым к любому натуральному числу, некоторые числа особой формы можно быстрее проверить на простоту. Например, тест на простоту Лукаса – Лемера может детерминированно определить, является ли число Мерсенна (на единицу меньше степени двойки ) простым, за одно и то же время, как и на одной итерации теста Миллера – Рабина. Вот почему с 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 г. Патрик Ларош, Great Internet Mersenne Prime Search
Proth Prime 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

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

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

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

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

Некоторые алгоритмы шифрования с открытым ключом , такие как RSA и обмен ключами Диффи – Хеллмана , основаны на больших простых числах ( обычно 2048- битные простые числа). RSA полагается на предположение, что намного проще (то есть более эффективно) выполнить умножение двух (больших) чисел и чем вычислить и (предполагаемое взаимно простое ), если известен только продукт . Обмен ключами Диффи – Хеллмана основан на том факте, что существуют эффективные алгоритмы для модульного возведения в степень (вычисления ), в то время как обратная операция ( дискретный логарифм ) считается сложной проблемой.

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

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

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

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

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

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

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

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

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

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

с более неотрицательном . Они названы в честь Пьера де Ферма , который предположил, что все такие числа простые. Первые пять из этих чисел - 3, 5, 17, 257 и 65 537 - простые, но составные, как и все другие числа Ферма, проверенные по состоянию на 2017 год. Обычный -угольник можно построить с помощью линейки и компаса, если и только если нечетные простые множители (если таковые имеются) являются различными простыми числами Ферма. Точно так же правильный -угольник может быть построен с использованием линейки, циркуля и трисектора угла тогда и только тогда, когда простые множители представляют собой любое количество копий 2 или 3 вместе с (возможно, пустым) набором различных простых чисел Пирпонта, простых чисел форма .

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

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

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

Биология

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

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

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

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

Примечания

использованная литература

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

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