Исследовательская работа по математике "Эти непростые "простые числа"

Ленинский район

МБОУ СОШ № 160

Секция «Математика»

Горбунов Александр

4В класс

Эти непростые «простые числа»

Руководитель:

Плешивцева Алёна Николаевна,

учитель начальных классов

Новосибирск

2018

Содержание

I  Введение

II Теоритическая часть

1. Из истории вопроса
2. Алгоритм "решето Эратосфена»
3. Моё исследование
4. Самое большое простое число
5. Узоры простых чисел

III Заключение

Приложение

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

         Ч. Узерелл «Этюды для программистов»

Введение

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

Цель:

• исследование множества простых чисел.

Задачи:

• исследовать «решето Эратосфена»
• самостоятельно составить таблицу простых чисел до 1000
• выяснить, существует ли самое большое простое число и имеет ли ряд простых чисел конец?
• подробнее узнать о применении простых чисел

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

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

• работа с учебной и научно-популярной литературой, ресурсами сети Интернет
• метод «решето Эратосфена».
• наблюдение, сравнение, анализ

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

Из истории вопроса

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

Просто́е число́ — это натуральное число, которое имеет ровно 2 натуральных делителя (только 1 и самого себя).

Составное число́ — натуральное число большее 1, не являющееся простым.1(единица) – особое число, оно не является ни простым, ни составным.Таким образом, все натуральные числа, за исключением единицы, разбиваются на простые и составные.

Евклид — древнегреческий математик, автор первого из дошедших до нас теоретических трактатов по математике. Биография, сведения о нем крайне скудны. Его научная деятельность протекала в Александрии в 3 веке до н. э. Евклид — первый математик александрийской школы. Его главная работа «Начала» содержит изложение планиметрии, стереометрии и ряда вопросов теории чисел. В ней он подвёл итог предшествующему развитию греческой математики и создал фундамент дальнейшего развития математики. Евклид — автор работ по математике, астрономии, оптике, музыке и др.

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

Эратосфен Киренский — древнегреческий математик (276-194 до нашей эры), заведовал Александрийской библиотекой и заложил основы математической географии, вычислив с большой точностью величину земного шара. Он был первым составителем таблицы простых чисел.

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

Решето́ Эратосфе́на — алгоритм нахождения всех простых чисел до некоторого целого числа n. Как и во многих случаях, здесь название алгоритма говорит о принципе его работы, то есть решето подразумевает фильтрацию, в данном случае фильтрацию всех чисел за исключением простых. По мере прохождения списка нужные числа остаются, а ненужные исключаются.

Алгоритм «Решето Эратосфена»

Эратосфен родился в 276 году до нашей эры, то есть этому методу уже около 2200 лет. Но он настолько прост и изящен,что можно объяснить его любому ребёнку. Итак, в чем суть метода и как его применять.

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

Берем числовую последовательность натуральных чисел, начиная с 2

2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12

И удаляем все числа кратные 2.

Для этого умножаем числа натурального ряда, по порядку на 2 и результат

умножения вычеркиваем.

2×2=4, вычеркиваем 4,

2х3=6, вычеркиваем 6 и т.д.

Таким образом, исключаем все четные, больше 2.

Два  — простое число, так как имеет, всего два натуральных делителя 1 и 2.

Получаем.

2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12…

Затем вычеркиваем числа кратные трем (умножаем на 3 все числа, также по

порядку ):

2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15…

Потом, вычеркиваем числа кратные пяти и т.д.

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

есть простые.

Сам Эратосфен построил таблицу простых чисел до 1000.

Сейчас, найдены огромные простые числа, но процесс все еще идет.

Моё исследование

Я решил сам составить таблицу простых чисел по методу «решето Эратосфена».

В итоге я составил 10 таблиц и выяснил, что количество простых чисел до 1000 равно 168.

Простые числа от 1 до 100:  25 чисел

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 до 200: 21 число

101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167,  173, 179, 181, 191, 193, 197, 199

Простые числа от 201 до 300:  16 чисел

211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293

Простые числа от 301 до 400: 16 чисел

307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397

Простые  числа от 401 до 500: 17 чисел

401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499

Простые числа от 501 до 600: 14 чисел

503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599

Простые числа от 601 до 700: 16 чисел

601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691

Простые числа от 700 до 800: 14 чисел

701,709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797

Простые числа от 800 до 900: 15 чисел

809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887   

Простые  числа от 900 до 1000:  14 чисел

907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997

Я пришёл к выводу:количество простых чисел постепенно уменьшается.

Самое большое простое число.

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

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

Многие учёные-математики, а также любители, занимаются поиском рекордных по величине простых чисел, за нахождение которых организацией ElectronicFrontierFoundationбыло предложено несколько наград в зависимости от величины числа. Так, в 2009 году была вручена премия в 100 000 долларов США, назначенная сообществом ElectronicFrontierFoundation за нахождение простого числа, десятичная запись которого содержит не менее 10 миллионов цифр.

Издавна ведутся записи, отмечающие наибольшие известные на то время простые числа. Один из рекордов поставил в 1772 году математик Эйлер, найдя простое число 231 — 1 = 2 147 483 647[2].

26 декабря 2017 года наибольшим известным простым числом стало число 277 232 917 − 1, которое содержит 23 249 425 десятичных цифр[1]. Открытие сделал JonathanPace в рамках проекта GIMPS.

Узоры простых чисел

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

Сидя как-то на скучной лекции, он, ни о чем не думая, начал рисовать решетку из горизонтальных и вертикальных линий. В одной из полученных таким образом клеток он поставил 1 и стал нумеровать остальные клетки по спирали, расходящейся от первой клетки:

5 4 3

6 1 2

7 8 9

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

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

квадратиками, а простые - черными. Выделяющиеся тёмные линии – это залежи простых чисел.

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

Фрагмент спирали Улама - простейшая иллюстрация закономерности в распределении простых чисел.

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

Заключение

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

В процессе работы над исследованием, я сделал следующие выводы:

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

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

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

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

«Простые числа не так просты,

как это кажется с первого взгляда!»

Фома Евграфович Топорищев,

писатель-философ

Приложение 1

Удивительные сказки

«Сказка о простых числах»

Жил да был на свете один мальчик. Звали его Кирилл. Однажды он в 4 классе со своим учителем поспорил, что простые числа человеку не нужны.

-Ну, есть они и пусть будут, но нам от этого ни какой пользы нет.

Учитель ему и говорит:

-Раз ты так считаешь то приведи пример.

-Сейчас… ну… эм…

-Ну-ну, молодой человек.

- Я дома найду почему нам от этого нет никакой пользы.

Думал Кирилл, думал и тут, у него дома начались новости. И диктор сказала:

-Срочно - на человека упала надпись с магазина…

И тут Кирилла осенило, что вот они могут убить человека.

Пришёл он в класс и говорит:

-Алена Николаевна, по новостям вчера сказали, что на человека упала надпись с магазина.

-Да-да, было такое!Эх, бедный человек!

-И вот упала цифра 3, это ведь простое число!

- Это работники плохо прикрепили, вот она и упала.

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

-Добро пожаловать, человек, в наш мир – Мир Простых чисел.

- От вас всё равно нет никакой пользы, - перебил Кирилл.

Подходит к нему учитель и Кирилл подумал, что он заснул на уроке:.

-Так Курочкин к доске! - сказала Алена Николаевна.

Кирилл вышел к доске. Учительница указала на 1.

-Скажи, простое это число или нет?

-Да,- ответил Кирилл.

-Нет. Неправильно, оно не простое и не составное. «2» за урок!

Потом он проснулся, пришёл в школу и сказал:

- Я понял, для чего нужны простые числа.

-Для чего?

-Для того, что бы не получать двойки за урок…

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

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

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

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

Криптография и простые числа

В 1975 г. УитфилдуДиффи и Мартину Хеллману, в то время работавшим в Стэнфордском университете, пришла в голову идея асимметричного шифрования, или «шифрования с открытым ключом». Эта система основана на специальных математических функциях, называемых «односторонними функциями с потайным входом», которые позволяют зашифровывать текст, но делают расшифровку практически невозможной без знания используемого кода. Идея состоит в том, что каждый пользователь имеет пару ключей: открытый и закрытый. Если мы хотим отправить кому-то сообщение, мы зашифровываем это сообщение с помощью открытого ключа — то есть ключа, известного всем. Но только человек, имеющий соответствующий закрытый ключ, может расшифровать это сообщение. Одним из преимуществ такого метода является то, что закрытый ключ никогда не передается и поэтому его не нужно постоянно менять в целях безопасности. Идея метода не совсем проста, но мы можем пояснить ее с помощью аналогии. Представьте себе большой магазин, где продаются сотни тысяч банок с краской разного цвета. Возьмем две любые банки и смешаем краску в разных количествах. Пока все просто. Теперь, если мы покажем кому-нибудь получившийся цвет и попросим «расшифровать», какое количество каких красок использовалось изначально, на такой вопрос будет очень трудно ответить.

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

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

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

Тогда возникает вопрос: можно ли узнать, какие простые числа были перемножены, чтобы в результате получилось 91? Для ответа на него надо взять список простых чисел и проделать несколько проверок. Казалось бы, простое решение, как и в случае определения цвета красок, если в магазине было всего около десятка основных цветов.Но с простыми числами все намного сложнее.

Например, ни у кого не хватит терпения проверить, что число 1409 305 684 859 является результатом умножения простых чисел 705 967 и 1996 277, особенно если учесть, что эти два простых числа взяты из списка простых чисел между 1 и 2000000, а там таких «всего лишь» 148933. Однако мы живем в эпоху высоких технологий, и, конечно, эту задачу можно довольно быстро решить с помощью хорошей программы и мощного компьютера. Хотя все зависит от того, насколько большой этот магазин красок. Не следует также забывать, что количество простых чисел не просто очень большое, а бесконечное.

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

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

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

Простые числа в науке и технике.

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