Нахождение простого числа

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

Натуральные числа можно поделить на простые и составные числа.

Каждое натуральное число, большее единицы, делится, по крайней мере, на два числа: на 1 и на само себя.

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

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

Эратосфен Киренский

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

Эратосфена Киренского (276 год до н.э. – 194 год до н.э.).

Один из самых разносторонних ученых античности. Особенно прославили Эратосфена труды по астрономии, географии и математике, однако он успешно трудился и в области филологии, поэзии, музыки и философии, за что современники дали ему прозвище Пентатл, т.е. Многоборец. Другое его прозвище Бета, т.е. «второй», возможно, также не содержит ничего уничижительного: им желали показать, что во всех науках Эратосфен достигает не высшего, но превосходного результата. Эратосфен родился в Африке, в Кирене. Учился сначала в Александрии, а затем в Афинах. Вероятно, именно благодаря столь широкому образованию и разнообразию интересов Эратосфен получил от Птолемея III Эвергета приглашение вернуться в Александрию, чтобы стать воспитателем наследника престола и возглавить Александрийскую библиотеку. Эратосфен принял это предложение и занимал должность библиотекаря вплоть до своей кончины. Его научные таланты удостоились высокой оценки современника Эратосфена, Архимеда, который посвятил ему свою книгу Эфодик (т.е. метод).

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

Сочинения Эратосфена не сохранились, мы имеем от них лишь фрагменты. Самым знаменитым математическим открытием Эратосфена стало так называемое «решето», с помощью которого находятся простые числа.

Сначала вычеркнем все четные числа, кроме двойки, это три столбика с желтым фоном. Потом вычеркнем числа, кратные трем, кроме самой тройки - это голубой столбик. Столбик под шестеркой уже вычеркнут как четный. Теперь избавляемся от чисел, кратных пяти, проводя синие пунктирные линии, впрочем, надо будет отметить только 25,35,55,65,85 и 95, так как остальные числа вычеркнуты ранее. Также делаем и с 7 - проводим розовую пунктирную линию, вычеркивая оставшиеся числа 49,77 и 91. Больше ничего вычеркивать не надо - числа кратные 8, 9 и 10 вычеркнуты при удалении соответственно четных и кратных трем. Оставшиеся числа и есть все простые числа, меньшие 102.

Теорема о бесконечности множества простых чисел

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

« Первых простых чисел существует больше любого указанного числа их».

Вот доказательство этой теоремы.

Предположим, что существует некое наибольшее простое число p. Тогда перемножим все простые числа, начиная с числа 2 и заканчивая числом p, и увеличим полученное произведение на единицу. Результат этих действий обозначим M.

Если число M составное, то оно должно иметь по крайне мере один простой делитель. Но этим делителем не может быть ни одно из простых чисел 2, 3, 5, 7, … p. Поскольку при делении M на каждое из них получаем в остатке один. Следовательно, число M либо само простое, либо делится на простое число большее p. Значит предположение, что существует наибольшее простое число p, неверно и множество простых чисел бесконечно.

Этапы развития теории простых чисел

Остановимся на некоторых этапах развития теории простых чисел.

В 1603 г. итальянский математик Пьетро Антонио Катальди составил таблицу простых чисел от 2 до 743.

В 1770 году Немецкий математик Иоганн Генрих Ламберт опубликовал таблицу наименьших делителей всех чисел, не превосходящих 102000 и не делящихся на 2, 3, 5. Вложив в этот труд поистине колоссальные усилия, Ламберт гарантировал бессмертие тому, кто доведет таблицу делителей до миллиона. На его призыв откликнулись многие вычислители.

В 1845 году французский математик Жозедо Бертран, исследуя таблицу простых чисел, в промежутке от 1 до 6 000 000 обнаружил, что между числами n и 2n-2 , n>3, содержится по крайне мере одно простое число. Например:

если n=4 получаем число 2*4-2=6. Между числами 4 и 6 действительно одно простое число 5.

Если n=7, то 2*7-2=12. Между 7 и 12 простое число 11.

В дальнейшем это свойство получило название постулата Бертрана, хотя самому ученому не удалось его доказать.

Числа Мерсенна

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

В это же время в прессе появилось сообщение о поступлении в Венскую академию 7 больших томов рукописных таблиц до 100 330 201.

Автором этого труда был Якуб Филлип Кулик, профессор высшей математики Пражского университета.

Среди простых чисел особую роль играют числа вида Мр = 2р -1 , где р - простое число.

Они называются простыми числами Мерсенна по имени французского монаха Мерена Мерсенна (1588-1648), одного из основателей Парижской Академии наук, друга Декарта и Ферма.