Проект по теме: Загадка простых чисел.

Проект

«Загадка простых чисел»

Ученика 7 А класса Гумбина Андрея

Руководитель: Зубкова С.Н.

Введение

Цель: изучение множества простых чисел.

Задачи:

1.Изучить свойства и особенности простых чисел.

2.Изучить методы для нахождения простых чисел (решето Эратосфена, числа Мерсенна, теория Чебышева).

3.Выяснить применение простых чисел.

Методы исследования:

1.Работа с учебной и научно-популярной литературой, ресурсами сети Интернет.

2.Наблюдение, сравнение, анализ, обобщение и систематизация изученного материала.

Актуальность:

Простые числа с давних времен привлекают внимание математиков. Простые числа следует одно за другим по закону, который еще не найден. Но простые числа в математике играют важную роль. Из них с помощью умножения получаются все остальные числа. Хорошо было бы, если все простые числа можно было сосчитать! Но эта проблема до сих пор остается нерешенной. Как сказал Евклид: самого большого простого числа не существует.

Гипотеза:

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

Содержание

1.Простые числа и их свойства

2.Способы нахождения простых чисел. Распределение простых чисел в натуральном ряду.

3.Применение простых чисел.

4. Практическая работа.

5.Выводы.

1.Простые числа и их свойства

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

Ко времени появления работы Евклида «Начала» в 300 в. до н.э. , уже было доказано несколько важных фактов касательно простых чисел. В своей книге Эвклид доказал, что простых чисел бесконечное количество. Это, кстати, один из первых примеров использования доказательства от противного.

Евклид определял простые числа так: “Простое число есть измеряемое только единицей”. Иными словами, простые числа не имеют других делителей, кроме единицы и самого себя.  Например, 5,7,13, 47.

Рассмотрев числовой ряд простых чисел, я обратил внимание, что:

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

2. Единственное чётное простое число 2. Все остальные простые числа нечётные. Любое другое четное число сюда попасть попросту не может, так как уже по определению, кроме себя и единицы, делится еще и на два.

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

3.Простые числа – близнецы.

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

Числа - близнецы до 500:   3-5; 5-7; 11-13; 17-19; 29-31; 41-43; 59-61; 71-73; 101-103; 107-109; 137-139; 149-151; 179-181; 191-193; 197-199.

Сколько всего существует близнецов - современной науке неизвестно. По мере удаления от нуля близнецы встречаются всё реже и реже.

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

Это тройка различных простых чисел, разность между наибольшим и наименьшим из которых минимальна. Наименьшими простыми числами, отвечающими заданному условию, являются – 2, 3, 5  и  3, 5, 7.

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

p, p+2, p+6  или  p, p+4, p+6

называется триплетом. 

Первые простые числа-триплеты:

(5, 7, 11), (7, 11, 13), (11, 13, 17), (13, 17, 19), (17, 19, 23), (37, 41, 43), (41, 43, 47), (67, 71, 73), (97, 101, 103), (101, 103, 107), (103, 107, 109), (107, 109, 113), (191, 193, 197), (193, 197, 199)

5. Квадруплеты простых чисел.

Четвёрки простых чисел вида (p, p+2, p+6, p+8) или сдвоенные близнецы или квадруплеты:

(5, 7, 11, 13), (11, 13, 17, 19), (101, 103, 107, 109), (191, 193, 197, 199)

2. Способы нахождения простых чисел.

Поиск простых чисел — одна из самых парадоксальных проблем математики. Ученые пытались решить ее на протяжении нескольких тысячелетий, но, обрастая новыми версиями и гипотезами, эта загадка по-прежнему остается неразгаданной. Появление простых чисел не подчинено какой-либо системе: они возникают в ряду натуральных чисел самопроизвольно, игнорируя все попытки математиков выявить закономерности в их последовательности. Над поиском максимально больших простых чисел в своё время бились Катальди, Рене Декарт, Пьер Ферма, Марен Мерсенн, Лейбниц, Эйлер и многие другие математики.

1) Решето Эратосфена.                                                                                       Одним из наиболее известных алгоритмов поиска и распознавания простых чисел является решето Эратосфена. Так этот алгоритм был назван в честь греческого математика Эратосфена Киренского, которого считают автором алгоритма.

Для нахождения всех простых чисел, меньших заданного числа, следуя методу Эратосфена, нужно выполнить следующие шаги:

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

2) Простые числа Марен Мерсенна

Простые числа Мерсенна являются простыми числами специального вида Mp = 2p – 1, где р — другое простое число.

До 1750 года было найдено всего 8 простых чисел Мерсенна: М2, М3, М5, М7, М13, М17, М19, М31. То, что М31 - простое число, доказал в 1750 году Л. Эйлер. В 1876 году французский математик Эдуард Люка установил, что число М127=170141183460469231731687303715884105727- простое. В 1883 г. сельский священник Пермской губернии И.М.Первушин доказал, что число М61=2305843009213693951 является простым. Позднее было установлено, что числа М89 и М107 простые. 12 простых чисел Мерсенна были вычислены с помощью только карандаша и бумаги, а для вычисления следующих уже использовались механические настольные счетные машины.

Распределённый проект по поиску простых чисел GIMPS был запущен в 1997 году, и ныне считается самым длительным непрерывным процессом распределённых вычислений в истории человечества: он продолжается уже почти 20 лет. Сейчас в пиковые моменты в GIMPS участвует 360.000 процессоров с суммарной производительностью 150 трлн операций в секунду. За время работы GIMPS участники этого проекта нашли 14 простых чисел Мерсенна. Последнее из них 274 207 281-1 было обнаружено 07 января 2016 года. Всего на данный момент известно 49 простых чисел Мерсенна. В списке самых больших простых чисел, известных на сегодняшний день, десять первых мест занимают числа Мерсенна.

3)Простые числа Ферма

Пьер Ферма, который прославился своими выдающимися математическими работами, высказал гипотезу о том, что числа вида 2n+1 всегда будут простыми, если n является степенью двойки. Он проверил это для n = 1, 2, 4, 8 и 16, и был уверен, что в случае, когда n не является степенью двойки, число не обязательно получалось простым. Эти числа называются числами Ферма, и лишь через 100 лет Эйлер показал, что следующее число, 232 + 1 = 4294967297 делится на 641, и следовательно, не является простым.

Распределение простых чисел в натуральном ряду

1. Открытие П.Л. Чебышева

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

Большой шаг в разрешении этого вопроса сделал великий русский ученый Панфутий Львович Чебышев. В 1850 г. он доказал, что между любым натуральным числом (не равным 1) и числом, в два раза больше его (т. е. между n и 2n), находится хотя бы одно простое число. 

2. Скатерть (спираль) С. Улама.

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

Улама заинтересовало, как же будет выглядеть его спираль, если её продолжить до нескольких тысяч простых чисел. Разработав программу, Улам получил рисунок для чисел от 1 до 65 000 (иногда его называют “скатерть Улама”), из которого видно, что даже у края картины простые числа продолжают послушно укладываться на прямые.

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

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

3. Применение простых чисел

Если так трудно найти следующее простое число, то где и для чего эти числа можно использовать на практике?» Наиболее распространенным примером использования простых чисел является применение их в криптографии (шифровании данных). Простые числа - столп всех систем криптографии.  Самые безопасные и трудно дешифруемые методы криптографии основаны на применении простых чисел, имеющих в составе более трех сотен цифр. Давайте попробуем проиллюстрировать проблему, с которой сталкивается дешифровщик для расшифровки некоего пароля. Допустим, паролем является один из делителей составного числа, а дешифровщиком выступает человек. Возьмем число из первого десятка, например, 8. Каждый (я надеюсь) человек способен в уме разложить число 8 на простые множители – 8=2*2*2. Усложним задачу: возьмем число из первой сотни, например, 111. В этом случае 111 быстро разложат в уме на множители люди, знающие признаки делимости числа на 3 (если сумма цифр числа кратна 3, то данное число делится на 3), и действительно - 111=3*37. Усложняя задачу, возьмем число из первой тысячи, например 1207. Человеку (без использования машинной обработки) потребуется, как минимум, бумага и ручка, для того чтобы перепробовать деление числа 1207 на «все» предшествующие этому числу простые числа. И только перебрав последовательно деление 1207 на все простые числа от 2 до 17 человек, наконец то, получит второй целый делитель данного числа – 71. Однако и 71 необходимо так же проверить на простоту.

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

154789632113546873655345754321548435132353453432415453453121

интернет проект «Империя чисел» раскладывает менее чем за 10 секунд и выдает ответ:

154789632113546873655345754321548435132353453432415453453121=
=13*10651*932121816911*40192385205666881251*29839509365380853006747

 Задумайтесь, сколько жизней должен прожить человек, чтобы разложить данное число на простые множители без помощи машин!

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

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

Один человек, зашифровав важную информацию, установил на нее пароль (P) равный одному из простых делителей числа (А), сказав другому человеку, что число (А) содержит только два простых делителя и дав ему ключ для расшифровки – число (B), являющееся вторым делителем числа (А). Не трудно понять, что для расшифровки необходимо разделить А на B, чтобы получить пароль Р. Например в элементарном варианте А=111, ключ B=3 тогда пароль равен А/B=37.

        Допустим, число А попало к злоумышленнику, и он знает условие о том, что А состоит из 2-х простых делителей. При условии, что А=111 злоумышленнику не составит особого труда даже в уме взломать пароль. Теперь представим ситуацию когда число А состоит из 2 простых чисел, каждое из которых состоит из тысячи цифр… Если злоумышленник не знает ключа (одного из делителей), для факторизации числа А, состоящего из двух тысяч цифр, ему потребуется, как минимум, суперкомпьютер и большое количество времени его работы!!!

4. Практическая работа:

1. Изучив метод Эратосфена, я определил ряд простых чисел до 200.

2. Рассмотрим числа близнецы. В пределах первой сотни близнецы – это следующие пары чисел:

Более того (за исключением первой пары), при делении на тройку левого собрата в остатке всегда остается двойка, а правого – единица.

Все пары простых чисел-близнецов, кроме (3,5) имеют вид (6n - 1, 6n + 1). Проверим:

При n = 2 6n – 1 =11, 6n + 1 =13

При n = 3 6n – 1=17, 6n + 1=19

При n = 5  6n – 1=29, 6n + 1= 31

3. При делении на 30  все квадруплеты, кроме первого и второго, дают одну и ту же четвёрку остатков:

(11, 13, 17, 19).

Проверим:

(101, 103, 107, 109)

101: 30 = 3 (остаток 11), 103 : 30 = 3 (остаток 13), 107 : 30 = 3 (остаток 17), 109 : 30 = 3 (остаток 19)

(191, 193, 197, 199)

191 : 30 =6 (остаток 11), 193 : 30 = 6 (остаток 13), 197 : 30=3 (остаток 17), 199 : 30 = 6 (остаток 19)

4.Попробовал я коснуться проблемы поиска чисел Мерсенна. Используя формулу Mp = 2p – 1 ,я вычислил несколько первых чисел по формуле и записал их по порядку в таблицу из четырех столбиков.

Я убедился, что формула Мерсенна не является универсальной.

5.В практической части своей работы я решил проверить теорию Чебышева на несложных примерах. Примем для n несколько произвольных значений и найдем соответственно значение 2n.

n = 11, 2n = 22; простые числа: 13,17,19

n = 25, 2n = 50; простые числа: 29,31,37

n = 54, 2n = 108; простые числа: 59,61,67

n = 99, 2n = 198; простые числа: 101,103,107

Я определил, что для рассмотренных мною примеров теорема Чебышева верна. Чебышев доказал ее для любого случая, для любого n. За эту теорему его назвали победителем простых чисел.

6.При подготовке проекта мне встречались интересные факты про простые числа. Вот один из них.

В 18 веке были открыты простые числа:

 31, 331, 3331, 33331, 333331, 3333331, 33333331.

Удивительно, но следующее число 333333331 не является простым, оно делится на 17.

    Выводы:

Проведя свои исследования и анализируя научно-популярную литературу, я сделал следующие выводы:

1. Для простых чисел не существует 100% доказанной формулы или закономерности, описывающих распределение простых чисел в бесконечном натуральном ряду.
2. Не существует самого большого простого числа, последовательность простых чисел бесконечна.
3. Многие ученые на протяжении многих веков вносили свой вклад в изучение темы «Простые числа».
4. Простые числа не совсем соответствуют значению и определению слова «простой». По своей сути они очень сложны, многогранны и хранят много тайн, неизвестного. Моя гипотеза не подтвердилась.
5. В настоящее время исследование простых чисел  продолжается.

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

Ч. Узерелл

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

1. Гальперин Г. «Просто о простых числах» // Квант. — № 4. — С. 9-14,38.

2.  Интернет ресурсы:

http://www.numbernautics.ru/chislonautics/804-2012-05-25-14-38-53

http://fb.ru/article/60293/prostyie-chisla-obyidennost-nerazgadannoy-zagadki

http://ru.wikipedia.org/wiki/Простое_число

https://vallentinn.livejournal.com/150597.html

http://www.etudes.ru/en/