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

редактировать

Положительное целое число с ровно двумя делителями, 1 и само по себе

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

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

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

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

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

Содержание

  • 1 Определение и примеры
  • 2 История
    • 2.1 Примитивность единицы
  • 3 Элементарные свойства
    • 3.1 Уникальная факторизация
    • 3.2 Бесконечность
    • 3.3 Формулы для простых чисел
    • 3.4 Открытые вопросы
  • 4 Аналитические свойства
    • 4.1 Аналитическое доказательство теоремы Евклида
    • 4.2 Число простых чисел ниже заданной границы
    • 4.3 Арифметические прогрессии
    • 4.4 Простые значения квадратичных многочленов
    • 4.5 Дзета-функция и гипотеза Римана
  • 5 Абстрактная алгебра
    • 5.1 Модульная арифметические и конечные поля
    • 5.2 p-адические числа
    • 5.3 Простые элементы в кольцах
    • 5.4 Простые идеалы
    • 5.5 Теория групп
  • 6 Вычислительные методы
    • 6.1 Пробное деление
    • 6.2 Сита
    • 6.3 Сравнение проверки простоты и доказательства простоты
    • 6.4 Специальные алгоритмы и наибольшее известное простое число
    • 6.5 Целочисленная факторизация
    • 6.6 Прочие вычисления приложения
  • 7 Другие приложения
    • 7.1 Конструируемые многоугольники и разбиения на многоугольники
    • 7.2 Квантовая механика
    • 7.3 Биология
    • 7.4 Искусство и литература
  • 8 Примечания
  • 9 Ссылки
  • 10 Внешние ссылки
    • 10.1 Генераторы и калькуляторы

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

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

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

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

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

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

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

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

История

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

Математический папирус Райнда, датируемый примерно 1550 г. до н.э., имеет египетские дроби разложения различных форм для простых и составных чисел. Однако самые ранние сохранившиеся записи явного изучения простых чисел относятся к древнегреческой математике. Евклид Элементы (ок. 300 г. до н.э.) доказывает бесконечность простых чисел и фундаментальную теорему арифметики и показывает, как построить совершенное число из простого числа Мерсенна. Другое греческое изобретение, Сито Эратосфена, до сих пор используется для построения списков простых чисел.

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

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

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

С 1951 г. все наибольшие известные простые числа были найдены с помощью этих тестов на компьютерах. Поиск все более крупных простых чисел вызвал интерес за пределами математических кругов благодаря Great Internet 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 следует указывать не как простое число, а в отдельной специальной категории как "единица ".

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

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

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

34866 = 2 ⋅ 3 ⋅ 3 ⋅ 13 ⋅ 149 = 2 ⋅ 3 2 ⋅ 13 ⋅ 149. {\ displaystyle {\ begin {align} 34866 = 2 \ cdot 3 \ cdot 3 \ cdot 13 \ cdot 149 \\ = 2 \ cdot 3 ^ {2} \ cdot 13 \ cdot 149. \ end {align}}}{\ displaystyle {\ begin {align} 34866 = 2 \ cdot 3 \ cdot 3 \ cdot 13 \ cdot 149 \\ = 2 \ cdot 3 ^ {2} \ cdot 13 \ cdot 149. \ конец {выровнено}}}

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

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

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

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

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

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

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

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

N = 1 + p 1 ⋅ p 2 ⋯ pn. {\ displaystyle N = 1 + p_ {1} \ cdot p_ {2} \ cdots p_ {n}.}{\ displaystyle N = 1 + p_ {1} \ cdot p_ {2} \ cdots p_ {n}.}

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

N = p 1 ′ ⋅ p 2 ′ ⋯ pm ′ {\ displaystyle N = p '_ {1} \ cdot p' _ {2} \ cdots p '_ {m}}{\displaystyle N=p'_{1}\cdot p'_{2}\cdots p'_{m}}

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

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

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

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

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

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

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

⌊ A 3 n ⌋ и ⌊ 2 ⋯ 2 2 μ ⌋ {\ Displaystyle \ left \ lfloor A ^ {3 ^ {n}} \ right \ rfloor {\ text {and}} \ left \ lfloor 2 ^ {\ cdots ^ {2 ^ {2 ^ { \ mu}}}} \ right \ rfloor}{\ displaystyle \ left \ lfloor A ^ {3 ^ { n}} \ right \ rfloor {\ text {and}} \ left \ lfloor 2 ^ {\ cdots ^ {2 ^ {2 ^ {\ mu}}}} \ right \ rfloor}

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(1 3 + 1 5) + (1 5 + 1 7) + (1 11 + 1 13) + ⋯, {\ displaystyle \ left ({{\ frac {1} {3}} + {\ frac {1} {5}}} \ right) + \ left ({{\ frac {1} {5}} + {\ frac {1} {7}}} \ right) + \ left ({{\ frac {1} {11}} + {\ frac {1} {13}}} \ right) + \ cdots,}{\ displaystyle \ left ({{\ frac {1} {3}} + {\ frac {1} {5} }} \ right) + \ left ({{\ frac {1} {5}} + {\ frac {1} {7}}} \ right) + \ left ({{\ frac {1} {11}} + {\ frac {1} {13}}} \ right) + \ cdots,}

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

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

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

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

π (n) ∼ n log ⁡ n, {\ displaystyle \ pi (n) \ sim {\ frac {n} {\ log n}}, }{\ displaystyle \ pi (n) \ sim {\ frac {n} {\ log n}},}

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

π (n) ∼ Li ⁡ (n) = ∫ 2-й журнал ⁡ t. {\ displaystyle \ pi (n) \ sim \ operatorname {Li} (n) = \ int _ {2} ^ {n} {\ frac {dt} {\ log t}}.}{\ displaystyle \ pi (n) \ sim \ operatorname {Li} (n) = \ int _ {2} ^ {n} {\ frac {dt} {\ log t}}. }

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ζ (s) = ∑ n = 1 ∞ 1 ns = ∏ p prime 1 1 - p - s. {\ displaystyle \ zeta (s) = \ sum _ {n = 1} ^ {\ infty} {\ frac {1} {n ^ {s}}} = \ prod _ {p {\ text {prime}}} {\ frac {1} {1-p ^ {- s}}}.}{\ displaystyle \ zeta ( s) = \ sum _ {n = 1} ^ {\ infty} {\ frac {1} {n ^ {s}}} = \ prod _ {p {\ text {prime}}} {\ frac {1} {1-p ^ {- s}}}.}

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

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

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

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

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

Некоторые теоремы о простых числах могут быть сформулированы с использованием модульной арифметики. Например, малая теорема Ферма утверждает, что если a ≢ 0 {\ displaystyle a \ not \ Equiv 0}{\ displaystyle a \ not \ Equiv 0} (mod p {\ displaystyle p}p ), затем ap - 1 ≡ 1 {\ displaystyle a ^ {p-1} \ Equiv 1}{\ displaystyle a ^ {p-1} \ Equiv 1} (mod p {\ displaystyle p}p ). Суммируя это по всем вариантам a {\ displaystyle a}a , уравнение

∑ a = 1 p - 1 ap - 1 ≡ (p - 1) ⋅ 1 ≡ - 1 (mod п), {\ Displaystyle \ сумма _ {а = 1} ^ {р-1} а ^ {р-1} \ экв (р-1) \ CDOT 1 \ эквив -1 {\ pmod {р}},}{\ displaystyle \ sum _ {a = 1} ^ {p-1} a ^ {p-1} \ Equiv (p -1) \ cdot 1 \ Equiv -1 {\ pmod {p}},}

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

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

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

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

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

Гауссовские простые числа с нормой меньше 500

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

{…, - 11, - 7, - 5, - 3, - 2, 2, 3, 5, 7, 11,…}. {\ displaystyle \ {\ dots, -11, -7, -5, -3, -2,2,3,5,7,11, \ dots \} \,.}\ {\ точки, -11, -7, -5, -3, -2,2,3,5,7,11, \ точки \} \,.

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

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

Простые идеалы

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

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

Теория групп

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

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

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

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

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

Пробное деление

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

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

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

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

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

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

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

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

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

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

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

ТипПростое числоДесятичное число цифрДатаНайдено по
простому числу Мерсенна 2-124,862,0487 декабря 2018 г.Патрик Ларош, Great Internet Mersenne Prime Search
Proth prime 10,223 × 2 + 19,383,76131 октября 2016 г.Петер Сабольч, PrimeGrid
факториальное простое число 208 003! - 11,015,843июль 2016 г.Соу Фукуи
первичный прайм 1,098,133 # - 1476,311Март 2012Джеймс П. Берт, PrimeGrid
двойные простые числа 2,996,863,034,895 × 2 ± 1388,342Сентябрь 2016 г.Том Грир, PrimeGrid

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

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

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

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

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

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

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

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

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

Связная сумма двух узлов

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

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

Конструируемых многоугольников и многоугольников

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

Простое число Ферма является единственным числом формы

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

с k {\ displaystyle k}к a неотрицательным целым числом. Они названы в честь Пьера де Ферма, предположил, что все такие числа простые. Первые пять из этих чисел - 3, 5, 17, 257 и 65 537 - простые, но F 5 {\ displaystyle F_ {5}}F_5 является составным, как и все остальные числа Ферма. которые были проверены по состоянию на 2017 год. A обычный n {\ displaystyle n}n-gon можно построить с помощью линейки и компаса тогда и только тогда, когда нечетные простые множители n {\ displaystyle n}n(если есть) различные простыми числами Ферма. Точно так же обычный n {\ displaystyle n}n-угольник может быть использован с использованием линейки, циркуля и трисектора угла тогда и только тогда, когда простые множители n {\ displaystyle n}n - любое копий 2 или 3 вместе с (возможно, пустым) набором различных простых чисел Пирпонта формы, простых чисел 2 a 3 b + 1 { \ displaystyle 2 ^ {a} 3 ^ {b} +1}{\ displaystyle 2 ^ {a} 3 ^ {b} +1} .

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

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

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

Биология

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

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

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

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

Примечания

Ссылки

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

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

Последняя правка сделана 2021-06-02 05:56:31
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте