Как математически найти простое число

Была ли эта статья полезной?

Просто́е число́ — натуральное число, имеющее ровно два различных натуральных делителя. Другими словами, натуральное число является простым, если оно отлично от и делится без остатка только на и на само ^[1].

Пример: число простое (делится на и на ), а не является простым, так как, помимо и , делится на  — имеет три натуральных делителя.

Изучением свойств простых чисел занимается теория чисел, а основная теорема арифметики устанавливает в ней их центральную роль: любое целое число, превышающее , либо является простым, либо может быть выражено произведением простых чисел, причём такое представление однозначно с точностью до порядка сомножителей^[1]. Единицу не относят к простым числам, так как иначе указанное разложение становится неоднозначным^[2]: .

Натуральные числа можно разделить на три класса: единица (имеет один натуральный делитель), простое число (имеет два натуральных делителя), составное число (имеет более двух натуральных делителей)^[1]. Как простых, так и составных чисел бесконечно много.

Последовательность простых чисел начинается так:

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, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, …^[3]

Существуют различные алгоритмы проверки числа на простоту. Например, известный метод перебора делителей в сравнении с другими примитивный и медленный.

Простые числа широко используются в математике и смежных науках. Во многих алгоритмах информационных технологий, например в асимметричных криптосистемах, используются свойства факторизации целых чисел^[4].

Многие проблемы, касающиеся простых чисел, остаются открытыми.

Существуют обобщения понятия простого числа для произвольных колец и других алгебраических структур.

История[править | править код]

Неизвестно, когда было определено понятие простого числа, однако первые свидетельства относят к верхнему палеолиту, что подтверждается костью Ишанго^[5].

В сохранившихся записях древнеегипетских математиков есть намёки на то, что у них были некоторые представления о простых числах: например, папирус Райнда, относящийся ко второму тысячелетию до нашей эры, содержит таблицу соотношений числа 2 к , представленных суммой трёх или четырёх египетских дробей с единицей в числителе и различных знаменателях. Разложения дробей, знаменатели которых имеют общий делитель, похожи, поэтому египтяне по крайней мере знали разницу между простым и составным числами^[6].

Самые ранние дошедшие до нас исследования простых чисел принадлежат математикам Древней Греции. Они изобрели решето Эратосфена — алгоритм последовательного нахождения всех простых чисел от 1 до . Опубликованные в приблизительно трёхсотом году до нашей эры «Начала» Евклида содержат важные теоремы о простых числах, включая бесконечность их множества, лемму Евклида и основную теорему арифметики^[7].

Вплоть до XVII века существенных новых работ в области простых чисел не было^[8]. В 1640 году Пьер де Ферма сформулировал малую теорему Ферма, затем доказанную Лейбницем и Эйлером, и теорему о сумме двух квадратов, а также высказал предположение: все числа вида  являются простыми, и даже доказал это до . Но уже для следующего числа Ферма Эйлер доказал делимость на . Новые простые числа в последовательности Ферма не найдены до сих пор. В то же время французский монах Марен Мерсенн обнаружил, что последовательность , где  — простое, даёт также простое число^[9] (числа Мерсенна).

Работа Эйлера в теории чисел вместила немало сведений о простых. Он показал, что бесконечный числовой ряд  — расходящийся. В 1747 году он доказал, что чётные совершенные числа являются значениями последовательности , где сомножитель является числом Мерсенна. В его переписке с Гольдбахом последний изложил свою знаменитую гипотезу о представлении любого чётного числа, начиная с четырёх, суммой двух простых^[10]. Доказательство гипотезы пока не найдено.

С начала XIX века внимание многих математиков занимала проблема асимптотического распределения простых чисел^[10]. Лежандр и Гаусс независимо друг от друга высказали предположение: плотность простых чисел в среднем близка к величине, обратно пропорциональной натуральному логарифму^[11].

Долгое время простые числа считались малоприменимыми за пределами чистой математики. Ситуация изменилась в 1970-е годы, после появления концепций криптографии с открытым ключом, в которых простые числа составили основу первых алгоритмов шифрования, таких как RSA^[12].

Разложение натуральных чисел в произведение простых[править | править код]

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

Основная теорема арифметики[править | править код]

Основная теорема арифметики утверждает, что каждое натуральное число, большее единицы, представимо в виде произведения простых чисел, причём единственным способом с точностью до порядка следования сомножителей^[14]. Таким образом, простые числа являются элементарными «строительными блоками» натуральных чисел. Например:

Как было показано в этом примере, один и тот же простой делитель может появляться несколько раз. Разложение:

n = p₁ · p₂ · … · p_t

числа n на (конечное число) простых множителей p₁, p₂, … ,p_t называется разложением на простые множители числа n. Основная теорема арифметики может быть перефразирована таким образом: любое разложение на простые числа будет тождественным с точностью до порядка делителей. На практике для большинства чисел есть много простых алгоритмов разложения на множители, все они дают один и тот же результат^[13].

Простота единицы[править | править код]

Большинство древних греков даже не считало числом, поэтому они не могли считать его простым^[15]. К Средним векам и эпохе Возрождения многие математики включали в качестве первого простого числа^[16]. В середине XVIII века Христиан Гольдбах внёс в список в качестве первого простого числа в своей знаменитой переписке с Леонардом Эйлером; однако сам Эйлер не считал простым числом^[17]. В XIX веке многие математики по-прежнему считали число простым числом. Например, список простых чисел Деррика Нормана Лемера до числа, переизданный в 1956 году, начинался с в качестве первого простого числа. Говорят, что Анри Лебег является последним математиком, который назвал простым^[18]. К началу XX века математики стали приходить к консенсусу о том, что не является простым числом, а скорее формирует свою специальную категорию — «единицу»^[16].

Если считать простым числом, то основная теорема Евклида об арифметике (упомянутая выше) не будет выполняться, как было указано в начале статьи. Например, число может быть разложено как 3 · 5 и 1 · 3 · 5. Если бы являлась простым числом, эти два варианта считались бы разными факторизациями ; следовательно, утверждение этой теоремы пришлось бы изменить^[16]. Точно так же решето Эратосфена работало бы неправильно, если бы считалась простым: модифицированная версия решета, которая предполагает, что является простым числом, исключает все множители, кратные (то есть все остальные числа), и даёт на выходе только одно число — . Кроме того, простые числа имеют несколько свойств, которых нет у числа , такие как отношение числа к его соответствующему значению функции тождества Эйлера или суммы функции делителей^[2].

Алгоритмы поиска и распознавания простых чисел[править | править код]

Простые способы нахождения начального списка простых чисел вплоть до некоторого значения дают решето Эратосфена, решето Сундарама и решето Аткина^[19].

Однако, на практике вместо получения списка простых чисел зачастую требуется проверить, является ли данное число простым. Алгоритмы, решающие эту задачу, называются тестами простоты. Существует множество полиномиальных тестов простоты, но большинство их являются вероятностными (например, тест Миллера — Рабина) и используются для нужд криптографии^[20]. В 2002 году было доказано, что задача проверки на простоту в общем виде полиномиально разрешима, но предложенный детерминированный тест Агравала — Каяла — Саксены имеет довольно большую вычислительную сложность, что затрудняет его практическое применение^[21].

Для некоторых классов чисел существуют специализированные эффективные тесты простоты (см. ниже).

Тест простоты[править | править код]

Тестом простоты (или проверкой простоты) называется алгоритм, который, приняв на входе число, позволяет либо не подтвердить предположение о составности числа, либо точно утверждать его простоту. Во втором случае он называется истинным тестом простоты. Задача теста простоты относится к классу сложности P, то есть время работы алгоритмов её решения зависит от размера входных данных полиномиально, что было доказано в 2002 году^[22]. Появление полиномиального алгоритма предсказывалось существованием полиномиальных сертификатов простоты и, как следствие, тем, что задача проверки числа на простоту принадлежала классам NP и co-NP одновременно.

Существующие алгоритмы проверки числа на простоту могут быть разделены на две категории: истинные тесты простоты и вероятностные тесты простоты. Результатом вычислений истинных тестов всегда является факт простоты либо составности числа. Вероятностный тест показывает, является ли число простым с некоторой вероятностью. Числа, удовлетворяющие вероятностному тесту простоты, но являющиеся составными, называются псевдопростыми^[23]. Одним из примеров таких чисел являются числа Кармайкла^[24].

Одним из примеров истинных тестов простоты является тест Люка-Лемера для чисел Мерсенна. Очевидный недостаток этого теста заключается в его применимости только к числам определённого вида. Среди других примеров можно привести основанные на малой теореме Ферма^[25]

• Тест Пепина для чисел Ферма
• Теорема Прота для чисел Прота
• Тест Агравала — Каяла — Саксены, первый универсальный, полиномиальный, детерминированный и безусловный тест простоты.
• Тест Люка — Лемера — Ризеля

А также:

• метод перебора делителей
• Теорема Вильсона
• Критерий Поклингтона
• Тест Миллера
• Тест Адлемана — Померанса — Румели, усовершенствованный^[26] Коэном и Ленстрой
• Тест простоты с использованием эллиптических кривых.

К вероятностным тестам простоты относят:

• Тест Ферма
• Тест Миллера — Рабина
• Тест Соловея — Штрассена
• Тест Бейли — Померанца — Селфриджа — Уогстаффа

Большие простые числа[править | править код]

Уже в течение многих столетий поиск «больших» простых чисел вызывает интерес математиков. В последние десятилетия эти исследования приобрели прикладное значение из-за применения таких чисел в ряде алгоритмов шифрования, таких как RSA^[12].

В семнадцатом столетии Марен Мерсенн предположил, что числа вида простые (при n ≤ 257) только для n равных 2, 3, 5, 7, 13, 17, 19, 31, 67, 127 и 257^[11]. Проверка верности предположения была намного выше возможностей того времени. Только в XX веке было обнаружено, что гипотеза была ложной и, вероятно, сделана «слепо», поскольку Мерсенн не учел три случая (для n = 61, 89 и 107); кроме того, оказалось, что числа, соответствующие n = 67 и n = 257 — составные^[11].

В 1876 году Эдуард Люка доказал, что число M ₁₂₇ (39-значное число) — простое, оно оставалось самым большим известным простым числом до 1951 года, когда были найдены (44 цифры) и, немного позднее, (из 79 цифр) — последнее простое число, которое было найдено с помощью электронного калькулятора. С тех пор все последующие большие простые числа были обнаружены с помощью компьютера: с 1952 года (когда SWAC показал, что M ₅₂₁ является простым), по 1996 год они были найдены суперкомпьютером, и все были простыми Мерсенна (найденные с использованием теста Люка-Лемера, специфического алгоритма для таких чисел), за исключением числа , которое было рекордом между 1989 и 1992 годами^[27].

Алгоритмы получения простых чисел[править | править код]

Некоторые задачи математики с использованием факторизации требуют ряд очень больших простых чисел, выбранных случайным образом. Алгоритм их получения, основанный на постулате Бертрана (Для любого натурального n ≥ 2 найдётся простое число p в интервале n < p < 2n.)^[28]:

Время решения задачи этим алгоритмом не определено, но есть большая вероятность, что оно всегда является полиномиальным, пока имеется достаточно простых чисел, и они распределены более-менее равномерно. Для простых случайных чисел эти условия выполняются^[21].

Наиболее эффективным средством построения простых чисел является несколько модифицированная малая теорема Ферма^[26].

Пусть N, S — нечётные натуральные числа, N-1 = S*R, причем для каждого простого делителя q числа S существует целое число такое, что

,

Тогда каждый простой делитель p числа N удовлетворяет сравнению

Следствие. Если выполнены условия теоремы Ферма и , то N — простое число^[26].

Покажем теперь, как с помощью последнего утверждения, имея большое простое число , можно построить существенно большее простое число . Выберем для этого случайным образом чётное число на промежутке и положим . Затем проверим число на отсутствие малых простых делителей, разделив его на малые простые числа; испытаем некоторое количество раз с помощью алгоритма Рабина. Если при этом выяснится, что  — составное число, следует выбрать новое значение и опять повторить вычисления. Так следует делать до тех пор, пока не будет найдено число N, выдержавшее испытание алгоритмом Рабина достаточно много раз. В этом случае появляется надежда на то, что  — простое число, и следует попытаться доказать простоту с помощью тестов простоты^[26].

Бесконечность множества простых чисел[править | править код]

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

Наибольшее известное простое[править | править код]

Издавна ведутся записи, отмечающие наибольшие известные на то время простые числа^[30]. Один из рекордов поставил в своё время Эйлер, найдя простое число 2³¹ − 1 = 2 147 483 647.

Наибольшим известным простым числом по состоянию на январь 2019 года является число Мерсенна M_82 589 933 = 2^82 589 933 − 1. Оно содержит 24 862 048 десятичных цифр; в книге с записью этого числа было бы около девяти тысяч страниц. Его нашли 7 декабря 2018 года в рамках проекта по распределённому поиску простых чисел Мерсенна GIMPS. Предыдущее самое большое известное простое число, открытое в декабре 2017 года, было на 1 612 623 знака меньше^[31].

Числа Мерсенна выгодно отличаются от остальных наличием эффективного теста простоты: теста Люка — Лемера. Благодаря ему простые числа Мерсенна давно удерживают рекорд как самые большие известные простые.

За нахождение простых чисел из более чем 100 000 000 и 1 000 000 000 десятичных цифр EFF назначила^[32] денежные призы соответственно в 150 000 и 250 000 долларов США^[33]. Ранее EFF уже присуждала призы за нахождение простых чисел из 1 000 000 и 10 000 000 десятичных цифр.

Простые числа специального вида[править | править код]

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

• Числа Мерсенна — числа вида , где n — натуральное число^[34]. При этом число Мерсенна может быть простым, только если n — простое число. Как уже было отмечено выше, эффективным тестом простоты является тест Люка — Лемера^[35].
• Числа Ферма — числа вида , где n — неотрицательное целое число^[36]. Эффективным тестом простоты является тест Пепина. По состоянию на февраль 2015 года известно только 5 простых чисел Ферма (для n = 0, 1, 2, 3, 4), двадцать восемь следующих чисел Ферма (до включительно) оказались составными^[37], однако не доказано, что других простых чисел Ферма нет^[38].
• Числа Вудала — числа вида ^[39]. Эффективным тестом простоты является тест Люка — Лемера — Ризеля^[40].
• Числа Каллена — числа вида ^[41][42].
• Числа Прота — числа вида , причём k нечётно и ^[43]. Эффективным тестом простоты для чисел Прота является тест Бриллхарта — Лемера — Селфриджа (англ. Brillhart–Lehmer–Selfridge test)^[44]. Числа Каллена и числа Ферма являются частным случаем чисел Прота (соответственно при k = n и при k = 1, )^[45].
• Числа Миллса — числа вида где  — константа Миллса^[46].

Для поиска простых чисел обозначенных типов в настоящее время используются проекты распределённых вычислений GIMPS, PrimeGrid, Ramsey@Home, Seventeen or Bust, Riesel Sieve, Wieferich@Home.

Некоторые свойства[править | править код]

• Если p — простое, и p делит ab, то p делит a или b. Доказательство этого факта было дано Евклидом и известно как лемма Евклида^[7][47]. Она используется в доказательстве основной теоремы арифметики.
• Кольцо вычетов является полем тогда и только тогда, когда  — простое^[48].
• Характеристика каждого поля — это ноль или простое число^[48].
• Если  — простое, а  — натуральное, то делится на (малая теорема Ферма)^[49].
• Если  — конечная группа, порядок которой делится на , то содержит элемент порядка (теорема Коши)^[50].
• Если  — конечная группа, и  — максимальная степень , которая делит , то имеет подгруппу порядка , называемую силовской подгруппой, более того, количество силовских подгрупп равно для некоторого целого (теоремы Силова)^[51].
• Натуральное является простым тогда и только тогда, когда делится на (теорема Вильсона)^[52].
• Если  — натуральное, то существует простое , такое, что (постулат Бертрана)^[53].
• Ряд чисел, обратных к простым, расходится^[10]. Более того, при

  

• Любая арифметическая прогрессия вида , где  — целые взаимно простые числа, содержит бесконечно много простых чисел (теорема Дирихле о простых числах в арифметической прогрессии)^[54].
• Всякое простое число, большее 3, представимо в виде или , где  — некоторое натуральное число. Отсюда, если разность между несколькими последовательными простыми числами (при k>1) одинакова, то она обязательно кратна 6 — например: 251-257-263-269; 199-211-223; 20183-20201-20219.
• Если  — простое, то кратно 24 (справедливо также для всех нечётных чисел, не делящихся на 3)^[55].
• Теорема Грина-Тао. Существуют сколь угодно длинные конечные арифметические прогрессии, состоящие из простых чисел^[56].
• Никакое простое число не может иметь вид , где n>2, k>1. Иначе говоря, число, следующее за простым, не может быть квадратом или более высокой степенью с основанием, бо́льшим 2. Из этого следует также, что если простое число имеет вид , то k — простое (см. числа Мерсенна)^[34].
• Никакое простое число не может иметь вид , где n>1, k>0. Иначе говоря, число, предшествующее простому, не может быть кубом или более высокой нечётной степенью с основанием, бо́льшим 1^[57].
• Каждое простое число (кроме чисел вида ) можно представить в виде суммы трех квадратов^[58].

Применения[править | править код]

Простые числа являются фундаментальными компонентами во многих областях математики.

Арифметические функции[править | править код]

Арифметические функции, а именно функции, определённые на множестве натуральных чисел и принимающих значения во множестве комплексных чисел, играют решающую роль в теории чисел. В частности, среди них наиболее важными являются мультипликативные функции, то есть функции , обладающие следующим свойством: если пара состоит из взаимно простых чисел, то имеет место равенство^[59]

Примерами мультипликативных функций являются функция Эйлера , которая ставит в соответствие числу количество натуральных чисел, меньших n и взаимно простых с ним и количество делителей числа n^[60]. Значение этих функций от степени простого числа:

• Функция Эйлера:

• Функция делителя:

Арифметические функции можно легко вычислить, зная значения, которые они принимают для степеней простых чисел^[59]. На самом деле из разложения натурального числа n на множители

мы имеем, что

и следовательно, возвращаясь к задаче вычисления получается что вычислить от каждой степени простого делителя обычно проще, чем вычислить по общей формуле^[61].

Например, чтобы узнать значение функции Эйлера от n = 450 = 2 × 3 ² × 5 ², достаточно вычислить

Модульная арифметика[править | править код]

В модульной арифметике простые числа играют очень важную роль: кольцо вычетов является полем тогда и только тогда, когда n является простым^[48]. Также существование первообразного корня кольца привязано к простым числам: оно существует, только если n — простое число, 1, 2, 4 или число в форме , где p нечётно.

Одной из важнейших теорем модульной арифметики является малая теорема Ферма^[52]. Эта теорема утверждает, что для любого простого числа р и любого натурального числа a имеем:

или для любого простого р и любого натурального а не делящегося на р, справедливо:

Это свойство можно использовать для проверки того, что число не является простым. На самом деле, если n таково, что:

для некоторого натурального а, то n не может быть простым^[52]. Однако это свойство не может быть использовано для проверки числа на простоту: есть некоторые числа, называемые числами Кармайкла (наименьшее — 561) для которых это будет неверно. Числом Кармайкла называется составное число, которое является псевдопростым числом по каждому основанию b, взаимно простому с n. В 1994 году Уильям Роберт Альфорд, Эндрю Гранвиль и Карл Померанс показали, что таких чисел бесконечно много^[62].

Теория групп[править | править код]

Простые числа также играют основополагающую роль в алгебре. В теории групп группа, в которой каждый элемент является степенью простого числа р, называется р-группой^[63]. P-группа является конечной тогда и только тогда, когда порядок группы (число её элементов) является степенью р. Примером бесконечной р-группы является p-группа Прюфера^[64]. Известно, что p-группы имеют нетривиальный центр и, следовательно, не могут быть простыми (кроме группы с p элементами); если группа конечна, более того, все нормальные подгруппы пересекают центр нетривиальным образом.

Примером таких групп является циклическая группа умножения по модулю простого числа^[65].

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

В теореме Коши утверждается, что если порядок конечной группы G делится на простое число p, то G содержит элементы порядка p. Эта теорема обобщается теоремами Силова^[50].

Криптосистема с открытым ключом[править | править код]

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

RSA[править | править код]

Трудность факторизации больших чисел привела к разработке первого эффективного метода криптографии с открытым ключом — RSA^[68]. В этой криптографической системе, человек, который должен получить зашифрованное сообщение, генерирует ключ: выбираются два различных случайных простых числа и заданного размера (обычно используются, 1024- или 2048-битные числа). Далее вычисляется их произведение , называемое модулем. Вычисляется значение функции Эйлера от числа : . Выбирается целое число (), взаимно простое со значением функции . Обычно в качестве берут небольшие простые числа (например, простые числа Ферма). Число называется открытой экспонентой (англ. public exponent). Вычисляется число , называемое секретной экспонентой, мультипликативно обратное к числу e по модулю . Пара публикуется в качестве открытого ключа RSA (англ. RSA public key). Пара играет роль закрытого ключа RSA (англ. RSA private key) и держится в секрете^[12].

Теоретически можно получить закрытый ключ из общедоступной информации: в настоящее время для этого требуется факторизация числа , что делает передачу защищенного сообщения безопасной, если простые числа удовлетворяют определённым условиям и являются «достаточно большими». Пока не известно, существуют ли эффективные методы для расшифровки сообщения, не связанные с прямой атакой на факторизацию , но было показано, что плохой выбор открытого ключа может сделать систему более уязвимой для таких атак^[69].

В 1991 году RSA Security опубликовала список полупростых чисел, предлагая денежные призы за разложение некоторых из них на множители, с целью подтверждения безопасности метода и поощрения исследования в этой области: инициатива называлась Challenge RSA Factoring^[70]. На протяжении многих лет некоторые из этих чисел были разложены, а для других проблема факторизации все ещё остается открытой; однако конкурс был завершен в 2007 году^[70].

Формулы для нахождения простых чисел[править | править код]

В разное время предпринимались попытки указать выражение, значениями которого при разных значениях входящих в него переменных были бы простые числа^[54].
Л. Эйлер указал многочлен принимающий простые значения при n = 0, 1, 2, …, 40. Однако при n = 41 значение многочлена является составным числом. Можно доказать, что не существует многочлена от одной переменной n, который принимает простые значения при всех целых n^[54].
П. Ферма предположил, что все числа вида 2^2k + 1 простые; однако Эйлер опроверг эту гипотезу, доказав, что число 2²⁵ + 1 = 4 294 967 297 — составное^[54].

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

содержащий 26 переменных и имеющий степень 25. Наименьшая степень для известных многочленов такого типа — 5 при 42 переменных; наименьшее число переменных — 10 при степени около 1,6·10^45[71][72]. Этот результат является частным случаем доказанной Юрием Матиясевичем диофантовости любого перечислимого множества.

Интересно, что приведённый выше многочлен, который порождает простые числа, сам разлагается на множители. Заметим, что второй множитель этого многочлена (в фигурных скобках) имеет форму: единица минус сумма квадратов. Таким образом, многочлен может принимать положительные значения (при положительных ) только если, каждый из этих квадратов (то есть каждый многочлен в квадратных скобках) равен нулю. В этом случае выражение в фигурных скобках будет равно 1^[73].

Открытые вопросы[править | править код]

До сих пор существует много открытых вопросов относительно простых чисел, наиболее известные из которых были перечислены Эдмундом Ландау в 1912 году на Пятом Международном математическом конгрессе^[74]:

1. Проблема Гольдбаха (первая проблема Ландау): верно ли, что каждое чётное число, большее двух, может быть представлено в виде суммы двух простых чисел?
2. Вторая проблема Ландау: бесконечно ли множество «простых близнецов» — пар простых чисел, разность между которыми равна 2^[54]? В 2013 году математик Чжан Итан из университета Нью-Гэмпшира^[75][76] доказал, что существует бесконечно большое количество пар простых чисел, расстояние между которыми не превышает 70 миллионов. Позже Джеймс Мэйнард улучшил результат до 600. В 2014 году проект Polymath^[en] под руководством Теренса Тао несколько улучшили последний метод, заменив оценку расстояния на 246.
3. Гипотеза Лежандра (третья проблема Ландау): верно ли, что для всякого натурального числа между и всегда найдётся простое число^[77]?
4. Четвёртая проблема Ландау: бесконечно ли множество простых чисел вида , где  — натуральное число^[54]?

Открытой проблемой является также существование бесконечного количества простых чисел во многих целочисленных последовательностях, включая числа Мерсенна^[54], числа Фибоначчи, числа Ферма и др.

Вариации и обобщения[править | править код]

Неприводимые и простые элементы[править | править код]

В начале статьи было дано определение простого числа: натуральное число называется простым, если у него ровно два делителя — единица и само число. Аналогичное понятие можно ввести и в других алгебраических структурах; чаще всего рассматривается коммутативные кольца без делителей нуля (области целостности)^[78][79]. У таких колец, однако, могут быть делители единицы, образующие мультипликативную группу. Например, в кольце целых чисел существуют два делителя единицы: и Поэтому все целые числа, кроме делителей единицы, имеют не два, а по меньшей мере четыре делителя; например, у числа 7 делителями являются Это означает, что обобщение понятия простого числа должно опираться на иные его свойства.

Аналогом простого числа для области целостности является неприводимый элемент, который определяется следующим образом^[80].

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

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

Важное значение имеет аналог основной теоремы арифметики, который в обобщённом виде формулируется следующим образом^[81]:

Не всякая область целостности факториальна, см. контрпример. Евклидово кольцо всегда факториально^[82].

Существует другое, более узкое обобщение понятия простого числа, называемое простым элементом^[80].

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

Обратное, вообще говоря, неверно, неприводимый элемент может не быть простым, если кольцо не является факториальным. Пример^[83]: рассмотрим кольцо чисел вида где  — целые числа. Число 3 в нём неприводимо, так как у него только 4 делителя: . Однако оно не является простым элементом, в чём убеждает равенство:

Число 3 делит правую часть равенства, но не делит ни одного из сомножителей. Можно из этого факта сделать вывод, что рассмотренное кольцо не факториально; и в самом деле, равенство показывает, что разложение на неприводимые множители в этом кольце не однозначно.

Примеры[править | править код]

Кольцо целых чисел факториально. В нём, как уже упоминалось выше, два делителя единицы.

Гауссовы целые числа[править | править код]

Кольцо гауссовых чисел состоит из комплексных чисел вида где  — целые числа. Делителей единицы четыре: Это кольцо факториально, неприводимыми элементами являются часть обычных простых чисел и «простые гауссовы» (например, ). См. критерий простоты гауссова числа.

Пример разложения для числа 2, которое в кольце гауссовых чисел не является простым:  — неединственность разложения здесь кажущаяся, поскольку ассоциирована с , согласно равенству:

Целые числа Эйзенштейна[править | править код]

Кольцо целых чисел Эйзенштейна состоит из комплексных чисел следующего вида^[84]:

где  — целые числа, (кубический корень из единицы),

В этом кольце шесть делителей единицы: (±1, ±ω, ±ω²), оно евклидово и поэтому факториально. Неприводимые элементы (они же простые элементы) кольца называются простыми числами Эйзенштейна.

Критерий простоты: целое число Эйзенштейна является простым числом Эйзенштейна тогда и только тогда, когда выполняется одно из следующих взаимоисключающих условий:

1. ассоциировано с натуральным простым числом вида
2. (норма ) является натуральным простым вида или .

Отсюда следует, что норма любого целого числа Эйзенштейна является либо простым натуральным числом, либо квадратом простого натурального числа^[84].

Числа, ассоциированные или комплексно-сопряжённые с простыми числами Эйзенштейна, также являются простыми числами Эйзенштейна.

Кольцо многочленов[править | править код]

Большое значение в алгебре имеет кольцо многочленов , образованное многочленами с коэффициентами из некоторого поля Делителями единицы являются здесь ненулевые константы (как многочлены нулевой степени). Кольцо многочленов евклидово и поэтому факториально. Если в качестве взять поле вещественных чисел, то неприводимыми будут все многочлены 1-й степени и те многочлены 2-й степени, у которых нет вещественных корней (то есть их дискриминант отрицателен)^[85].

См. также[править | править код]

Примечания[править | править код]

Литература[править | править код]

• Ван дер Варден. Алгебра. Определения, теоремы, формулы. — СПб.: Лань, 2004. — 624 с. — ISBN 5-8114-0552-9.
• Василенко О. Н. Теоретико-числовые алгоритмы в криптографии. — М.: МЦНМО, 2003. — 328 с. — ISBN 5-94057-103-4. Архивная копия от 27 января 2007 на Wayback Machine
• Винберг Э. Б. Малая теорема Ферма и ее обобщения // Математическое просвещение — М.: Изд-во МЦНМО, 2008. — Т. 12. — С. 43—53.
• Гальперин Г. Просто о простых числах // Квант. — № 4. — С. 9—14,38.
• Генри С. Уоррен, мл. Глава 16. Формулы для простых чисел // Алгоритмические трюки для программистов = Hacker’s Delight. — М.: «Вильямс», 2007. — 288 с. — ISBN 0-201-91465-4.
• Карпушина Н. Палиндромы и «перевёртыши» среди простых чисел // Наука и жизнь. — 2010. — № 5.
• Кордемский Б. А. Математическая смекалка. — М.: ГИФМЛ, 1958. — 576 с.
• Кормен Т., Лейзер Ч. Глава 33.8. Проверка чисел на простоту // Алгоритмы. Построение и анализ. — М.: МЦНМО, 2002. — С. 765—772. — ISBN 5-900916-37-5.
• Крэндалл Р., Померанс К. Простые числа. Криптографические и вычислительные аспекты = Prime Numbers: A Computational Perspective. — М.: УРСС, Либроком, 2011. — 664 с. — ISBN 978-5-397-02060-2.
• Курош А. Г. Лекции по общей алгебре. — 2-е изд.. — Наука, 1973.
• Ленг С. Алгебра. — М.: Мир, 1967.
• Матиясевич Ю.. Формулы для простых чисел // Квант. — 1975. — № 5. — С. 5—13.
• Нестеренко Ю. В. Алгоритмические проблемы теории чисел // Введение в криптографию / Под редакцией В. В. Ященко. — Питер, 2001. — 288 с. — ISBN 5-318-00443-1.
• Цагер Д. Первые 50 миллионов простых чисел // Успехи математических наук. — Российская академия наук, 1984. — Т. 39, № 6(240). — С. 175—190.
• Черёмушкин А. В. Лекции по арифметическим алгоритмам в криптографии. — М.: МЦНМО, 2002. — 104 с. — 2000 экз. — ISBN 5-94057-060-7. Архивировано 31 мая 2013 года..
• Простое число // Энциклопедический словарь юного математика / Сост. А. П. Савин. — М.: Педагогика, 1985. — С. 262—263. — 352 с.
• Энрике Грасиан . Простые числа. Долгая дорога к бесконечности. — Де Агостини, 2014. — Т. 3. — 148 с. — (Мир математики). — ISBN 978-5-9774-0682-6. — ISBN 978-5-9774-0637-6.
• Bakhtiari M., Maarof M. A. Serious Security Weakness in RSA Cryptosystem (англ.) // International Journal of Computer Science Issues — 2012. — Vol. 9, Iss. 1, No 3. — P. 175—178. — ISSN 1694-0814; 1694-0784
• Crandall R., Pomerance C. Глава 3. «Recognizing Primes and Composites». Глава 4. «Primality Proving» // Prime Numbers: A Computational Perspective. — Springer, 2005. — С. 117—224. — ISBN 0-387-25282-7.

Ссылки[править | править код]

• Кноп К. В погоне за простотой.
• The Prime Pages (англ.) — база данных наибольших известных простых чисел (англ.).
• Геометрия простых и совершенных чисел (исп.).
• Скрипт визуализации
• Форум искателей простых чисел (англ.).

Степан Кузнецов
«Квант» №10, 2020

Как быстро проверить, является ли данное натуральное число n простым? Такая задача часто возникает на практике. Один из примеров — шифр RSA¹. Это асимметричный шифр: шифрование производится закрытым ключом (известен только отправителю), а расшифровка — открытым (известен всем). Чтобы сгенерировать такую пару ключей для шифра RSA, нужно выбрать два больших числа p и q, причем оба числа должны быть простыми — иначе шифр невозможно будет расшифровать.

Проще всего действовать по определению, перебирая все числа от 1 до n и проверяя, не является ли какое-то из них делителем. Этот способ можно немного усовершенствовать: если n = ab, то меньший из двух делителей a и b окажется меньше или равен (sqrt{n}). Значит, достаточно перебирать числа не до n, а всего лишь до (sqrt{n}).

Время работы такого алгоритма, однако, будет огромным. Например, если в двоичной записи числа n тысяча разрядов (это минимальная длина криптографического ключа RSA, гарантирующая безопасность), то число проверок равно (sqrt{n}) ≈ 2⁵⁰⁰ ≈ 3 ⋅ 2¹⁵⁰. Если даже одна проверка делается за 1/10⁹ секунды (частота 1 гигагерц), то для выяснения простоты числа n понадобится 3 ⋅ 10¹⁴¹ c ≈ 10¹³⁴ лет! Можно попытаться «подобраться» к числу n с помощью решета Эратосфена, однако серьезного уменьшения времени работы это не даст. Нужны более глубокие идеи.

Начнем с малой теоремы Ферма (МТФ): если n — простое число, то для любого a от 1 до n − 1 число a^n − 1 при делении на n дает остаток 1 (т. е. a ^n − 1 ≡ 1(mod n)). Значит, если мы вдруг нашли такое a, что остаток оказался другим, то n заведомо не простое! Разумеется, перебирать все a в попытке найти нужное — затея не лучше, чем перебирать возможные делители. Но мы попробуем угадать a, выбирая его случайным образом.

Эта идея не такая безнадежная, как может показаться на первый взгляд. Действительно, пусть оказалось, что a₀^n − 1 (not≡) 1(mod n), а a₁^n − 1
≡ 1(mod n) (т. е. если мы выбрали a₀ , то мы угадали, а если выбрали a₁, то нет). Тогда

(a₀ ⋅ a₁)^n − 1 ≡ a₀^n − 1 ⋅ a₁^n − 1 ≡ a₀^n − 1 (not≡) 1(mod n)

. Таким образом, если мы угадали с выбором a₀, то также удачным будет выбор a₀ ⋅ a₁. Более того, если a₀ взаимно просто с n, то для разных значений a₁ числа a₁ ⋅ a₂ будут различны по модулю n. Таким образом, среди всех чисел от 1 до n − 1, взаимно простых с n, окажется не менее половины «удачных»: действительно, каждому «неудачному» числу a₁ соответствует как минимум одно уникальное «удачное», равное остатку от деления a₀ ⋅ a₁ на n (где a₀ — одно фиксированное «удачное» число).

Итак, алгоритм — его называют тестом Ферма — действует так. Выбираем случайное a в диапазоне от 2 до n − 1 (число 1 выбирать бессмысленно). Если a не взаимно просто с n — это можно быстро проверить с помощью алгоритма Евклида² , то n заведомо составное. Иначе вычисляем остаток от деления a ^n − 1 на n, и если он не равен 1, то n — составное. Если же равен, то вероятность того, что мы выбрали «неудачное» a, а для другого a получился бы неединичный остаток, не превосходит 1/2. Возвести a в большую степень можно методом последовательного деления показателя пополам («быстрое возведение в степень»); при этом после каждого шага лучше брать остаток по модулю n, чтобы избежать слишком больших чисел. Повторяя алгоритм k раз, каждый раз выбирая случайное a независимо, мы уменьшим эту вероятность до 1/2^k , что очень быстро стремится к нулю с ростом k.

Подведем итог. Если тест Ферма отвечает, что n составное, то он совершенно точно прав; если говорит, что простое — то может ошибиться, но с очень малой вероятностью. Эту вероятность мы контролируем за счет изменения параметра k — например, можем сделать ее меньше, чем вероятность сбоя техники. Тогда на практике алгоритм будет неотличим от точного — а работает он намного быстрее, чем перебор делителей!

К сожалению, у теста Ферма есть фатальный недостаток. Существуют так называемые числа Кармайкла: эти вредные числа не являются простыми, но удовлетворяют МТФ для любого a, взаимно простого с n. В таком случае мы не сможем найти ни одного «удачного» a₀, и приведенное выше рассуждение недействительно. (Вероятность же случайно наткнуться на число a, не взаимно простое с n, мала.) Самые маленькие числа Кармайкла: 561, 1105, 1729. Числа Кармайкла относительно редки, однако, к сожалению, их бесконечно много³. (Иначе можно было бы «починить» тест Ферма, добавив в начале сверку с конечным списком чисел Кармайкла.)

Тем не менее, основную идею теста Ферма можно «спасти». Один из способов это сделать дает тест Соловея — Штрассена. Поскольку нас интересует случай нечетного n (иначе оно заведомо составное, если не равно 2), то n − 1 нацело делится на 2. Если n простое, то в силу МТФ имеем (left ( a^{frac{n-1}{2}}-1 right ) left ( a^{frac{n-1}{2}}+1 right )=a^{n-1}-1equiv0pmod{n}), откуда (a^{frac{n-1}{2}}equivpm1pmod{n}). Более того, знак (+ или –) можно вычислить, зная a и n — это символ Якоби (left (frac{a}{n} right )). Таким образом, мы получили новое сравнение, нарушение которого означает непростоту n, а именно: (a^{frac{n-1}{2}}equivleft ( frac{a}{n} right )pmod{n}). Теперь, однако, никакого аналога чисел Кармайкла нет: оказывается, что для составного n всегда найдется a₀, для которого (a_0^{frac{n-1}{2}}notequivleft ( frac{a}{n} right )pmod{n}). Далее, как и для теста Ферма, можно доказать, что таких «удачных» a не менее половины среди всех чисел от 1 до n − 1, взаимно простых с n. Доказательства сформулированных выше фактов элементарные, но довольно технические. Их можно найти, например, в книге О. Н. Василенко «Теоретико-числовые алгоритмы в криптографии» (М.: МЦНМО, 2003).

Итак, получается алгоритм: выбираем случайное a от 2 до n − 1, взаимно простое с n (если нашлось не взаимно простое — немедленно отвечаем, что n составное); вычисляем остаток от деления (a^{frac{n-1}{2}}) на n и сравниваем его по модулю n с (left ( frac{a}{n} right )) . Если ответ «не равно», то a составное, иначе — предположительно простое. Во втором случае вероятность ошибки равна 1/2, теперь уже для любого n. Повторяя алгоритм k раз, снижаем вероятность ошибки до 1/2k .

Существуют и другие вероятностные тесты на простоту. А можно ли построить алгоритм проверки на простоту, который работает быстро и при этом выдает ответ точно, а не с некоторой (пусть и сколь угодно близкой к 1) вероятностью? Такие тесты называются детерминированными. Таков тест Миллера (1976). Этот тест быстрый и детерминированный, однако доказательство того, что он работает правильно, опирается на недоказанное утверждение — расширенную гипотезу Римана. Быстрый детерминированный тест, корректность которого доказана полностью, был предложен сравнительно недавно — это тест Агравала — Каяла — Саксены или AKS-тест (2002). Однако вероятностные тесты все еще работают быстрее, чем AKS-тест.

---

¹ Подробнее о шифре RSA читайте в статье В.А. Успенского «Как теория чисел помогает в шифровальном деле» (Соросовский образовательный журнал, 1996, №6).

² Вагутен В. Алгоритм Евклида и основная теорема арифметики («Квант», 1972, №6); Абрамов С. Самый знаменитый алгоритм («Квант», 1985, №11).

³ Alford W.R., Granville A., Pomerance C. There are infinitely many Carmichael numbers. Annals of Mathematics, 1994, vol. 139, p. 703–722.

Как находить простые числа

• Авторы
• Руководители
• Файлы работы
• Презентация
• Наградные документы

Текст работы размещён без изображений и формул.
Полная версия работы доступна во вкладке “Файлы работы” в формате PDF

Введение

Всякий, кто изучает простые числа, бывает, очарован и одновременно ощущает собственное бессилие. Определение простых чисел так просто и очевидно; найти очередное простое число так легко; разложение на простые сомножители – такое естественное действие.

Почему же простые числа столь упорно сопротивляются нашим попыткам постичь порядок и закономерности их расположения? Может быть, в них вообще нет порядка, или же мы так слепы, что не видим его?
(Ч. Узерелл.1982)

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

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

Цель: сбор и систематизация сведений о нахождении множества простых чисел для овладения способами решения олимпиадных задач с простыми числами.

Задачи:

1. Проанализировать источники исследования.

2. Найти сведения об истории отыскания простых чисел в интернете.

3. Попытаться составить модели для нахождения простых чисел с помощью найденных сведений.

4. Найти и решить олимпиадные задачи с простыми числами.

Объект исследования: простые числа

Предмет исследования: олимпиадные задачи с простыми числами разных уровней сложности.

Гипотеза: все простые числа нужно отыскивать одно за другим.

Методы исследования: изучение источников по теме исследования, анализ полученных материалов, моделирование.

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

Какие источники помогут нам в поиске? Сайты: problems.ru проект МЦНМО при участии школы 57, научно-популярный физико-математический журнал «Квант». Статьи: Н. Макарова, «Простые числа», материал из Википедии — свободной энциклопедии, «Решето Эратосфена», «Число Мерсенна», «Простые числа Мерсенна», «Криптография», «Шифрование».

Основная часть

Глава 1. Теоретические сведения

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

Одним из первых свойств чисел, открытым человеком, было то, что некоторые из них могут быть разложены на два или более множителей, например:

6=2 3, 9=3∙3, 30=2∙15=3∙10.

А, например, числа 3,7,13,37 не могут быть разложены подобным образом.

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

Евклид определял простые числа так: «Простое число есть измеряемое только единицей». Иными словами, простые числа не имеют других делителей, кроме единицы и самого себя. Если p простое число, то его можно представить в виде произведения двух натуральных чисел только следующим образом:

p = p∙1.

Числа, не являющиеся простыми, называются составными. Всякое составное число имеет не меньше двух делителей отличных от 1.

1 – особое число, оно не является ни простым, ни составным.

Простые числа-близнецы это пара простых чисел, отличающихся на 2.

Если натуральное число a делится на натуральное число b, то число b называют делителем числа a, а число а – кратным числа b.

Таким образом, простые числа – это как бы “кирпичики” для строительства всех натуральных чисел. Например, число N = 500 представимо в виде такого произведения:N = 2² ∙5³

Представление составного числа в указанном виде называют разложением числа на простые множители.

Свойства делимости.

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

Если уменьшаемое и вычитаемое делится на одно и то же число, то и разность делится на это число.

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

Основная теорема арифметики.

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

Глава 2 Модели простых чисел

Модель «Решето Эратосфена»

Эратосфен Кире́нский древнегреческий ученый, жил в третьем веке до новой эры в Александрии.

В математике Эратосфена интересовал вопрос о том, как найти все простые числа среди натуральных чисел от 1 до… . Он придумал для этого следующий способ: сначала вычеркивают все числа, делящиеся на 2 (исключая само число 2). Потом берут первое из оставшихся чисел (а именно 3). Ясно, что это число – простое. Вычеркивают все идущие после него числа, делящиеся на 3. Первым оставшимся числом будет 5. Вычеркивают все идущие после него числа, делящиеся на 5, и т.д. Числа, которые уцелеют после всех вычеркиваний, и являются простыми. Так как во времена Эратосфена писали на восковых табличках и не вычеркивали, а “выкалывали” цифры, то табличка после описанного процесса напоминала решето. Поэтому метод Эратосфена для нахождения простых чисел получил название “решето Эратосфена”. (Приложение 1).

Древнейший алгоритм такого поиска был предложен 2000 лет назад.

Итак, Решето Эратосфена работает как своего рода аналоговая вычислительная машина. И, значит, вот что изобрел великий грек: он изобрел счетную машину. Простые числа располагаются на числовом ряду весьма причудливым образом.

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

II. Модель «Формулы 6n – 1, 6n + 1, где n натуральное число»

Анализируя Решето видно, что все простые числа либо на 1 меньше, либо на 1 больше чисел, кратных 6, т.е. 6n – 1, 6n + 1.

6 ∙ 1–1=5, 6 ∙ 1+1=7, 6 ∙ 2–1=11, 6 ∙ 2+1=13, 6 ∙ 3–1=17, 6 ∙ 3+1=19,

6 ∙ 4–1=23, 6 ∙4+1=25, 6 ∙5–1=29, 6 ∙ 5+1=31,

6 ∙ 6–1=35 – составное число.

III. Модель «Число Мерсенна 2^р – 1, где p – простое число»

2² – 1 = 3, 2⁵ – 1 = 31, 2⁷ – 1 = 127, … .

Но, 2¹¹ – 1 составное. 2¹¹ – 1 =2047 = 23∙ 89.

3, 7, 31, 127, 2047, 8191, 131071, 524287, 8388607.

2⁶⁷ – 1 = 193707721 ∙ 761838257287.

2^43112609 – 1 (46^-е число Мерсенна) – это самое большое найденное простое число.

В течение почти 200 лет математики считали, что число Мерсенна 2⁶⁷ – 1 простое. В 1903 г профессор Коул доказал, что это число имеет два простых множителя: 193707721 и 761838257287. Коул, чтобы разложить число на множители потратил все воскресенья в течение трёх лет.

Маре́н Мерсе́нн (1588 — 1648) — французский математик, физик, философ и теолог.

Числа вида 2^р – 1, где p – простое число, называются числами Мерсенна, впервые заметившего, что среди таких чисел много простых.

Как видно, среди первых девяти чисел Мерсенна только два составные.

В настоящее время составлены специальные программы для поиска чисел Мерсенна. Последнее число найдено в 2018 г.

Глава 3. Как искали?

Изучали таблицу простых чисел, двигаясь по натуральному ряду. (Приложение 2)

Простые числа в среднем встречаются все реже.

Числа-близнецы – два простых числа идут через одно, (например, 17 и 19, 29 и 31), а иногда подряд идет миллион составных чисел.

Простые числа могут оканчиваться только на следующие цифры: 1, 3, 7 или 9. Если число оканчивается на 2, 5 или 0, то оно не может быть простым, просто потому, что делится без остатка соответственно на 2, на 5 или на 10 (естественно, кроме 2 и 5).

Глава 4. Как применяются простые числа в жизни человека

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

Простые числа находят спрятанными в природе, но человечество научилось их использовать.

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

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

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

Глава 5. Какие задачи нашли?

1. Докажите, что любое простое число, большее 3, можно записать в одном из двух видов: 6n + 1 либо 6n – 1, где n – натуральное число.

2. Найти все такие натуральные числа p, что p и 5p + 1 – простые.

3. В книге рекордов Гиннесса написано, что наибольшее известное простое число равно 23021377 – 1. Не опечатка ли это?

4. Найдите все простые числа, которые отличаются на 17.

5. Найдите все натуральные n, при которых 2n – 1 и 2n + 1 – простые.

Какие задачи смогли решить?

Олимпиадных задач на простые числа много.

Задачи разного уровня сложности.

Чтобы решить любую задачу необходимо много знать.

Глава 6. Решение олимпиадных задач с простыми числами

Найти все такие натуральные числа p, что p и  5p + 1  – простые.

Решение: если p нечётно, то  5p + 1  чётно, значит, p чётное число, а чётное и одновременно простое число только при p = 2.

Ответ: p = 2.

Найти все такие натуральные числа p, что p и  3p² + 1  – простые.

Решение: если p нечётно, то  3p² + 1  чётно.

Ответ: p = 2.

В книге рекордов Гиннесса написано, что наибольшее известное простое число равно  23021377 – 1.  Не опечатка ли это?

Решение: Какая последняя цифра у числа  23021377 – 1? Любая степень числа, оканчивающегося цифрой 1, тоже оканчивается цифрой 1. Поэтому разность  23021377 – 1  оканчивается на 0 и, следовательно, не является простым числом.

Ответ: опечатка.

Найдите все простые числа, которые отличаются на 17.

Решение: такие числа имеют разную чётность.

Ответ: 2 и 19.

Найдите все простые числа, которые равны сумме двух простых чисел и разности двух простых чисел.

Решение: указанное простое число p нечётно, поэтому в сумме и разности участвуют числа разной чётности. Итак,  p = q + 2 = r – 2.  Отсюда видно, что числа дают разные остатки при делении на 3, значит, одно из них кратно 3, а так как оно простое, то равно 3.

Ответ: 5.

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

Решение: докажем, что любое простое число  p > 11  представляется в виде суммы двух составных. Поскольку любое такое число нечётно, то число  p – 9  чётно и, следовательно, составное. Поэтому  p = (p – 9) + 9  – искомое представление.

С другой стороны, непосредственно проверяется, что числа 2, 3, 5, 7 и 11 не представимы в виде суммы двух составных.

Докажите, что при  n > 2  числа  2n – 1 и  2n + 1  не могут быть простыми одновременно.

Решение: из трёх последовательных чисел  2n – 1,  2n,  2n + 1  одно делится на 3. Но 2n на 3 не делится. Значит, одно из двух оставшихся чисел кратно 3.

Заключение

Почему мы не смогли получить достоверную модель простых чисел?

Модель «Решето Эратосфена» не позволяет найти все простые числа, из-за трудоёмкости процесса;

Модель «Формулы 6n – 1, 6n + 1, где n натуральное число» при n= 4 в формуле 6n + 1 получаем составное число;

Модель «Число Мерсенна 2^р – 1, где p – простое число» при p=11 получаем составное число. Моделирование процесса нахождения простых чисел позволяет сделать вывод: гипотеза, что все простые числа нужно отыскивать одно за другим, подтвердилась.

Простые числа в будущем: простые числа несут в себе много тайн и их интересно узнать; продолжить изучение способов нахождения простых чисел и изучение методов решения олимпиадных задач с простыми числами.

Список литературы

Н. Макарова, «Простые числа».

Гальперин Г. А. Просто о простых числах.- Квант, № 4, 9 – 38 (1987)

http://ru.wikipedia.org

www.problems.ru

Приложение 1

Решето Эратосфена

Приложение 2

Таблица простых чисел

Просмотров работы: 1782

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

Эти числа занимают уникальный пьедестал в математике, особенно в области теории чисел. Великие умы потратили бесчисленные часы для расследования этой проблемы, в том числе такие великие умы, как Пол Эрдос, Г.Х. Харди и Сриниваса Рамануджан, и это лишь некоторые из них. Теперь, прежде чем мы углубимся в различные алгоритмы, чтобы найти простые числа, давайте сначала установим предварительное понимание простых чисел.

Что такое простые числа?

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

Чтобы понять это более точно, давайте выберем два числа – 5 и 6. Теперь 5 – это число, которое можно получить только умножением на 1 и 5 (само число). Однако, когда мы берем число 6, то замечаем, что его можно получить другим способом, кроме умножения 1 и 6 (само число). Его также можно получить умножением чисел 2 и 3, что означает, что это не простое число. Число, которое не является простым, известно как составное число.

Метод Марена Мерсенна

Метод простого числа Мерсенна – это специальный метод нахождения определенного вида простого числа, известный как простые числа Мерсенна. Название для этого метода происходит от французского монаха Марин Мерсенн, который первым определил его. Простые числа Мерсенна – это те, которые сводимы к виду 2ⁿ-1, где n-простое число. Первые несколько чисел в этом методе являются 2, 3, 5, 7, 13, 17, 19, 31, 61, и 89. Долгое время метод простых чисел Мерсенна представлял собой тяжёлую работу, так как при переходе к более высоким простым числам он был очень трудоемким.

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

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

В августе 2008 года системный администратор UCLA Эдсон Смит нашел наиболее значимое простое число, известное на тот момент. Смит установил программное обеспечение для Great Internet Mersenne Prime Search (Gimps), проекта распределенных вычислений на добровольной основе. Это число было простым числом Мерсенна длиной 12 978 189 цифр. Чтобы дать представление о том, насколько он велик, на его написание уйдет почти два с половиной месяца, а в случае печати он растянется на 50 км!

Метод простых чисел Ферма

Число Ферма, как и число Мерсенна, представляет собой особый вид простого числа. Название происходит от математика 17-го века и юриста Пьера де Ферма. Число Ферма похоже на число Мерсенна… с одной маленькой поправкой. Давайте возьмем число Ферма F_m, где мы можем определить F_m как 2^m +1. Здесь m снова равно 2, возведенному в степень n или 2ⁿ.

Фермат был твердо убежден в том, что все числа вышеуказанной формы – это простые числа. В дальнейшем он сказал, что он будет производить простые числа для всех целочисленных значений m. Что делает эти числа уникальными и красивыми, но очень хитрыми, так это то, что простые числа становятся чрезвычайно большими очень быстро, даже в пределах первых четырех итераций. Чтобы доказать это, возьмем n в качестве следующих значений, n=0, 1, 2, 3 и 4.

Когда n = 0, m = 2⁰ = 1; поэтому F₀ = 2 1 + 1 = 2 + 1 = 3, что является простым. Когда n = 1, m = 2¹ = 2; поэтому F₁ = 2² + 1 = 4 + 1 = 5, что является простым. Когда n = 2, m = 2² = 4; следовательно, F₂ = 2⁴ + 1 = 16 + 1 = 17, что является простым. Когда n = 3, m = 2³ = 8; следовательно, F₃ = 2⁸ + 1 = 256 + 1 = 257, что является простым. Когда n = 4, m = 2⁴ = 16; следовательно, F₄ = 2¹⁶ + 1 = 65536 + 1 = 65537, что является простым числом. Теперь, как вы можете заметить, к тому времени, когда мы достигнем F₅, значение достигает 4 294 967 297.

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