Простые числа.

[barzel]

Система защиты информации RSA базируется на свойствах произведения простых чисел.

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

Что такое вообще простое число? Любое число, которое делиться только на единицу и на само себя называется простым. Благодаря этим своим свойствам, можно сказать, что простые числа суть кирпичики или базисные элементы числового ряда. То есть любое число можно получить просто перемножив несколько простых чисел. Так же как в химии все базируется на таблице элементов Менделеева, то и в математике пытаются навести порядок в простых числах.
Но при их исследовании возникает ощущение, что это просто какой-то хаос без определенной закономерности.

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

Давайте же проследим за историей поиска волшебной формулы для простых чисел.

Древняя Греция. Товарищ Эвклид приводит доказательство бесконечности множества простых чисел. Если взять произведение всех известных простых чисел и прибавить единицу, то получиться еще одно простое число. И так можно продолжать бесконечно долго.
Интересно, что это не всегда работает. Если взять простые числа до 13 и произвести такую манипуляцию, то мы не получим простое число. Мы получим 2x3x5x7x11x13+1=30,031. Это число не простое, 59х509=30,031

1605-1665. Пьер де Ферма́ вывел формулу для так называемых чисел Ферма. F=2 ^2N+1. Но уже пятый член этого ряда не простое число и его можно разделить на 641.

1664. Мерсенн. Числа Мерсенна имеют формулу p = 2ⁿ – 1, но формула работает не всегда. Например при n=11, p=2047 = 23 x 89

1690-1764 Эйлер на письмо Кристиана Гольдбаха пришел к заключению, что Каждое чётное число, большее двух, можно представить в виде суммы двух простых чисел..Это назвывается бинарная проблема Гольдбаха.

25 декабря 1640 года. Pождественская теорема Ферма-Эйлера. Нечётное простое число представимо в виде суммы двух квадратов (целых чисел) тогда и только тогда, когда оно имеет вид 4k+1

1707— 1783. Интересен многочлен (полином) x² + x + 41, который изучал ещё Леонард Эйлер. Он дает 39 простых чисел. Если учесть простоту формулы, то это просто поражает. А что, если обобщить формулу?
x² + x + q, то она вообще будет давать q-2 простых чисел. Поразительно.

1849. 15-летний Гаусс пошел в этом поиске другим путем. Вместо поиска формулы, он решил найти закономерность распределения простых чисел. И оказалась, что есть очень четкая зависимость. Он вывел новую функцию пи - количество простых чисел до определенного числа N- π(N). И оказалось, что эту функцию можно задать очень простой формулой: π(N)=N/ln(N). Для этого надо было соединить логарифмы с простыми числами, что совсем не тривиально. Это называется Теорема о распределении простых чисел.

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

Гаусс, ближе уже к преклонному возрасту, придумал интегральный логарифм, который он обозначал как,
Li(N)=1/log(2)+1/log(3)+..+1/log(N),
и задавал его через интеграл. π(N)~Li(N)

Следующим шагом было изучение Дзета-функции Риманом под руководством Дирихле. Сначала Риман был учеником Гаусса, а после смерти последнего Дирихле стал его научным руководителем. Дзета-функция- эта такая попытка объединить музыку и математику через сумму гармонического ряда.

В свое время Эйлер обнаружил, что при х=1, фунция равна бесконечности. А вот если х=2, то ряд равен π²/6. Поразительный результат, ряд бесконечный, а его сумма число конечное, но не рациональное.

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

Наше время. На наш век тоже осталось, что исследовать. В начале тысячелетия был опубликован список нерешенных математических задач. Среди них есть гипотеза Римана. За ее решение Математический институт Клэя (Clay Mathematics Institute, Кембридж, Массачусетс) выплатит приз в один миллион долларов США.

Знаменит ответ Гильберта на вопрос о том, каковы будут его действия, если он по какой-либо причине проспит пятьсот лет и вдруг проснется. Математик ответил, что самым первым делом он спросит, была ли доказана гипотеза Римана.