Свойства простых чисел впервые начали изучать математики Древней Греции. Математики пифагорейской школы (500 — 300 до н.э.) в первую очередь интересовались мистическими и нумерологическими свойствами простых чисел. Они первыми пришли к идеям о совершенных и дружественных числах.
У совершенного числа сумма его собственных делителей равна ему самому. Например, собственные делители числа 6: 1, 2 и 3. 1 + 2 + 3 = 6. У числа 28 делители — это 1, 2, 4, 7 и 14. При этом, 1 + 2 + 4 + 7 + 14 = 28.
Числа называются дружественными, если сумма собственных делителей одного числа равна другому, и наоборот – например, 220 и 284. Можно сказать, что совершенное число является дружественным для самого себя.
Ко времени появления работы Евклида «Начала» в 300 году до н.э. уже было доказано несколько важных фактов касательно простых чисел. В книге IX «Начал» Эвклид доказал, что простых чисел бесконечное количество. Это, кстати, один из первых примеров использования доказательства от противного. Также он доказывает Основную теорему арифметики – каждое целое число можно представить единственным образом в виде произведения простых чисел.
А затем случился большой перерыв в истории исследования простых чисел, связанный со Средними веками.
Следующие открытия были сделаны уже в начале 17-го века математиком Ферма. Он доказал гипотезу Альбера Жирара, что любое простое число вида 4n+1 можно записать уникальным образом в виде суммы двух квадратов, и также сформулировал теорему о том, что любое число можно представить в виде суммы четырёх квадратов.
Он разработал новый метод факторизации больших чисел, и продемонстрировал его на числе 2027651281 = 44021 × 46061. Также он доказал Малую теорему Ферма: если p – простое число, то для любого целого a будет верно a p = a modulo p.
Малая теорема Ферма послужила основой множества других результатов в теории чисел и методов проверки чисел на принадлежность к простым – многие из которых используются и по сей день.
Ферма много переписывался со своими современниками, в особенности с монахом по имени Марен Мерсенн. В одном из писем он высказал гипотезу о том, что числа вида 2 n +1 всегда будут простыми, если n является степенью двойки. Он проверил это для n = 1, 2, 4, 8 и 16, и был уверен, что в случае, когда n не является степенью двойки, число не обязательно получалось простым. Эти числа называются числами Ферма, и лишь через 100 лет Эйлер показал, что следующее число, 2 32 + 1 = 4294967297 делится на 641, и следовательно, не является простым.
Числа вида 2 n — 1 также служили предметом исследований, поскольку легко показать, что если n – составное, то и само число тоже составное. Эти числа называют числами Мерсенна, поскольку он активно их изучал.
Но не все числа вида 2 n — 1, где n – простое, являются простыми. К примеру, 2 11 — 1 = 2047 = 23 * 89. Впервые это обнаружили в 1536 году.
Многие годы числа такого вида давали математикам наибольшие известные простые числа. Что число M19, было доказано Катальди в 1588 году, и в течение 200 лет было наибольшим известным простым числом, пока Эйлер не доказал, что M31 также простое. Этот рекорд продержался ещё сто лет, а затем Люкас показал, что M127 — простое (а это уже число из 39 цифр), и после него исследования продолжились уже с появлением компьютеров.
В 1952 была доказана простота чисел M521, M607, M1279, M2203 и M2281.
К 2005 году найдено 42 простых чисел Мерсенна. Наибольшее из них, M25964951, состоит из 7816230 цифр.
Работа Эйлера оказала огромное влияние на теорию чисел, в том числе и простых. Он расширил Малую теорему Ферма и ввёл φ-функцию. Факторизовал 5-е число Ферма 2 32 +1, нашёл 60 пар дружественных чисел, и сформулировал (но не смог доказать) квадратичный закон взаимности.
Он первым ввёл методы математического анализа и разработал аналитическую теорию чисел. Он доказал, что не только гармонический ряд ∑ (1/n), но и ряд вида
1/2 + 1/3 + 1/5 + 1/7 + 1/11 +…
получаемый суммой величин, обратных к простым числам, также расходится. Сумма n членов гармонического ряда растёт примерно как log(n), а второй ряд расходится медленнее, как log[ log(n) ]. Это значит, что, например, сумма обратных величин ко всем найденным на сегодняшний день простым числам даст всего 4, хотя ряд всё равно расходится.
На первый взгляд кажется, что простые числа распределены среди целых довольно случайно. К примеру, среди 100 чисел, идущих прямо перед 10000000, встречается 9 простых, а среди 100 чисел, идущих сразу после этого значения – всего 2. Но на больших отрезках простые числа распределены достаточно равномерно. Лежандр и Гаусс занимались вопросами их распределения. Гаусс как-то рассказывал другу, что в любые свободные 15 минут он всегда подсчитывает количество простых в очередной 1000 чисел. К концу жизни он сосчитал все простые числа в промежутке до 3 миллионов. Лежандр и Гаусс одинаково вычислили, что для больших n плотность простых чисел составляет 1/log(n). Лежандр оценил количество простых чисел в промежутке от 1 до n, как
А Гаусс – как логарифмический интеграл
с промежутком интегрирования от 2 до n.
Утверждение о плотности простых чисел 1/log(n) известно как Теорема о распределении простых чисел. Её пытались доказать в течение всего 19 века, а прогресса достигли Чебышёв и Риман. Они связали её с гипотезой Римана – по сию пору не доказанной гипотезой о распределении нулей дзета-функции Римана. Плотность простых чисел была одновременно доказана Адамаром и Валле-Пуссеном в 1896 году.
В теории простых чисел есть ещё множество нерешённых вопросов, некоторым из которых уже многие сотни лет:
Текущие рекорды среди простых чисел
Самое большое простое число, вычисленное проектом GIMPS [Great Internet Mersenne Prime Search], можно посмотреть в таблице на официальной странице проекта. www.mersenne.org/primes
Самые большие близнецы среди простых чисел – это 2003663613 × 2 195000 ± 1. Они состоят из 58711 цифр, и были найдены в 2007 году.
Самое большое факториальное простое число (вида n! ± 1) – это 147855! — 1. Оно состоит из 142891 цифр и было найдено в 2002.
Наибольшее праймориальное простое число (число вида n# ± 1) – это 1098133# + 1.
Просто́е число́ — это натуральное число, имеющее ровно два различных натуральных делителя: единицу и само себя. Все остальные натуральные числа, кроме единицы, называются составными. Таким образом, все натуральные числа больше единицы разбиваются на простые и составные. Изучением свойств простых чисел занимается теория чисел. В теории колец простым числам соответствуют неприводимые элементы.
Разложение натуральных чисел в произведение простых
Основная теорема арифметики утверждает, что каждое натуральное число, большее единицы, представимо в виде произведения простых чисел, причём единственным способом с точностью до порядка следования сомножителей. Таким образом, простые числа — элементарные «строительные блоки» натуральных чисел.
Представление натурального числа в виде произведения простых называется разложением на простые или факторизацией числа. На настоящий момент неизвестны полиномиальные алгоритмы факторизации чисел, хотя и не доказано, что таких алгоритмов не существует. На предполагаемой большой вычислительной сложности задачи факторизации базируется криптосистема RSA и некоторые другие. Факторизация с полиномиальной сложностью теоретически возможна на квантовом компьютере с помощью алгоритма Шора.
Алгоритмы поиска и распознавания простых чисел
Простые способы нахождения начального списка простых чисел вплоть до некоторого значения дают Решето Эратосфена, решето Сундарама и решето Аткина.
Однако, на практике вместо получения списка простых чисел зачастую требуется проверить, является ли данное число простым. Алгоритмы, решающие эту задачу, называются тестами простоты. Существует множество полиномиальных тестов простоты, но большинство их являются вероятностными (например, тест Миллера — Рабина) и используются для нужд криптографии. В 2002 году было доказано, что задача проверки на простоту в общем виде полиномиально разрешима, но предложенный детерминированный тест Агравала — Каяла — Саксены имеет довольно большую вычислительную сложность, что затрудняет его практическое применение.
Для некоторых классов чисел существуют специализированные эффективные тесты простоты (см. ниже).
Бесконечность множества простых чисел
Простых чисел бесконечно много. Самое старое известное доказательство этого факта было дано Евклидом в «Началах» (книга IX, утверждение 20). Его доказательство может быть кратко воспроизведено так:
Представим, что количество простых чисел конечно. Перемножим их и прибавим единицу. Полученное число не делится ни на одно из конечного набора простых чисел, потому что остаток от деления на любое из них даёт единицу. Значит, число должно делиться на некоторое простое число, не включённое в этот набор. Противоречие.
Математики предлагали другие доказательства. Одно из них (приведённое Эйлером) показывает, что сумма величин, обратных к первым n простым числам, неограниченно растёт с ростом n.
Теорема о распределении простых чисел утверждает, что количество простых чисел меньших n, обозначаемое , растёт как .
Наибольшее известное простое
Наибольшим известным простым числом по состоянию на февраль 2011 года является . Оно содержит 12 978 189 десятичных цифр и является простым числом Мерсенна (M43112609). Его нашли 23 августа 2008 года на математическом факультете университета UCLA в рамках проекта по распределённому поиску простых чисел Мерсенна GIMPS.
Числа Мерсенна выгодно отличаются от остальных наличием эффективного теста простоты: теста Люка — Лемера. Благодаря ему простые числа Мерсенна давно удерживают рекорд как самые большие известные простые.
За нахождение простых чисел из более чем 100 000 000 и 1 000 000 000 десятичных цифр EFF назначила [2] денежные призы соответственно в 150 000 и 250 000 долларов США. Ранее EFF уже присуждала призы за нахождение простых чисел из 1 000 000 и 10 000 000 десятичных цифр.
Простые числа специального вида
Существует ряд чисел, простота которых может быть установлена эффективно с использованием специализированных алгоритмов.
С использованием теста Бриллхарта-Лемера-Селфриджа (англ.) может быть проверена простота следующих чисел:
Для поиска простых чисел обозначенных типов в настоящее время используются проекты распределенных вычислений GIMPS, PrimeGrid, Ramsey@Home, Seventeen or Bust, Riesel Sieve, Wieferich@Home.
Некоторые свойства
содержащий 26 переменных и имеющий степень 25. Наименьшая степень для известных многочленов такого типа — 5 при 42 переменных; наименьшее число переменных — 10 при степени около 15905. [6] Этот результат является частным случаем доказанной Юрием Матиясевичем диофантовости любого перечислимого множества.
Открытые вопросы
До сих пор существует много открытых вопросов относительно простых чисел, наиболее известные из которых были перечислены Эдмундом Ландау на Пятом Международном математическом конгрессе [7] :
Открытой проблемой является также существование бесконечного количества простых чисел во многих целочисленных последовательностях, включая числа Фибоначчи, числа Ферма и т. д.
Приложения
Большие простые числа (порядка ) используются в криптографии с открытым ключом. Простые числа также используются в хеш-таблицах и для генерации псевдослучайных чисел (в частности, в ГПСЧ вихрь Мерсенна).
Простые числа — это натуральные числа, больше единицы, которые делятся без остатка только на 1 и на само себя. Например: 2, 3, 5, 7, 11, 13, 17, 19, 23. Единица не является ни простым числом, ни составным.
Последовательность простых чисел начинается с 2 и является бесконечной; наименьшее простое число — это 2 (делится на 1 и на самого себя).
Составные числа — это натуральные числа, у которых есть больше двух делителей (1, оно само и например, 2 и/или 3); это противоположность простым числам. Например: 4, 6, 9, 12 (все делятся на 2, на 3, на 1 и на само себя).
Все натуральные числа считаются либо простыми, либо составными (кроме 1).
Натуральные числа — это те числа, которые возникли натуральным образом при счёте предметов; например: 1, 2, 3, 4. (нет ни дробей, ни 0, ни чисел ниже 0).
Зачастую множество простых чисел в математике обозначается буквой P.
Простые числа до 1000
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
101
103
107
109
113
127
131
137
139
149
Как определить, является ли число простым?
Очень простой способ понять, является ли число простым — нужно его разделить на простые числа и посмотреть, получится ли целое число. Сначала нужно попробовать его разделить на 2 и/или на 3. Если получилось целое число, то оно не является простым.
Если после первого деления не получилось целого числа, значит нужно попробовать разделить его на другие простые числа: 5, 7, 11 и т. д. (на 9 делить не нужно, т. к. это не простое число и оно делится на 3, а на него вы уже делили).
Более структурированный метод — это решето Эратосфена.
Решето Эратосфена
Это алгоритм поиска простых чисел. Для этого нужно:
Те числа, которые не будут вычеркнуты в конце этого процесса, являются простыми.
Взаимно простые числа
Это натуральные числа, у которых 1 — это единственный общий делитель. Например:
Число Мерсенна
Простое число Мерсенна — это простое число вида:
До 1536 г. многие считали, что числа такого вида были все простыми, пока математик Ульрих Ригер не доказал, что 2 (^11) – 1 = 2047 было составным (23 x 89). Затем появились и другие составные числа (p = 23, 29, 31, 37 и др.).
Например, для p = 23 это 2 (^23) – 1 = 8 388 607; И 47 x 178481 = 8 388 607, значит оно составное.
Почему 1 не является простым числом?
Российские математики Боревич и Шафаревич в своей знаменитой работе «Теория чисел» (1964 г.) определяют простое число как p (элемент кольца D), не равен ни 0, ни 1. И p можно называть простым числом, если его невозможно разложить на множители ab (т.е. p = ab), притом ни один из них не является единицей в D. Так как 1 невозможно представить ни в одном, ни в другом виде, 1 не считается ни простым числом, ни составным.
Почему 4 не является простым числом?
Простое число — это натуральное число, больше единицы, которое делится без остатка на 1 и на само себя. Т. к. 4 можно разделить на 1, на 2 и на 4, из-за деления на 2 оно не является простым.
Самое большое простое число
21 декабря 2018 года Great Internet Mersenne Prime Search (проект, целью которого является открытие новых простых чисел Мерсенна) обнаружил новое самое большое известное простое число:
Новое простое число также именуется M82589933 и в нём более чем на полтора миллиона цифр больше, чем в предыдущем (найденном годом ранее).
Просто́е число́ — это натуральное число, больше единицы, имеющее ровно два натуральных делителя: 1 и само себя. Изучением свойств простых чисел занимается теория чисел.
Последовательность простых чисел начинается с
Натуральное число, имеющее больше двух делителей, называется составным. Таким образом, все натуральные числа, за исключением единицы, разбиваются на простые и составные.
Разложение натуральных чисел в произведение простых
Основная теорема арифметики утверждает, что каждое натуральное число, больше единицы (1), представимо в виде произведения простых чисел, причём единственным способом (с точностью до порядка следования сомножителей). Таким образом, простые числа — «элементарные строительные блоки» натуральных чисел.
Представление натурального числа в виде произведения простых называется разложением на простые или факторизацией числа. На настоящий момент неизвестно полиномиальных алгоритмов факторизации чисел, хотя и не доказано, что таких алгоритмов не существует. (Здесь и далее речь идёт о полиномиальной зависимости времени работы алгоритма от логарифма проверяемого числа, то есть от количества его цифр). На алгоритмической сложности задачи факторизации базируется криптосис
af:Priemgetal ang:Frumtæl ar:عدد أولي be-x-old:Просты лік bg:Просто число bn:মৌলিক সংখ্যা br:Niveroù kentael ca:Nombre primer cs:Prvočíslo cy:Rhif cysefin da:Primtal el:Πρώτος αριθμός eo:Primo et:Algarv eu:Zenbaki lehen fa:اعداد اول gl:Número primo he:מספר ראשוני hr:Prost broj ht:Nonm premyé hu:Prímszámok id:Bilangan prima is:Frumtala ka:მარტივი რიცხვი la:Numerus primus lb:Primzuel lmo:Nümar primm lt:Pirminis skaičius lv:Pirmskaitlis nds:Primtall nl:Priemgetal nn:Primtal no:Primtall pl:Liczby pierwsze scn:Nùmmuru primu simple:Prime number sk:Prvočíslo sl:Praštevilo sr:Прост број sv:Primtal ta:பகா எண் th:จำนวนเฉพาะ uk:Просте число ur:مفرد عدد vi:Số nguyên tố vls:Priemgetal yi:פרימצאל yo:Nọ́mbà àkọ́kọ́ zh-min-nan:Sò͘-sò͘
Красивые аномалии встречаются в каждом предмете, но если есть одна область красоты, с которой согласится большинство математиков, то это простое число.
Эти числа занимают уникальный пьедестал в математике, особенно в области теории чисел. Великие умы потратили бесчисленные часы для расследования этой проблемы, в том числе такие великие умы, как Пол Эрдос, Г.Х. Харди и Сриниваса Рамануджан, и это лишь некоторые из них. Теперь, прежде чем мы углубимся в различные алгоритмы, чтобы найти простые числа, давайте сначала установим предварительное понимание простых чисел.
Что такое простые числа?
Самое техническое определение простых чисел состоит в том, что это натуральное число больше 1 и может быть получено только путем умножения 1 и самого себя. Если бы понимание натуральных чисел было более интуитивным, то можно было бы сказать, что это числа, которые мы используем для подсчета.
Метод Марена Мерсенна
Марен Мерсенн Французский математик
Однако, с появлением компьютеров, они теперь могли выполнять эти вычислительные вычисления, которые раньше делались людьми самым кропотливым и трудоемким образом. Мы определенно достигли более высоких простых чисел Мерсенна и простых чисел на общем уровне. Поиск простых чисел так же активен, как и другие численные поиски, выполняемые компьютерами. Другой числовой поиск, аналогичный движению простых чисел, заключается в добавлении десятичных разрядов к некоторым иррациональным числам, таким как пи (отношение длины окружности к диаметру). Однако непрерывный поиск следующего по величине простого числа существенно сложнее, чем поиск следующей цифры числа Пи.
Даже самые большие компьютеры (суперкомпьютеры) тратят значительное количество времени, чтобы проверить, является ли новое число (которое обычно ошеломляюще огромным) само по себе простым числом, и требуется еще больше времени, чтобы проверить, является ли число основным числом Мерсенна. По этой причине числа Мерсенна представляют большой интерес в области кибербезопасности и криптографии, особенно в отношении шифрования.
В августе 2008 года системный администратор UCLA Эдсон Смит нашел наиболее значимое простое число, известное на тот момент. Смит установил программное обеспечение для Great Internet Mersenne Prime Search (Gimps), проекта распределенных вычислений на добровольной основе. Это число было простым числом Мерсенна длиной 12 978 189 цифр. Чтобы дать представление о том, насколько он велик, на его написание уйдет почти два с половиной месяца, а в случае печати он растянется на 50 км!
Метод простых чисел Ферма
Пьер де Ферма (фр. Pierre de Fermat, 17 августа 1601 — 12 января 1665) — французский математик-самоучка, один из создателей аналитической геометрии, математического анализа, теории вероятностей и теории чисел.
Когда n = 0, m = 2 0 = 1; поэтому F0 = 2 1 + 1 = 2 + 1 = 3, что является простым. Когда n = 1, m = 2 1 = 2; поэтому F1 = 2 2 + 1 = 4 + 1 = 5, что является простым. Когда n = 2, m = 2 2 = 4; следовательно, F2 = 2 4 + 1 = 16 + 1 = 17, что является простым. Когда n = 3, m = 2 3 = 8; следовательно, F3 = 2 8 + 1 = 256 + 1 = 257, что является простым. Когда n = 4, m = 2 4 = 16; следовательно, F4 = 2 16 + 1 = 65536 + 1 = 65537, что является простым числом. Теперь, как вы можете заметить, к тому времени, когда мы достигнем F5, значение достигает 4 294 967 297.
На сегодняшний день мы достигли только F11, даже со всеми лучшими компьютерами и параллельными вычислениями и большой точностью. В конце концов, однако, мы можем сказать, что поиск простых чисел всегда будет идти до бесконечности и дальше!
, растёт как 
.
. Оно содержит 12 978 189 десятичных цифр и является простым числом Мерсенна (M43112609). Его нашли 23 августа 2008 года на математическом факультете университета UCLA в рамках проекта по распределённому поиску простых чисел Мерсенна GIMPS.
) используются в криптографии с открытым ключом. Простые числа также используются в хеш-таблицах и для генерации псевдослучайных чисел (в частности, в ГПСЧ вихрь Мерсенна).
