Теорема 1.3.5 (Ж. Адамар, Ш. Ж. Валле-Пуссен).

.

Любопытным фактом является утверждение следующей теоремы, доказанной в 1737 г. выдающимся швейцарским математиком Леонардом Эйлером (1707–1783).

Теорема 1.3.6 (Л. Эйлер). Ряд из чисел, обратных прос-тым, – расходящийся.

Это означает, что сумма ряда равна +. Тем не менее, его частичная сумма по всем известным простым числам (их примерно 50 млн) меньше 4.

Теоремы 1.3.5 и 1.3.6 приведены здесь без доказательства.

Также широко известно применение простых чисел в криптографии – науке о методах шифрования данных. Для криптографических целей нужны большие простые числа длиной более 80–90 десятичных знаков. Такие числа заме-чательно подходят для этих целей, т. к., во-первых, они встречаются довольно часто: аппроксимация была найдена французским математиком Жаком Адама-ром (1865–1963) и бельгийским математиком Шарлем Жаном де ла Валле-Пуссеном (1866–1962), которые независимо друг от друга доказали в 1896 г., что простых чисел, меньших натурального числа x, (теорема 1.3.5). Во-вторых, различные вычисления с простыми числами (модульная арифметика) дают хорошие односторонние функции (эффективно вычислимые, для задачи инвертирования которых не существует эффективных алгоритмов), позволяющие зашифровать преобразованное в числовой вид сообщение. Например, произведение двух простых чисел – качественная односторонняя функция.

Большой интерес представляют простые числа вида 2p – 1, которые названы в честь открывшего их французского математика, физика, философа и теолога Марена Мерсенна (1588–1648). Мерсенн открыл числа вида 2p – 1 в результате поиска совершенных чисел (так называются натуральные числа, которые равны сумме всех своих делителей, меньших данного числа, например, 496 = 1 + 2 + 4 + 8 + 16 + 31 + 62 + 124 + 248). Одним из преимуществ чисел вида 2p – 1, благодаря которому при проверке их на простоту происходит отсев показателей p, является то, что числа такого вида могут быть простыми только тогда, когда p – простое число. Но не для любого простого p число 2p – 1 является простым, например, 211 – 1 = 2047 = 23 × 89. При больших показателях p получаются огромные числа 2p – 1, поэтому все рекордные простые числа принадлежат классу чисел Мерсенна.

Французский математик Франсуа Эдуард Анатоль Люка (1842–1891) разработал методы для проверки чисел на простоту. В 1876 г. он доказал, что 2127 – 1 – простое число. Оно оставалось самым большим известным простым числом Мерсенна в течение 75 лет. Позже, в 1930 г., американский математик, профессор университета в Беркли Деррик Генри Лемер (род. в 1905 г.) продолжил работу Люка и получил тест проверки чисел Мерсенна на простоту, называемый теперь тестом Люка – Лемера.

Поиском простых чисел Мерсенна занимается проект GIMPS (Great Internet Mersenne Primes Search), действующий с 1996 г. Именно участники этого проекта последнее время находят новые большие простые числа Мерсенна. Инструментом поиска служит программа Prime95 основателя GIMPS Джорджа Вольтмана (род. в 1957 г.), последняя версия которой – v25.7, где и используется тест Люка – Лемера. Исходный текст этой программы открыт для изучения и представляет собой высокооптимизированный ассемблерный код.

Открытое в 1999 г. 38-е простое число Мерсенна являлось самым большим простым числом на конец XX в. – это число 26972593 – 1, которое содержит 2098960 десятичных знаков. После этого было открыто еще девять больших простых чисел Мерсенна. По состоянию на конец 2009 г. самым большим из них является открытое в августе 2008 г. 45-е число 243112609 – 1, содержащее 12978189 десятичных знаков, последним из найденных является открытое в ап-реле 2009 г. 47-е число 242643801 – 1, содержащее 12837064 десятичных знака.

Обобщением теоремы 1.3.2 является следующая теорема, доказанная в 1837 г. известным немецким математиком, внесшим существенный вклад в математический анализ, теорию функций и теорию чисел, Петером Густавом Ле-женом-Дирихле (1805–1859), приводимая здесь без доказательства.

Теорема 1.3.7 (П. Дирихле). Всякая арифметическая прогрессия {a + + b × n | n Î Z³0}, где a, b – фиксированные натуральные числа и (a, b) = 1, содержит бесконечно много простых чисел.

К сожалению, больше в теории чисел результатов, аналогичных теореме 1.3.7, нет. До сих пор существует много открытых вопросов относительно простых чисел, наиболее известные из которых были перечислены немецким математиком Эдмундом Георгом Германом Ландау (1877–1938) на V Международном математическом конгрессе в 1912 г.

Первая проблема Ландау, известная еще как проблема Гольдбаха (Крис-тиан Гольдбах (1690–1764), немецкий математик): доказать или опровергнуть, что каждое четное число, большее 2, может быть представлено в виде суммы двух простых чисел, а каждое нечетное число, большее 5, может быть представлено в виде суммы трех простых чисел. Вторая проблема Ландау: беско-нечно ли множество простых чисел-близнецов (чисел типа p и p + 2, например, 3 и 5, 5 и 7, 11 и 13, 17 и 19, 29 и 31,…, 1997 и 1999 и т. д.)? Третья проблема Ландау, известная также как гипотеза Лежандра (Адриен Мари Лежандр (1752–1833), французский математик): верно ли, что между n2 и (n + 1)2 всегда найдется простое число? Четвертая проблема Ландау: бесконечно ли множество простых чисел вида n2 + 1?

Открытыми проблемами являются бесконечность множества простых чисел Мерсенна, а также чисел Ферма и чисел-значений многочлена Эйлера , n = 0, 1, 2,... Еще известный французский математик Пьер де Ферма (1601–1665) показал, что , , , , – простые числа, и выдвинул гипотезу, что все числа такого вида простые. Однако эта гипотеза была опровергнута в 1732 г. Леонардом Эйлером, нашедшим разложение числа на простые множители: и больше простых чисел вида Fn найдено не было. При n = 0, 1, 2, 3,…, 39 многочлен g(n) дает число простое, однако больше простых чисел такого вида не найдено, например, g(40) = 412.