XI Международный конкурс научно-исследовательских и творческих работ учащихся
Старт в науке
Как находить простые числа
Автор работы награжден дипломом победителя II степени
Полная версия работы доступна во вкладке "Файлы работы" в формате PDF
Введение
Всякий, кто изучает простые числа, бывает, очарован и одновременно ощущает собственное бессилие. Определение простых чисел так просто и очевидно; найти очередное простое число так легко; разложение на простые сомножители - такое естественное действие.
Почему же простые числа столь упорно сопротивляются нашим попыткам постичь порядок и закономерности их расположения? Может быть, в них вообще нет порядка, или же мы так слепы, что не видим его?
(Ч. Узерелл.1982)
Данная тема была выбрана потому, что существует тайна распределения простых чисел в ряду натуральных чисел - в одних частях ряда их больше, в других – меньше. Возник интерес к способам нахождения простых чисел, возможности создания модели, с помощью которой можно найти все простые числа и как полученные знания помогут разобраться с решением некоторых олимпиадных задач.
Исходя, из этого актуальность исследования обусловлена наличием в работе представлений о поисках простых чисел и подборкой олимпиадных задач по теме разных уровней сложности.
Цель: сбор и систематизация сведений о нахождении множества простых чисел для овладения способами решения олимпиадных задач с простыми числами.
Задачи:
1. Проанализировать источники исследования.
2. Найти сведения об истории отыскания простых чисел в интернете.
3. Попытаться составить модели для нахождения простых чисел с помощью найденных сведений.
4. Найти и решить олимпиадные задачи с простыми числами.
Объект исследования: простые числа
Предмет исследования: олимпиадные задачи с простыми числами разных уровней сложности.
Гипотеза: все простые числа нужно отыскивать одно за другим.
Методы исследования: изучение источников по теме исследования, анализ полученных материалов, моделирование.
Практическая значимость: материалы будут способствовать повышению интереса к математике и помогут разобраться с решением некоторых олимпиадных задач. Возможно использование материала на внеклассных мероприятиях, занятиях внеурочной деятельности.
Какие источники помогут нам в поиске? Сайты: problems.ru проект МЦНМО при участии школы 57, научно-популярный физико-математический журнал «Квант». Статьи: Н. Макарова, «Простые числа», материал из Википедии — свободной энциклопедии, «Решето Эратосфена», «Число Мерсенна», «Простые числа Мерсенна», «Криптография», «Шифрование».
Основная часть
Глава 1. Теоретические сведения
Интерес к изучению простых чисел возник у людей в глубокой древности. И вызван он был не только практической необходимостью. Привлекала их необычная магическая сила. Числа, которыми можно выразить количество любых предметов.
Одним из первых свойств чисел, открытым человеком, было то, что некоторые из них могут быть разложены на два или более множителей, например:
6=2 3, 9=3∙3, 30=2∙15=3∙10.
А, например, числа 3,7,13,37 не могут быть разложены подобным образом.
Определение. Простым называется число, которое делится только само на себя и на единицу.
Евклид определял простые числа так: «Простое число есть измеряемое только единицей». Иными словами, простые числа не имеют других делителей, кроме единицы и самого себя. Если p простое число, то его можно представить в виде произведения двух натуральных чисел только следующим образом:
p = p∙1.
Числа, не являющиеся простыми, называются составными. Всякое составное число имеет не меньше двух делителей отличных от 1.
1 – особое число, оно не является ни простым, ни составным.
Простые числа-близнецы это пара простых чисел, отличающихся на 2.
Если натуральное число a делится на натуральное число b, то число b называют делителем числа a, а число а – кратным числа b.
Таким образом, простые числа – это как бы “кирпичики” для строительства всех натуральных чисел. Например, число N = 500 представимо в виде такого произведения:N = 22 ∙53
Представление составного числа в указанном виде называют разложением числа на простые множители.
Свойства делимости.
Если в сумме натуральных чисел каждое слагаемое делится на некоторое число, то и сумма делится на это число.
Если уменьшаемое и вычитаемое делится на одно и то же число, то и разность делится на это число.
Если в произведении натуральных чисел один из множителей делится на некоторое число, то и произведение делится на это число.
Основная теорема арифметики.
Каждое натуральное число, отличное от 1, может быть представлено в виде произведения простых множителей, и притом только единственным образом (с точностью до порядка следования сомножителей).
Глава 2 Модели простых чисел
Модель «Решето Эратосфена»
Эратосфен Кире́нский древнегреческий ученый, жил в третьем веке до новой эры в Александрии.
В математике Эратосфена интересовал вопрос о том, как найти все простые числа среди натуральных чисел от 1 до… . Он придумал для этого следующий способ: сначала вычеркивают все числа, делящиеся на 2 (исключая само число 2). Потом берут первое из оставшихся чисел (а именно 3). Ясно, что это число - простое. Вычеркивают все идущие после него числа, делящиеся на 3. Первым оставшимся числом будет 5. Вычеркивают все идущие после него числа, делящиеся на 5, и т.д. Числа, которые уцелеют после всех вычеркиваний, и являются простыми. Так как во времена Эратосфена писали на восковых табличках и не вычеркивали, а "выкалывали" цифры, то табличка после описанного процесса напоминала решето. Поэтому метод Эратосфена для нахождения простых чисел получил название "решето Эратосфена". (Приложение 1).
Древнейший алгоритм такого поиска был предложен 2000 лет назад.
Итак, Решето Эратосфена работает как своего рода аналоговая вычислительная машина. И, значит, вот что изобрел великий грек: он изобрел счетную машину. Простые числа располагаются на числовом ряду весьма причудливым образом.
Найти редкие оазисы простых чисел, затерянные в обширных пустынях составных чисел, нелегко. Решето Эратосфена позволяет это сделать! Но всё же найти все простые числа таким способом нельзя.
II. Модель «Формулы 6n – 1, 6n + 1, где n натуральное число»
Анализируя Решето видно, что все простые числа либо на 1 меньше, либо на 1 больше чисел, кратных 6, т.е. 6n – 1, 6n + 1.
6 ∙ 1–1=5, 6 ∙ 1+1=7, 6 ∙ 2–1=11, 6 ∙ 2+1=13, 6 ∙ 3–1=17, 6 ∙ 3+1=19,
6 ∙ 4–1=23, 6 ∙4+1=25, 6 ∙5–1=29, 6 ∙ 5+1=31,
6 ∙ 6–1=35 – составное число.
III. Модель «Число Мерсенна 2р – 1, где p – простое число»
22 – 1 = 3, 25 – 1 = 31, 27 – 1 = 127, ... .
Но, 211 – 1 составное. 211 – 1 =2047 = 23∙ 89.
3, 7, 31, 127, 2047, 8191, 131071, 524287, 8388607.
267 – 1 = 193707721 ∙ 761838257287.
243112609 – 1 (46-е число Мерсенна) – это самое большое найденное простое число.
В течение почти 200 лет математики считали, что число Мерсенна 267 – 1 простое. В 1903 г профессор Коул доказал, что это число имеет два простых множителя: 193707721 и 761838257287. Коул, чтобы разложить число на множители потратил все воскресенья в течение трёх лет.
Маре́н Мерсе́нн (1588 — 1648) — французский математик, физик, философ и теолог.
Числа вида 2р – 1, где p – простое число, называются числами Мерсенна, впервые заметившего, что среди таких чисел много простых.
Как видно, среди первых девяти чисел Мерсенна только два составные.
В настоящее время составлены специальные программы для поиска чисел Мерсенна. Последнее число найдено в 2018 г.
Глава 3. Как искали?
Изучали таблицу простых чисел, двигаясь по натуральному ряду. (Приложение 2)
Простые числа в среднем встречаются все реже.
Числа-близнецы - два простых числа идут через одно, (например, 17 и 19, 29 и 31), а иногда подряд идет миллион составных чисел.
Простые числа могут оканчиваться только на следующие цифры: 1, 3, 7 или 9. Если число оканчивается на 2, 5 или 0, то оно не может быть простым, просто потому, что делится без остатка соответственно на 2, на 5 или на 10 (естественно, кроме 2 и 5).
Глава 4. Как применяются простые числа в жизни человека
Люди поняли, что простые числа являются не только ключом к выживанию, но и огромным количеством строительного материала в математике. Каждое число, по сути, представляет собой совокупность простых чисел, а совокупность чисел составляет математику, а из математики получается целый научный мир.
Простые числа находят спрятанными в природе, но человечество научилось их использовать.
Криптография, (криптография — обеспечение конфиденциальности и целостности данных) благодаря которой наши кредитные карточки остаются в безопасности, когда мы покупаем что-нибудь онлайн, использует простые числа. Каждый раз, когда вы вводите номер своей кредитной карты на вебсайте, вы полагаетесь на то, что простые числа сохранят ваши тайны и информацию о вас в секрете. Для кодирования вашей кредитной карты ваш компьютер получает публичный номер Н с вебсайта, который и будет использоваться для совершения операций с вашей кредитной картой.
Причиной, по которой такое кодирование является настолько безопасным, является то, что очень легко перемножить простые числа между собой, но разложить число на простые множители практически невозможно.
Шифрование – это не единственная область применения простых чисел на практике. Простые числа используются в компьютерном моделировании различных процессов. Так же без них не обойтись и в машиностроении – например, количество лопаток турбин реактивных самолётов должно составлять простое число. Если этим правилом пренебречь, то возникает резонанс, разрушающий лопатки турбины.
Глава 5. Какие задачи нашли?
1. Докажите, что любое простое число, большее 3, можно записать в одном из двух видов: 6n + 1 либо 6n – 1, где n – натуральное число.
2. Найти все такие натуральные числа p, что p и 5p + 1 – простые.
3. В книге рекордов Гиннесса написано, что наибольшее известное простое число равно 23021377 – 1. Не опечатка ли это?
4. Найдите все простые числа, которые отличаются на 17.
5. Найдите все натуральные n, при которых 2n – 1 и 2n + 1 – простые.
Какие задачи смогли решить?
Олимпиадных задач на простые числа много.
Задачи разного уровня сложности.
Чтобы решить любую задачу необходимо много знать.
Глава 6. Решение олимпиадных задач с простыми числами
Найти все такие натуральные числа p, что p и 5p + 1 – простые.
Решение: если p нечётно, то 5p + 1 чётно, значит, p чётное число, а чётное и одновременно простое число только при p = 2.
Ответ: p = 2.
Найти все такие натуральные числа p, что p и 3p² + 1 – простые.
Решение: если p нечётно, то 3p² + 1 чётно.
Ответ: p = 2.
В книге рекордов Гиннесса написано, что наибольшее известное простое число равно 23021377 – 1. Не опечатка ли это?
Решение: Какая последняя цифра у числа 23021377 – 1? Любая степень числа, оканчивающегося цифрой 1, тоже оканчивается цифрой 1. Поэтому разность 23021377 – 1 оканчивается на 0 и, следовательно, не является простым числом.
Ответ: опечатка.
Найдите все простые числа, которые отличаются на 17.
Решение: такие числа имеют разную чётность.
Ответ: 2 и 19.
Найдите все простые числа, которые равны сумме двух простых чисел и разности двух простых чисел.
Решение: указанное простое число p нечётно, поэтому в сумме и разности участвуют числа разной чётности. Итак, p = q + 2 = r – 2. Отсюда видно, что числа дают разные остатки при делении на 3, значит, одно из них кратно 3, а так как оно простое, то равно 3.
Ответ: 5.
Найдите все простые числа, которые нельзя записать в виде суммы двух составных.
Решение: докажем, что любое простое число p > 11 представляется в виде суммы двух составных. Поскольку любое такое число нечётно, то число p – 9 чётно и, следовательно, составное. Поэтому p = (p – 9) + 9 – искомое представление.
С другой стороны, непосредственно проверяется, что числа 2, 3, 5, 7 и 11 не представимы в виде суммы двух составных.
Докажите, что при n > 2 числа 2n – 1 и 2n + 1 не могут быть простыми одновременно.
Решение: из трёх последовательных чисел 2n – 1, 2n, 2n + 1 одно делится на 3. Но 2n на 3 не делится. Значит, одно из двух оставшихся чисел кратно 3.
Заключение
Почему мы не смогли получить достоверную модель простых чисел?
Модель «Решето Эратосфена» не позволяет найти все простые числа, из-за трудоёмкости процесса;
Модель «Формулы 6n – 1, 6n + 1, где n натуральное число» при n= 4 в формуле 6n + 1 получаем составное число;
Модель «Число Мерсенна 2р – 1, где p – простое число» при p=11 получаем составное число. Моделирование процесса нахождения простых чисел позволяет сделать вывод: гипотеза, что все простые числа нужно отыскивать одно за другим, подтвердилась.
Простые числа в будущем: простые числа несут в себе много тайн и их интересно узнать; продолжить изучение способов нахождения простых чисел и изучение методов решения олимпиадных задач с простыми числами.
Список литературы
Н. Макарова, «Простые числа».
Гальперин Г. А. Просто о простых числах.- Квант, № 4, 9 – 38 (1987)
http://ru.wikipedia.org
www.problems.ru
Приложение 1
Решето Эратосфена
Приложение 2
Таблица простых чисел