VI Международный конкурс научно-исследовательских и творческих работ учащихся
Старт в науке
Простые числа. Решето Эратосфена.
Автор работы награжден дипломом победителя II степени
Полная версия работы доступна во вкладке "Файлы работы" в формате PDF
«Простые числа не так просты,
как это кажется с первого взгляда!»
Фома Евграфович Топорищев,
писатель-философ
ВВЕДЕНИЕ
Актуальность.
В арифметике Эратосфен стал вторым гроссмейстером (после Евклида). Он составил первую таблицу простых чисел («Решето Эратосфена») и заметил, что многие простые числа группируются в пары близнецов: таковы 11 и 13, 29 и 31, 41 и 43… А Евклид доказал, что множество всех простых чисел бесконечно. Верно ли то же самое для чисел-близнецов? Эта задача не покорилась Эратосфену. Знать бы ему и его насмешливым питомцам, что она не будет решена даже через 22 столетия! В наши дни "проблема близнецов" остается единственной не решенной задачей, которая досталась нам от Античности. Справятся ли с нею математики 21 века?
Сейчас простые числа используются в разных областях: шифрование, нанотехнологии, программирование и во многих других. Простые числа помогают людям быть точнее в этих областях, а сейчас точность очень важна. В нанотехнологиях, например: в эти проекты вложены большие деньги, одно неверное действие – и эти вложения не принесут пользы.
Программирование: набрал не ту цифру – и придётся программировать заново. Одна ошибка может запросто поломать многодневную работу.
Данная работа посвящена простым числам и их вычислению, а также изучению трудов Эратосфена.
Цель исследования: Изучить алгоритм построения «Решета Эратосфена» и решить систему задач на простые числа.
Задачи исследования:
Изучить историю возникновения простых чисел и способы их нахождения.
Познакомиться со способом нахождения простых чисел «Решетом Эратосфена» и научиться находить простые числа с его помощью.
Найти ответы на вопросы, самостоятельно решив «Системы задач на простые числа».
Гипотеза: если простые числа так просты, как это кажется, то математики давно их изучили, и тогда про них должно быть все известно.
Методы исследования:
1.Работа с учебной и научно-популярной литературой, ресурсами сети
Интернет.
2. Решение задач на простые числа.
Объект исследования: Простые числа.
Предмет исследования: Решето Эратосфена.
Глава I. Теоретические основы простых чисел.
I.1. Понятие простого числа.
Слово «простой» в толковом словаре русского языка С.И.Ожегова обозначает «однородный по составу, не составной, не сложный, не трудный, легкодоступный пониманию, осуществлению».
Так неужели эти числа так просты, понятны и доступны? Соответствуют ли они своему названию? Из чего составлены целые числа? Конечно же, из единиц. Число 12 есть сумма двенадцати единиц. Но в то же время 12 - это произведение 3 и 4, 2 и 6. В свою очередь число 4 равно произведению 2 и 2, а 6 - произведению 2 и 3. Числа 2 и 3, так же как и числа 5, 7, 11, 13 и т. д. дальше не раскладываются. Их назвали простыми. Эти числа раскладываются на два различных множителя - единицу и себя самого. Число 1 не считают простым, поскольку оно раскладывается на два одинаковых множителя: 1 = 1 • 1.
Самое маленькое простое число – 2. Самое большое простое число, 391 581·2216193 – 1, было открыто 6 августа 1989 г. группой Aмдал-6. Число, содержащее 65 087 знаков, было получено на суперкомпьютере «Амдал-1200» в Санта-Кларе, штат Калифорния, США. Группа также открыла самые большие парные простые числа: (1 706 595·211235 – 1) и (1 706 595·211235 + 1).
I.2. Историческая справка
Эратосфен – древнегреческий математик, живший в 276-194 г. г. до нашей эры.Один из самых разносторонних ученых античности. Он заложил основы математической географии, вычислив с большой точностью величину земного шара, изобрел Широту и Долготу, а так же придумал високосный год. Большую часть своей жизни провел в Александрии (Египет), где был вторым главой Великой библиотеки.
Особенно прославили Эратосфена труды по астрономии, географии и математике, однако он успешно трудился и в области филологии, поэзии, музыки и философии, за что современники дали ему прозвище Пентатл, т.е. Многоборец. Другое его прозвище, Бета, т.е. "второй", по-видимому, также не содержит ничего унизительного: им желали показать, что во всех науках Эратосфен достигает не высшего, но превосходного результата.
Труды Эратосфена
Из сочинений Эратосфена по математике до нашего времени дошло только написанное к царю Птолемею письмо об удвоении куба. Это письмо сохранилось в комментарии Евтокия к трактату Архимеда «О шаре и цилиндре». В письме содержатся некоторые исторические сведения о делийской задаче, а также описание прибора, изобретённого самим автором и известного под именем мезолябия.
С ведения о других математических сочинениях Эратосфена отличаются крайней неполнотой. Папп в двух местах своего Собрания называет сочинение Эратосфена О средних величинах, замечая при этом, что оно во всех своих предположениях стоит в связи с линейными местами.
О сочинении Эратосфена «Платоник», посвящённом пропорциям, говорит Теон Смирнский. Возможно, что именно к Эратосфену восходит алгоритм «разворачивания всех рациональных отношений из отношения равенства», описанный Теоном Смирнским и Никомахом Геразским
Самым знаменитым математическим открытием Эратосфена стало так называемое "решето Эратосфена", с помощью которого находятся простые числа. Предложил свой способ великий греческий учёный Эратосфен около 200г. до н. э.
Впервые доказал, что простых чисел бесконечно много, великий учёный Евклид. К наиболее достоверным сведениям о жизни Евклида принято относить то немногое, что приводится в Комментариях Прокла к первой книге Начал Евклида. Отметив, что «писавшие по истории математики» не довели изложение развития этой науки до времени Евклида, Прокл указывает, что Евклид был старше Платоновского кружка, но моложе Архимеда и Эратосфена и «жил во времена Птолемея I Сотера», «потому что и Архимед, живший при Птолемее Первом, упоминает об Евклиде и, в частности, рассказывает, что Птолемей спросил его, есть ли более короткий путь изучения геометрии, нежели Начала; а тот ответил, что нет царского пути к геометрии»
Дополнительные штрихи к портрету Евклида можно почерпнуть у Паппа и Стобея. Папп сообщает, что Евклид был мягок и любезен со всеми, кто мог хотя в малейшей степени способствовать развитию математических наук, а Стобей передаёт ещё один анекдот о Евклиде. Приступив к изучению геометрии и разобрав первую теорему, один юноша спросил у Евклида: «А какая мне будет выгода от этой науки?» Евклид подозвал раба и сказал: «Дай ему три обола, раз он хочет извлекать прибыль из учёбы».
Некоторые современные авторы трактуют утверждение Прокла — Евклид жил во времена Птолемея I Сотера — в том смысле, что Евклид жил при дворе Птолемея и был основателем Александрийского Мусейона. Следует, однако, отметить, что это представление утвердилось в Европе в XVII веке, средневековые же авторы отождествляли Евклида с учеником Сократа философом Евклидом из Мегар. Анонимная арабская рукопись XII века сообщает:
Евклид, сын Наукрата, известный под именем «Геометра», ученый старого времени, по своему происхождению грек, по местожительству сириец, родом из Тира…
I.3. Способ нахождения простых чисел: Решето Эратосфена.
Теория чисел до сих пор имеет множество нерешенных задач, трудность которых связана, в том числе, и с чрезвычайной трудоемкостью проверки свойств числа, с ростом его значения. Большое число таких задач связано с понятием простого числа.
С древних времен известно, что во множестве натуральных чисел встречаются числа, которые делятся только на 1 и на само число. Такие числа назвали простыми.
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27,…
Еще Эвклид доказал, что простых чисел бесконечно много, но до сих пор не найдена формула, позволяющая вычислять следующее простое число, если известны все предыдущие простые числа. То есть, для того, чтобы найти следующее за простым числом 23 простое число, нужно проверить на делимость числа , 25, 27, 29 и обнаружить, что из их только число 29 не имеет делителей, то есть является простым. Причем, достаточно для числа n проверять его на делимость до числа n/2+1, то есть для числа 29 это проверка до значения делителя 29/2+1=15.
Знаменитый греческий учёный-математик Эратосфен Киренский разработал метод нахождения простых чисел – Решето Эратосфена.
А почему решето? Объясняют так: мы зачеркиваем числа, потом зачеркиваем еще числа, то, что остается, как бы напоминает то, что ОСТАЕТСЯ В РЕШЕТЕ. На самом деле все, что мы делаем, еще больше напоминает решето. Дело в том, что вычеркиваемые числа находятся на прямых линиях, а настоящее решето состоит из нитей, которые в натянутом виде тоже прямые. И эта мысль толкает нас к тому, чтобы построить решето весьма своеобразным способом: не вычисляя, а только лишь ПРОВОДЯ ЛИНИИ по линейке. Получается что-то вроде... решета...
Те немногие числа, которые остались незачеркнутыми, - простые (а также 2, 3, 5 и 7): 11, 13,17 и т.д. Итак, Решето Эратосфена работает как своего рода аналоговая вычислительная машина. И, значит, вот что изобрел великий грек: он изобрел СЧЕТНУЮ МАШИНУ. А ведь для простых чисел не существует даже формулы, по которой их можно вычислить все. Нет такой формулы, а Решето есть. Простые числа располагаются на числовом ряду весьма причудливым образом, но, создав Решето Эратосфена достаточно большого размера, мы отсеем (построим) их ВСЕ без исключения. Все они окажутся в дырках совершенно правильного геометрически Решета! Так «правильно» ли их расположение или «неправильно»? Никто не может сказать.
Решето Эратосфена для чисел от 1 до 100.
Подобным образом, в Научно-исследовательской лаборатории Лос-Аламоса1 были получены все простые числа до 100 000 000.
Другим очень простым методом является применение таблиц простых чисел, т. е. использование простых чисел уже найденных другими. За последние 200 лет было составлено и издано много таблиц простых чисел. Наиболее обширной из них является таблица Д. X. Лемера, содержащая все простые числа до 10 000 000. Но, по-видимому, не имеет большого смысла идти на значительные затраты и усилия, чтобы опубликовать эти таблицы. Лишь в очень редких случаях математику, даже специалисту в теории чисел, приходится решать вопрос о том, является ли какое-то большое число простым. Кроме того, большие числа, о которых математик хочет узнать, являются они составными или простыми, не берутся им произвольно. Числа, которые он хочет исследовать, обычно появляются в специальных математических задачах, и, таким образом, эти числа имеют очень специфическую форму.
Глава II. Практическое применение простых чисел
II.1. Задачи на простые числа.
1. Какие из следующих чисел являются простыми:
а) год Вашего рождения
б) текущий год
в) номер Вашего дома.
Решение:
а) Год моего рождения – 2005. 2005 – составное число, так как делится на 5.
б) Текущий год – 2018. 2018 – составное число, так как делится на 2.
в) Номер моего дома – 13. 13 является простым числом, так как делится только на само себя и на 1.
2. Найдите простое число, следующее за простым числом 1973.
Решение:
Нужно отсчитывать по числу:
1974 – делится на 2.
1975 – делится на 5.
1976 – делится на 2.
1977 – делится на 3.
1978 – делится на 2.
1979 – ни на что не делится. Значит, 1979 будет следующим простым числом после 1973.
3. Попытайтесь определить количество простых чисел в диапазоне 10001 – 10100.
Решение:
10007, 10009, 10037, 1039, 1061, 10067, 10069, 10079, 10091, 10093, 10099;
Т. е. 11 простых чисел
4. а) Кто и когда впервые разделил числа на чётные и нечётные, простые и составные?
б) Как Вы думаете, как учёный пришёл к этому открытию?
в) Могло ли случиться так, что простые числа так и не были открыты?
а) Впервые разделил числа на чётные и нечётные, простые и составные великий учёный Пифагор.
б) Как мне кажется, Пифагор пришёл к этому открытию, когда решал очередные задачи. И заметил, что числа, оканчивающиеся на 0, 2, 4, 6, и 8, делятся на 2 без остатка, а те, что оканчиваются на 1, 3, 5, 7 или 9, делятся на 2 с остатком, и разделил их на чётные и нечётные. После этого он заметил очередной факт – некоторые нечётные числа делятся только на 1 и сами на себя. Он назвал их простыми, а те, у кого больше двух делителей определил в группу составных чисел. Т.е. Пифагор пришёл к этому открытию методом наблюдения.
в) Я считаю, что такого случиться не могло, в связи с развитием мыслительной деятельности человека.
5. Какие числа называются чётными, а какие – нечётными? Какие числа называются простыми, а какие – составными? Приведите пример чётных и нечётных чисел, простых и составных.
Чётные – числа, которые делятся на 2 без остатка, а нечётные – с остатком.
Примеры: нечётные – 1, 57, 83… чётные – 2, 52, 98…
Простые числа – числа, которые имеют только два делителя (1 и само число), а составные – больше двух делителей.
Примеры: простые – 2, 1999, 10007… составные – 6, 198, 153…
6. а) Назовите два простых нечётных числа.
б) Сможете ли Вы привести пример двух простых чётных чисел?
в) Назовите все простые чётные числа.
а) Два простых нечётных числа – 3, 2011.
б)Нет, потому что простое чётное число только одно.
в)2.
7. С помощью решета Эратосфена найдите все простые числа от 1 до 50.
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47.
8. В разные времена математики пытались найти формулу, которая позволяла бы вычислять простые числа. Так, Леонард Эйлер указал формулу: p = x * x – x + 41, позволяющую вычислять сорок одно простое число, если х = 0, 1, 2… 40. С помощью этой формулы найдите пять простых чисел.
p = простое число
х = целое число от нуля до сорока.
0 х 0 - 0 + 41 = 41.
5 х 5 – 5 + 41 = 61.
20 х 20 – 20 + 41 = 421.
3 х 3 – 3 + 41 = 47.
40 х 40 – 40 = 1601
9 . Леонард Эйлер (1707г. – 1793г.), швейцарец по национальности, большую часть своей жизни проработавший в Петербургской академии наук, много сил отдавал изучению натуральных чисел. Одним из первых он высказал догадку, что всякое натуральное чётное число, большее 2, можно представить в виде суммы двух простых чисел. Проверьте это на примере нескольких чисел.
4 = 2 + 2; 8 = 5 + 3; 4010 = 2011 + 1999; 30 = 17 + 3.
10. Знаменитый учёный Христиан Гольдбах (1690г. – 1764г.), работавший в Петербургской академии наук, высказал догадку (в 1742г.), что любое нечётное число, большее 5, может быть представлено в виде суммы трёх простых чисел. Русский учёный академик Иван Матвеевич Виноградов (1891г. – 1983г.) сумел доказать это. Проверьте это на примере нескольких чисел.
7 = 2 + 2 + 3; 21 = 17 + 2 + 2; 55 = 19 + 19 + 17.
11. Несколько столетий ждёт решения «проблема близнецов». Какие числа называются числами-близнецами? Пользуясь таблицей простых чисел, назовите несколько пар чисел-близнецов.
Числа-близнецы – это простые числа, находящиеся на расстоянии друг от друга в одно составное число.
Примеры: 17 и 19, 1997 и 1999, 1301 и 1303…
12. Изучением простых чисел занимался русский математик Пафнутий Львович Чебышев (1821г. – 1894г.). Он доказал предположение француза Ж. Бертрана, что между любым натуральным числом, большим единицы, и числом, вдвое большим данного, всегда имеется не менее одного простого числа. Проверьте это на примере нескольких простых чисел.
2 х 2 = 4. Между 2 и 4 простое число – 3.
4 х 2 = 8. Между 4 и 8 простое число – 7.
20 х 2 = 40. Между 20 и 40 – 23, 29, 31, 37.
ЗАКЛЮЧЕНИЕ
Подводя итог проделанной работы, мы выяснили, чтопроблема простых чисел всё ещё существует, так как человечество ещё не знает, бесконечно ли много чисел-близнецов, или нет. С одной стороны – дело любопытное, интересно же, так оно или не так, но с другой – зачем заморачиваться по такой ерунде… Так считают некоторые. Как хорошо, что я к ним не отношусь, иначе не писал бы эту работу…
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ И ЛИТЕРАТУРЫ
http://ru.wikipedia.org/wiki/Решето_Эратосфена
Олехник С.Н., Нестеренко Ю.В., Потапов М.К. Старинные занимательные задачи. - М.:"Вита-Пресс", 1994.
Энциклопедия «Занимательная математика»
http://www.natalimak1.narod.ru/prost.htm
http://intoclassics.net/news/2010-11-22-19805
Учебник «Математика 6 класс», Н.Я.Виленкин, В.И. Жохова и др.изд. «Мнемозина», Москва 2013
1 Справка: Лос-А́ламос (исп. Los Álamos — «хлопковое дерево») — населённый пункт и округ в штате Нью-Мексико