Какие бывают простые числа. Как найти простые числа

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

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

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

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

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

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

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

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

Все натуральные числа, кроме единицы подразделяются на простые и составные. Простое число - это натуральное число, которое имеет только два делителя: единицу и само себя . Все остальные называются составными. Исследованием свойств простых чисел занимается специальный раздел математики - теория чисел. В теории колец простые числа соотносят с неприводимыми элементами.

Приведем последовательность простых чисел начиная с 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, ... и т.д.

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

Такое представление натурального числа называется разложением натурального числа на простые числа или факторизацией числа.

Одним из самых древних и эффективных способов вычисления простых чисел является «решето Эрастофена».

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

Кстати сказать, что для некоторых классов чисел существуют специализированные эффективные тесты простоты. К примеру, для проверки чисел Мерсенна на простоту применяют тест Люка-Лемера, а для проверки на простоту чисел Ферма - тест Пепина.

Все мы знаем, что чисел бесконечно много. Справедливо возникает вопрос: сколько же тогда существует простых чисел? Простых чисел также бесконечное количество. Наиболее древним доказательством этого суждения является доказательство Евклида, которое изложено в «Началах». Доказательство Евклида имеет следующий вид:

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

Теорема распределения простых чисел утверждает, что количество простых чисел меньших n, обозначаемое π(n), растёт как n / ln(n).

За тысячи лет исследования простых чисел, было выявлено, что наибольшим известным простым числом является 243112609 − 1. Это число включает 12 978 189 десятичных цифр и является простым числом Мерсенна (M43112609). Это открытие было сделано 23 августа 2008 года на математическом факультете университета uCLA в рамках проекта по распределённому поиску простых чисел Мерсенна GIMPS.

Главной отличительной особенностью чисел Мерсенна является наличие высоко эффективного теста простоты Люка - Лемера. С его помощью простые числа Мерсенна на протяжении длительного периода времени являются самыми большими из известных простых чисел.

Однако по сей день многие вопросы относительно простых чисел не получили точных ответов. На 5-м Международном математическом конгрессе Эдмунд Ландау сформулировал основным проблемы в области простых чисел:

Проблема Гольдбаха или первая проблема Ландау заключается в том, что необходимо доказать или опровергнуть, что каждое чётное число, большее двух, может быть представлено в виде суммы двух простых чисел, а каждое нечётное число, большее 5, может быть представлено в виде суммы трёх простых чисел.
Вторая проблема Ландау требует найти ответ на вопрос: бесконечно ли множество «простых близнецов» - простых чисел, разность между которыми равна 2?
Гипотеза Лежандра или третья проблема Ландау такова: верно ли, что между n2 и (n + 1)2 всегда найдётся простое число?
Четвёртая проблема Ландау: бесконечно ли множество простых чисел вида n2 + 1?
Помимо вышеперечисленных проблем существует проблема определения бесконечного количества простых чисел во многих целочисленных последовательностях типа числа Фибоначчи, числа Ферма и т. д.

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

Функция floor(x) округляет число x до ближайшего целого числа, которое меньше или равно x.

Узнайте о модульной арифметике. Операция "x mod y" (mod является сокращением латинского слова "modulo", то есть “модуль”) означает "поделить x на y и найти остаток". Иными словами, в модульной арифметике по достижении определенной величины, которую называют модулем , числа вновь "превращаются" в ноль. Например, часы отсчитывают время с модулем 12: они показывают 10, 11 и 12 часов, а затем возвращаются к 1.

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

Узнайте о подводных камнях малой теоремы Ферма. Все числа, для которых не выполняются условия теста, являются составными, однако остальные числа лишь вероятно относятся к простым. Если вы хотите избежать неверных результатов, поищите n в списке "чисел Кармайкла" (составных чисел, которые удовлетворяют данному тесту) и "псевдопростых чисел Ферма" (эти числа соответствуют условиям теста лишь при некоторых значениях a ).

Если удобно, используйте тест Миллера-Рабина. Хотя данный метод довольно громоздок при вычислениях вручную, он часто используется в компьютерных программах. Он обеспечивает приемлемую скорость и дает меньше ошибок, чем метод Ферма. Составное число не будет принято за простое, если провести расчеты для более ¼ значений a . Если вы случайным способом выберете различные значения a и для всех них тест даст положительный результат, можно с достаточно высокой долей уверенности считать, что n является простым числом.

Для больших чисел используйте модульную арифметику. Если у вас под рукой нет калькулятора с функцией mod или калькулятор не рассчитан на операции с такими большими числами, используйте свойства степеней и модульную арифметику, чтобы облегчить вычисления. Ниже приведен пример для 3 50 {\displaystyle 3^{50}} mod 50:

Перепишите выражение в более удобном виде: mod 50. При расчетах вручную могут понадобиться дальнейшие упрощения.
(3 25 ∗ 3 25) {\displaystyle (3^{25}*3^{25})} mod 50 = mod 50 mod 50) mod 50. Здесь мы учли свойство модульного умножения.
3 25 {\displaystyle 3^{25}} mod 50 = 43.
(3 25 {\displaystyle (3^{25}} mod 50 ∗ 3 25 {\displaystyle *3^{25}} mod 50) mod 50 = (43 ∗ 43) {\displaystyle (43*43)} mod 50.
= 1849 {\displaystyle =1849} mod 50.
= 49 {\displaystyle =49} .

Перевод

Свойства простых чисел впервые начали изучать математики Древней Греции. Математики пифагорейской школы (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 «Начал» Эвклид доказал, что простых чисел бесконечное количество. Это, кстати, один из первых примеров использования доказательства от противного. Также он доказывает Основную теорему арифметики – каждое целое число можно представить единственным образом в виде произведения простых чисел.

Также он показал, что если число 2 n -1 является простым, то число 2 n-1 * (2 n -1) будет совершенным. Другой математик, Эйлер, в 1747 году сумел показать, что все чётные совершенные числа можно записать в таком виде. По сей день неизвестно, существуют ли нечётные совершенные числа.

В году 200 году до н.э. грек Эратосфен придумал алгоритм для поиска простых чисел под названием «Решето Эратосфена».

А затем случился большой перерыв в истории исследования простых чисел, связанный со Средними веками.

Следующие открытия были сделаны уже в начале 17-го века математиком Ферма. Он доказал гипотезу Альбера Жирара, что любое простое число вида 4n+1 можно записать уникальным образом в виде суммы двух квадратов, и также сформулировал теорему о том, что любое число можно представить в виде суммы четырёх квадратов.

Он разработал новый метод факторизации больших чисел, и продемонстрировал его на числе 2027651281 = 44021 × 46061. Также он доказал Малую теорему Ферма: если p – простое число, то для любого целого a будет верно a p = a modulo p.

Это утверждение доказывает половину того, что было известно как «китайская гипотеза», и датируется 2000 годами ранее: целое n является простым тогда и только тогда, если 2 n -2 делится на n. Вторая часть гипотезы оказалась ложной – к примеру, 2 341 - 2 делится на 341, хотя число 341 составное: 341 = 31 × 11.

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

Ферма много переписывался со своими современниками, в особенности с монахом по имени Марен Мерсенн. В одном из писем он высказал гипотезу о том, что числа вида 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 году.

Многие годы числа такого вида давали математикам наибольшие известные простые числа. Что число M 19 , было доказано Катальди в 1588 году, и в течение 200 лет было наибольшим известным простым числом, пока Эйлер не доказал, что M 31 также простое. Этот рекорд продержался ещё сто лет, а затем Люкас показал, что M 127 - простое (а это уже число из 39 цифр), и после него исследования продолжились уже с появлением компьютеров.

В 1952 была доказана простота чисел M 521 , M 607 , M 1279 , M 2203 и M 2281 .

К 2005 году найдено 42 простых чисел Мерсенна. Наибольшее из них, M 25964951 , состоит из 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, как

π(n) = n/(log(n) - 1.08366)

А Гаусс – как логарифмический интеграл

π(n) = ∫ 1/log(t) dt

С промежутком интегрирования от 2 до n.

Утверждение о плотности простых чисел 1/log(n) известно как Теорема о распределении простых чисел. Её пытались доказать в течение всего 19 века, а прогресса достигли Чебышёв и Риман. Они связали её с гипотезой Римана – по сию пору не доказанной гипотезой о распределении нулей дзета-функции Римана. Плотность простых чисел была одновременно доказана Адамаром и Валле-Пуссеном в 1896 году.

В теории простых чисел есть ещё множество нерешённых вопросов, некоторым из которых уже многие сотни лет:

гипотеза о простых числах-близнецах – о бесконечном количестве пар простых чисел, отличающихся друг от друга на 2
гипотеза Гольдбаха: любое чётное число, начиная с 4, можно представить в виде суммы двух простых чисел
бесконечно ли количество простых чисел вида n 2 + 1 ?
всегда ли можно найти простое число между n 2 and (n + 1) 2 ? (факт, что между n и 2n всегда есть простое число, было доказан Чебышёвым)
бесконечно ли число простых чисел Ферма? есть ли вообще простые числа Ферма после 4-го?
существует ли арифметическая прогрессия из последовательных простых чисел для любой заданной длины? например, для длины 4: 251, 257, 263, 269. Максимальная из найденных длина равна 26 .
бесконечно ли число наборов из трёх последовательных простых чисел в арифметической прогрессии?
n 2 - n + 41 – простое число для 0 ≤ n ≤ 40. Бесконечно ли количество таких простых чисел? Тот же вопрос для формулы n 2 - 79 n + 1601. Эти числа простые для 0 ≤ n ≤ 79.
бесконечно ли количество простых чисел вида n# + 1? (n# - результат перемножения всех простых чисел, меньших n)
бесконечно ли количество простых чисел вида n# -1 ?
бесконечно ли количество простых чисел вида n! + 1?
бесконечно ли количество простых чисел вида n! – 1?
если p – простое, всегда ли 2 p -1 не содержит среди множителей квадратов простых чисел
содержит ли последовательность Фибоначчи бесконечное количество простых чисел?

Самые большие близнецы среди простых чисел – это 2003663613 × 2 195000 ± 1. Они состоят из 58711 цифр, и были найдены в 2007 году.

Самое большое факториальное простое число (вида n! ± 1) – это 147855! - 1. Оно состоит из 142891 цифр и было найдено в 2002.

Наибольшее праймориальное простое число (число вида n# ± 1) – это 1098133# + 1.

Перевод