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

Оглавление

^{ВВЕДЕНИЕ} 2

_{ПРОСТЫЕ ЧИСЛА} 2

Понятие простого числа 2

Бесконечность ряда простых чисел 3

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

Способы поиска простых чисел 4

Открытие века – Закон простых чисел 5

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

Исследования ученых теории простых чисел 5

Примеры ряда проблем в теории простых чисел 6

Задачи прикладного характера 7

Задачи на применение законов простых чисел 8

Магические квадраты 8

Применение закона простых чисел в различных областях 9

_{ЗАКЛЮЧЕНИЕ} 10

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

«В мире царит гармония, и выражена эта гармония – в числах»

Пифагор, древнегреческий математик

^{ВВЕДЕНИЕ}

На уроках математики при изучении темы «Простые и составные числа» учитель рассказал нам о простых числах, истории их изучения, а также применении знаний о них в современном мире. Мне захотелось побробнее их изучить. И чем больше я погружался в тему, тем интереснее и сложнее мне представились простые числа, которые вовсе и ни такие простые. Простые числа были введены примерно две с половиной тысячи лет назад, а нашли неожиданное практическое применение совсем недавно. Мы живем в век IT-технологий, но многие загадки простых чисел не решены до сих пор, есть даже такие, к которым ученые не знают, как подступиться. Предметом изучения простого числа послужили: теория о простых числах, способы их задания, интересные открытия в этой области и их практическое применение. Итак, целью моей работы является расширение знаний о простых числах. Я поставил для себя такие задачи: узнать историю развития теории простых чисел, ^{определить правила или способы нахождения простых чисел, узнать интересные достижения и проблемы в теории простых чисел, познакомиться с применением теории простых чисел в различных областях, как находить простые числа из множества натуральных чисел, изучить применение простых чисел в задачах.}

_{ПРОСТЫЕ ЧИСЛА} Понятие простого числа

Простые числа делятся без остатка только на себя и единицу. Простые числа - это основа составных чисел: всего множества натуральных чисел, не являющимися простыми. Одно из основных утверждений арифметики гласит: каждое натуральное число единственным образом разлагается на простые множители: 70 = 2ꞏ5ꞏ7; 1001=7ꞏ11ꞏ13. Разложение чисел на простые множители показывает, что всякое число является либо простым, либо произведением двух или нескольких простых чисел. Важно, число 1 не является ни простым, и не составным числом. Единственным четным простым числом является 2.

Первые простые числа 2, 3, 5, 7, 9, 11, 13, 17, 19, 23, 29, 31, 37, 41.

Заметны несколько особенностей: числа-«близнецы» - простые числа, разность между которыми равна 2. Называют их так потому, что они оказались по соседству друг с другом, разделенные только четным числом: 3 и 5, 5 и 7, 7 и 9, 17 и 19. Пары близнецов с общим элементом образуют пары простых чисел - «двойников»: 3-5-7. Можно заметить, что сумма этих чисел всегда кратна трем: 3+5+7=15, 5+7+9=21, 7+9+11=27.

Бесконечность ряда простых чисел

Я заметил, что в первом десятке простых чисел 4, во втором десятке – 4, в третьем, четвертом, шестом, седьмом и девятом – по 2, в восьмом – 3, а в десятом - только 1 число. Наблюдается нерегулярность распределения простых чисел. Было замечено, что по мере продвижения от малого числа к большему в натуральном ряду простые числа встречаются всё реже. Существует ли последнее простое число, или имеет ли ряд простых чисел конец? Около 300 лет до нашей эры на этот вопрос дал отрицательный ответ знаменитый древнегреческий математик Евклид, живший в III веке до нашей эры. В своем труде «Начало» он собрал все сведения по математике, которые были известны до него, систематизировал их, изложил очень четко и логически, начав с основных утверждений, которые принимаются без доказательств - аксиомы, а из них выводятся теоремы, которые доказываются. Именно в этом труде он задался вопросом: а сколько простых чисел? Конечное их число или бесконечное? Он доказал, что за каждым простым числом имеется, ещё большее простое число, то есть, существует бесчисленное множество простых чисел.

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

Одно дело быть уверенным в том, что существуют какие угодно большие простые числа, а другое дело — знать, какие эти числа. Очевидно, что чем больше натуральное число, тем больше вычислений надо провести, чтобы узнать, является ли оно простым или нет. Издавна ведутся записи, отмечающие наибольшие известные на то время простые числа. Один из рекордов поставил в своё время Эйлер в 18 веке, он нашел простое число 2³¹ – 1= 2 147 483647.

Марен Мерсенн (1588-1648г.), французский математик, предложил формулу поиска простых чисел M_n=2ⁿ-1, например: M₂=2²-1=3; M₃=2³-1=7. Наибольшим известным простым число-рекордсменом по состоянию на октябрь 2024 года является число Мерсенна: 2^136279841 - 1. Оно было найдено Люком Дюрантом в октябре 2024 года и содержит 41 024 320 десятичных цифр! Предыдущее самое большое известное простое число, открытое в декабре 2018 года, было на 16 миллионов знаков меньше. Для его нахождения понадобилось 75 мощных компьютеров, а чтобы распечатать его на бумаге понадобится более 13 тысяч страниц формата А4. 

Способы поиска простых чисел

Существуют различные способы поиска простых чисел. Первый, кто занимался задачей «выписать из множества натуральных чисел простые», был великий греческий математик древности Эратосфен, живший почти 2 300 лет назад. Он придумал такой способ: записал все числа от единицы до какого-то числа, а потом вычеркнул единицу, которая не является ни простым, ни составным числом, затем вычеркивал через одно все числа, идущие после 2, числа, кратные двум, т.е. 4,6,8 и т.д.). Первым оставшимся числом после 2 было 3. Далее вычеркивались через два все числа, идущие после трех, числа, кратные 3, т.е. 6, 9, 12, и т.д., в конце концов оставались не вычеркнутыми только простые числа: 2, 3, 5, 7, 11, 13, …

Таким образом, Эратосфен изобрёл способ, посредством которого можно отсеять все простые числа от 1 до некоторого определённого числа путем вычленения всех чисел кратных каждому простому числу. Этот способ называется «Решето Эратосфена». Решето Эратосфена - самый простой способ нахождения начального списка простых чисел вплоть до некоторого значения. Греки делали записи на покрытых воском табличках или на папирусе, а числа не вычёркивали, а выкалывали иглой, то таблица в конце вычислений напоминала решето, отсюда и название метода. Решето Эратосфена, как теоретический метод исследования, в теории чисел был введен в 1920 году Норвежским математиком В.Бруном. Математики, используя этот способ, составили таблицы простых чисел между 1 и 12000000. Я, изучая материал, пока видел только таблицу простых чисел до 100.

Внедрение средств вычислительной техники в облегчило решение задач, связанных с трудоёмкими расчётами. В память компьютеров можно заложить табличные данные любого объёма, такими возможностями не обладают калькуляторы. Поэтому над проблемами составления компактных и удобных таблиц, предназначенных, в частности, для анализа чисел, продолжают работать специалисты-математики. Применение для этой цели вычислительных машин позволило сделать весьма существенный шаг вперёд. Например, современная таблица чисел, для составления которой была привлечена вычислительная техника, охватывает числа до 10 000 000. Это довольно объёмистая книга. На практике вместо получения списка простых чисел зачастую требуется проверить, является ли данное число простым. Алгоритмы, решающие эту задачу, называются тестами простоты.

Открытие века – Закон простых чисел

Еще в глубокой древности ученых интересовал вопрос о том, по какому закону расположены в натуральном ряду простые числа. Победитель простых чисел – Владимир Хренов – своим открытием Закона простых чисел произвел шок в научном мире. Русский гений, Владимир Хренов сделал научное открытие, которое переворачивает существующее представление о времени и пространстве, что простые числа - это не хаос. Простые числа получаются по формуле: 6ꞏN + 1, где N - любое натуральное число.

13=6ꞏ2-1; 17=6ꞏ3-1; 19=6ꞏ3+1; 23=6ꞏ4-1; 31=6ꞏ5+1; 37=6ꞏ6-1

ПРИМЕНЕНИЕ ТЕОРИИ ПРОТЫХ ЧИСЕЛ

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

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

Чебышёв Пафнутий Львович (1821-1894) доказал, что между любым натуральным числом больше 1, и числом вдвое больше данного, всегда имеется хотя бы одно простое число. Рассмотрим следующие пары простых чисел, удовлетворяющих этому условию:

и 4 - простое число 3 и 6 - простое число 5 10 и 20 -простые числа 11; 13; 17; 19

5 и 10 - простое число 7 7 и 14 - простые числа 11; 13 11 и 22 - простые числа 13; 17; 19

Вывод: действительно, между любым натуральным числом больше 1 и числом вдвое больше данного, имеется хотя бы одно простое число.

Христиан Гольдбах, почти 250 лет назад высказал предложение, что любое нечетное число больше 5, можно представить в виде суммы трех простых чисел.

Примеры: 21 = 3 + 7 + 11, 37 = 17 + 13 + 7, 23= 5 + 7 + 11, 29= 11 + 13 + 5

Виноградов Иван Матвеевич (1891-1983), советский математик, доказал это предложение лишь 200 лет спустя.

Примеры: 7 = 2 + 2 + 3; 15 = 3 + 5 + 7 = 5 + 5 + 5; 9 = 3+3 + 3, 20 = 7 + 11 + 2.

Примеры ряда проблем в теории простых чисел

Многие свойства простых чисел являются для нас до сих пор загадкой. В 1742 году великому Эйлеру, когда он работал в Санкт-Петербургской Академии наук профессор Христиан Гольдбах прислал письмо. Он, проверив достаточно большое количество чисел пришел к выводу, что любое четное число, начиная с 4, является суммой двух простых чисел. Это совершенно не просто! Эйлер не ответил на письмо, ему не удалось решить эту задачу. Это было почти 250 лет назад. Утверждение Гольбаха по состоянию на 2024 год остается открытой математической проблемой.

Примеры: 28= 11 + 17; 924 = 311 + 613; 56= 19 + 37; 102 = 59 + 43.

Наиболее известные проблемы простых чисел были перечислены Эдмундом Ландау на Пятом Международном математическом конгрессе.

Первая проблема Ландау (проблема Гольдбаха): Каждое чётное число, большее двух, может быть представлено в виде суммы двух простых чисел, а каждое нечётное число, большее 5, может быть представлено в виде суммы трёх простых чисел.

Примеры: 8 = 3+5; 12 = 5+7; 16=13 +3; 17= 11+3+3;24=19+5, 21=11+7+3, 50 = 13+37

Вторая проблема Ландау (проблема Гольдбаха): Бесконечно ли множество «простых близнецов» — простых чисел, разность между которыми равна 2?

Определил следующие числа «близнецы»:

3 и 5; 5 и 7; 7 и 9; 11 и 13, 17 и 19; 41 и 43.

Пары близнецов состоят из двойников с общим элементом. Мне удалось найти следующие пары близнецов - «двойников».

Решение: (3, 5) и (5, 7); (7, 9) и (9, 11)

Известно, что простых чисел бесконечно много. Но никто не знает, конечно, или бесконечно множество пар близнецов.

Третья проблема Ландау (гипотеза Лежандра): Верно ли, что между числами вида: Nꞏ2 и (N + 1)ꞏ2, где N – нечетное всегда найдётся простое число?

Решение: а) при N=3, получим 6 и 8, между ними простое число 7.

б) при N=5, получим10 и 12, между ними простое число 11.

в) при N=9, получим18 и 20, между ними простое число 19.

Четвёртая проблема Ландау: Бесконечно ли множество простых чисел вида Nꞏ2+1?

Решение:

при N=1, то имеем 3; при N=2, то имеем 5; при N=3, то имеем 7

при N=5, то имеем 11, при N=6 то имеем 13; при N=8, то имеем 17 и т.д.

Задачи прикладного характера

Задача 1. С помощью решета Эратосфена определите сколько простых чисел находится от 1 до 100.

Решение: Для этого выпишем все числа от 1 до 100 вряд. .

1. Буду вычеркивать числа, которые не являются простыми: 1, так как это не простое число. 2 - первое простое число, подчеркиваю его и вычеркиваю все числа кратные 2, то есть числа 4, 6, 8... 100.

2. Следующее простое число 3. Подчеркну его и вычеркну числа кратные 3 – это числа 9, 15, 21 ... 99.

3. Затем подчеркну простое число 5 и вычеркну все числа кратные 5 - 25...95. И так далее, пока не останется одно простое число 97.

Вывод: Между 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.

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	28	29	30
31	32	33	34	35	36	37	38	39	40
41	42	43	44	45	46	47	48	49	50
51	52	53	54	55	56	57	58	59	60
61	62	63	64	65	66	67	68	69	70
71	72	73	74	75	76	77	78	79	80
81	82	83	84	85	86	87	88	89	90
91	92	93	94	95	96	97	98	99	100

Задачи на применение законов простых чисел

Задача 3. Как с помощью двух проверок показать, что число 19 – простое?

Решение. 1) 19=6ꞏ3+1 (по формуле Хренова В.) 2) 19=3+5+11 (по Виноградову П.)

Магические квадраты

Простым числам посвящено множество занимательных математических задач в применении квадратных матриц – магических квадратов, у которых суммирование элементов по любой строке, любому столбцу и двум главным диагоналям дает одно и то же число. Первый из них была придуман Генри Эрнестом Дьюдни, известным английским специалистом по головоломкам. Существуют ли магические квадраты, состоящие только из простых чисел? Оказывается, да.

Я рассмотрел магические квадраты размером 3х3, 4х4. Определил сумму вдоль каждой строки, каждого столбца и каждой главной диагонали каждого из этих квадратов.

Решение: Вдоль каждой строки, столбца и главной диагонали сумма чисел одна и та же.

1	67	43
7	13	61
73	31	7

3	61	19	37
43	31	5	41
7	11	73	29
67	17	23	13

1. 2.

1.Магический квадрат размером 3х3: сумма 111

2. Магический квадрат размером 4х4: сумма 120

Применение закона простых чисел в различных областях

В алгоритме шифрования используется простая идея − вычисление произведения двух простых чисел легко (прямая задача), а разложение полученного в результате этой операции числа на простые множители (обратная задача) достаточно трудоемко. Задача разложения на множители числа, состоящего из 155 разрядов, требует более 35 лет непрерывной работы самого современного компьютера. Проверка на простоту усложняется с ростом величины числа и уже давно вышла за пределы физических возможностей человека: выполнить проверку простоты числа длиною в миллионы цифр можно лишь с помощью компьютеров, да и им потребуются на это годы. Знание законов позволило дать такие запатентованные технические решения защиты передачи информации, которые считались просто невозможными. Простые числа необходимы для создания шифров. Рано или поздно всякий шифр рассекречивается. Здесь ученые обращаются к одному из важнейших разделов информатики – к криптографии. Наиболее распространенным примером использования простых чисел является применение их в криптографии (шифровании данных). Самые безопасные и трудно дешифруемые методы криптографии основаны на применении простых чисел, имеющих в составе более трех сотен цифр.

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

_{ЗАКЛЮЧЕНИЕ}

В ходе работы над данной темой мне удалось расширить представление о простых числах по следующим направлениям: изучил интересные стороны развития теории простых чисел, познакомился с новыми достижениями ученых, доступные для моего понимания в этой области и практическом ее применении; ^{сформировал общее представление о способах нахождения простых чисел, освоил принцип выделения простых чисел из натурального ряда с помощью способа «Решето Эратосфена» в пределах до 100;изучил применение теории простых чисел в задачах; познакомился с применением теории простых чисел в различных областях.}

В ходе написания работы мне удалось освоить два способа получения ряда простых чисел: практический способ – отсеивание (решето Эратосфена); аналитический способ – работа с формулой (закон простых чисел).

В рамках исследования: сделал самостоятельно проверку ряда математических утверждений путем подстановки значений, получив верные математические выражения; определил ряд чисел «Двойники» и «Близнецы»; составил ряд числовых выражений, обозначенных в проблемах Ландау; проверил, что квадраты 3х3, 4х4 магические; решил задачу двумя способами на применение закона простых чисел и утверждений.

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

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

• Боро, В., Цагир Д., Рольфс Ю., Крафт Ч., Янцен Е. Живые числа –М.:Мир, 1985.

• Стройк Д. Краткий очерк истории математики -М.: Наука, 1990.

• Детская энциклопедия, Изд.2.- М.:Просвящение,1965.

• Арутюнян, Е.Б.Занимательная математика, – М.: АСТ– ПРЕСС, 1999, 368с.

• Гальперин, Г., Просто о простых числах. – М.: Квант. — № 4. — С. 9-14,38.

• Кордемский, Б.А. Математическая смекалка. — М.: ГИФМЛ, 1958. — 576 с.

• Крэндалл, Р. Простые числа. Криптографические и вычислительные аспекты. Prime Numbers: A Computational Perspective. — М.: Либроком, 2011. — 664 с. — ISBN 978-5-397-02060-2.

• Матиясевич, Ю. Формулы для простых чисел. -М.: Квант, 1975. — № 5. — С. 5-13.

14