Простые числа - долгий путь к бесконечности

ПРОЕКТ ПО ПРЕДМЕТУ МАТЕМАТИКА

ТЕМА: «ПРОСТЫЕ ЧИСЛА – ДОРОГА К БЕСКОНЕЧНОСТИ»

Выполнил:

ученик 8 класса

филиала МОУ СОШ №17 – СОШ №3

Ахмеров  Данил Адисонович

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

учитель по информатике

Мелешкина Вера Геннадьевна

г. Карталы

2016

Содержание

Введение                                                                                3

Виды чисел                                                                                4

Множество простых чисел                                                                4

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

Проверка простоты числа                                                                5

Формулы, помогающие найти некоторые простые числа                        6

Заключение                                                                                7

Приложения                                                                                 8

Список использованной литературы                                                15

Введение

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

Так же попытки найти простые числа ведут к появлению новых инструментов для расчётов, в особенности для работы с компьютером. Так же имея большой список простых чисел можно проверить не доказанные теоремы, так как если кто-то выдвигает гипотезу относительно простых чисел, но оказывается, что одно число среди миллионов натуральных чисел нарушает её, то гипотеза является ложной. Это стимулирует поиск простых чисел различного вида, таких как: простые числа Мерсенна (Приложение 8), простых палиндромов (Приложение 5), простых чисел близнецов (Приложение 4), и так далее. Такие поиски иногда превращаются в соревнование, за победы в котором присуждаются большие призы.

Виды чисел

Составными числами называются числа, которые являются произведением двух натуральных чисел больше единицы. Примеры составных чисел: 4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 22, 24, 25, … [4]

Простыми числами называют числа, которым кратны только два целых числа (единица, и само число). Число 1 не относится ни к простым, ни к составным числам, а число 2 является единственным чётным простым числом (Приложение 1).

Чётными числами называют числа кратные числу 2. Например: 2, 4, 6, 8, 10, …

Полупростые числа, это числа, которые являются произведением двух простых чисел (Приложение 2).

Множество простых чисел

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

Продвигаясь по ряду натуральных чисел, могу заметить, что среди больших чисел, простые числа попадаются всё реже. Может показаться, что со временем, простые числа больше не будут появляться в ряду натуральных чисел. На самом деле множество простых чисел бесконечно. Евклид доказал, что, если взять ряд последовательности простых чисел (любой длинны, начиная с двойки), перемножив все числа ряда и прибавив к результату единицу, можно получить простое или полупростое число, множителей которых не было в изначальном ряду простых чисел (Приложение3). Новый список, полученный после перемножения изначального, всё же будет не полным [1].

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

Изучив простые числа, замечу, что среди них есть такие числа, которые находятся очень близко друг к другу, и между этими простыми числами, стоит одно (чётное) число. Такие числа называют «Простыми числами-близнецами».

Так как по мере увеличения ряда натуральных чисел, простые числа попадаются всё реже, числа-близнецы всё же можно найти среди больших чисел (Приложение 4).Но доказать, что множество простых чисел-близнецов бесконечно, никому не удавалось [1].

Ещё есть числа, которые читаются одинаково как с права на лево, так и слева на право. Такие числа называются палиндромами (Приложение5).

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

Есть несколько способов проверить, является ли натуральное число простым. Но при проверке довольно больших чисел понадобится очень много времени. Самый простой способ – поочерёдно пытаться делить число на простые числа, начиная с двойки. Если ни одно простое число меньше квадратного корня изначального числа не делит его нацело, можно утверждать, что число является простым [1].

Замечу, что есть ещё более простой способ проверки простого числа. По малой теореме Ферма (Приложение 6). Однако если число проходит тест, нельзя быть уверенным, что оно является простым, основание числа “” в таком случае называют ложным, и продолжают делать проверку со следующим взаимно простым с “p” числом. Вероятность обнаружения ложного числа уменьшается на ½ с каждой проверкой.

Так же существуют составные числа, которые проходят тест. Такие числа были обнаружены математиком Робертом Кармайклом. Существует всего 16 чисел Кармайкла, меньших 100000, а именно: 561, 1105, 1729, 2465, 2821, 6601, 8911, 10585, 15841, 29341, 41041, 46657, 52633, 62745, 63973, 75361. На сегодняшний день известно только 2163 таких числа, они находятся среди 25 миллиардов натуральных чисел [7].

Формулы, помогающие найти некоторые простые числа

Всё же известны формулы, с помощью которых можно найти простые или полупростые числа. Но существующие формулы, такие как: простые числа Ферма (Приложение 7), простые числа Мерсенна (Приложение 8), простые числа Прота (Приложение 9) и другие, не могут найти большинство простых чисел.

Для нахождения всех простых чисел до числа “n”, можно использовать: решето Эратосфена (Приложение 10), и геометрическое решето Матиясевича-Стечкин (Приложение 11). Но для большого числа “n”, поиск простых чисел окажется очень трудным и долгим занятием.

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

Заключение

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

Существует не мало геометрических моделей для поиска простых чисел. Иногда они вводят в заблуждение неопытных новичков, так как представлены в виде формул, по которым можно найти любое простое число. Но в действительности эти модели являются не более чем решетом Эратосфена, или другим представлением решета с помощью геометрических методов. Хотя некоторые из них всё же гениальны [1].

Приложения

Приложение 1 [2]

Таблица простых чисел до 1000

Приложение 2 [5]

   Таблица произведений простых чисел (до 47*47)

Приложение 3

По теореме Евклида, возьмём ряд простых чисел до десяти, и перемножим их:

2 ⋅ 3 ⋅ 5 ⋅ 7 = 210, и добавим к полученному числу единицу, получится - 211, данное число является простым.

Попробуем перемножить более длинный ряд простых чисел, например, до 13.

2 ⋅ 3 ⋅ 5 ⋅ 7 ⋅ 11 ⋅ 13 + 1 = 30031, число является полупростым, так как его можно разложить на два простых множителя – 59 и 509 [9].

Приложение 4

Парные простые числа могут быть описаны выражением «p,p + 2», где p – простое число. Все пары простых чисел-близнецов из первой тысячи:

(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), (227, 229), (239, 241), (269, 271), (281, 283), (311, 313), (347, 349), (419, 421), (431, 433), (461, 463), (521, 523), (569, 571), (599, 601), (617, 619), (641, 643), (659, 661), (809, 811), (821, 823), (827, 829), (857, 859), (881, 883).

Самыми большими известными числами-близнецами, открытыми в 2009 году, являются числа 65516468355 ⋅2333333  - 1 и 65516468355 ⋅2333333  + 1, каждое из которых состоит из 100355 цифр [1].

Приложение 5[6]

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

Все простые палиндромы за исключением числа 11, имеют не чётное количество цифр [3]. Список первых простых палиндромов:

2, 3, 5, 7, 11, 101, 131, 151, 181, 191, 313, 353, 373, 383, 727, 757, 787, 797, 919, 929, 10301, 10501, 10601, 11311, 11411, 12421, 12721, 12821, 13331, 13831, 13931, 14341, 14741, 15451, 15551, 16061, 16361, 16561, 16661, 17471, 17971, 18181, …

Приложение 6

Малая теорема Ферма гласит, что для простого числа “p”и числа “”, взаимно простого с числом “p”,  разность «p-» делится на “p”.

Пример: Пусть  = 8, и p = 3,        тогда 83 – 8 = 504, 504 / 3 = 168, число 3 является – простым. Так как число 3 является простым, то при продолжении тестирования его с помощью теоремы Ферма, оно всегда будет делить число «p-».

Попробуем проверить составное число. Пусть =2, а p=9, тогда 29 – 2 = 510, 510 не делится на 9, отсюда следует, что число 9 не является простым.

Доказательство малой теоремы Ферма:

Предложим, что теорема верна для некоторого натурального числа “”, за тем покажем, что оно также верно для числа  + 1.

Согласно биномиальному разложению Ньютона,        

 ( + 1)p = p +  + + … + .

Перенося члены pи 1 на лево, мы получим:

        (+1)p -  –  1 =  +  + … + .

Множитель pприсутствует во всех слагаемых в правой части, по этому правая часть уравнения делится на pи, следовательно, левая часть, ( + 1)p- p– 1, тоже делится на p.

Так как по индукции– делится на p, то и ( + 1)p тоже делится на p:                               [( + 1)p -  – 1] + - = ( + 1)p – ( + 1)

Следовательно, делимость на p так же верна в случае  + 1, то есть теорема доказана [1].

Приложение 7

Формула Ферма гласит, что числа являются простыми в , где “n” не отрицательное натуральное число.

Числа Ферма для n = 0, 1, 2, 3, 4 – образуют последовательность: 3, 5, 17, 257, 65537 [9].

Изучение чисел этого вида начал Ферма, и он выдвинул гипотезу, что все они простые. Однако гипотеза была опровергнута Эйлером в 1732 году, нашедшим простые множители числа F5 = 4294967297 = 641 ⋅ 6700417.

Приложение 8

Величайшей математической работой Мерсенна является тракт «Физико-математические размышления» 1644 года, в котором появились простые числа, названные его именем.

Во введении написано, что числа вида «2p – 1» являются простыми если “p” имеет, одно из следующих значений: 2, 3, 5, 7, 13, 17, 19, 31, 67, 127, 257.

Однако если число 2 возвести в степень 257, получится число состоящее из 77 цифр, до сих пор не известно, как Мерсенну удалось доказать, что полученное число является простым, используя методы вычисления своего времени.

Но прошло 100 лет, прежде чем Эйлеру удалось доказать, что число 231 – 1 является простым. А в 1947 году был получен полный список:                                         p = 2, 3, 5, 7, 13, 17, 19, 31, 51, 89, 107, 127.                        

Он показывает, что изначальный список Мерсенна содержал два не правильных числа, и в нём не хватало ещё трёх [1].

Приложение 9

Числами Прота являются числа вида «k ⋅ 2n + 1», где k является не чётным положительным числом, и n– положительным числом, причём k< 2n [10].

Числа Прота, образуют последовательность: 3, 5, 9, 13, 17, 25, 33, 41, 49, 57, 65, 81, 97, 113, 129, 145, 161, 177, 193, 209, 225, …

А простые числа Прота, образуют последовательность: 3, 5, 13, 17, 41, 97, 113, 193, 241, 257, 353, 449, 577, 641, 673, 769, 929, 1153, 1217, 1409, 1601, 2113, 2689, 2753, 3137, 3329, 3457, 4481, 4993, 6529, 7297, 7681, 7937, 9473, 9601, 9857, …

Простота чисел Прота проверяется с помощью теоремы Прота, которая утверждает, что число p является простым, только если существует цело число , для которого справедливо сравнение: (modp).К 2012 году, самым большим простым числом Прота является 19249 ⋅ 213018586 + 1.

Приложение 10[1]

Удобный способ поиска простых чисел до числа n, называется решетом Эратосфена. Для того чтобы начать поиск простых чисел, нужно нарисовать таблицу всех чисел, до числа n. Например, если число n = 100: сразу вычеркнем единицу, так как не является не простым не составным числом. Дальше вычеркнем все числа кратные двум, кроме самого числа, и так продвигаясь по ряду, игнорируя уже вычеркнутые числа, мы будем зачёркивать, числа кратные трём, пяти, семи, …. Все числа, которые не были вычеркнуты из таблицы, являются простыми.

Приложение 11

Геометрическое решето, построенное советскими математиками -Матиясевичом, Юрием Владимировичем (родился второго марта 1947 года, в Ленинграде), и Сергеем Борисовичем Стечкином (6 сентября 1920, Москва – 22 ноября 1995, Москва), позволяет найти любое простое число.

Чтобы его построить, начертим параболу x = y2; Отметим положительные числа “a”(числа - 2, 3, 4…) и “b”(числа - 2, 3, 4…) на оси OY, получим точки, -aи b. Проведём прямую до параболы, и получим точки с координатами (-a , a2) и (b , b2).Соединим точки, отмеченные на параболе отрезками. Как мы видим, отрезки не пересекают точки, отмеченные простыми числами на оси OX [8].

Приложение 12

        Программа на языке “Pascal”, для генерации простых чисел до 10000:

program abc;

var

  i, j:integer;

  pr:boolean;

begin

  writeln('Простые числа в диапазоне от 1 до 10000: ');

  for i := 2 to 10000 do

  begin

    pr := true;

    for j := 2 to i div 2 do

      if i mod j = 0 then

      begin

        pr := false;

        break;

      end;

    if pr then

      write(i, ' ');

  end;

  writeln;

end.

Список использованной литературы

1. Энрике Грасиан, «Простые числа», Москва – 2014г., DeAGOSTINI.
2. Простые числа: https://ru.wikipedia.org/wiki/%D0%9F%D1%80%D0%BE%D1%81%D1%82%D0%BE%D0%B5_%D1%87%D0%B8%D1%81%D0%BB%D0%BE
3. Список простых чисел: https://ru.wikipedia.org/wiki/%D0%A1%D0%BF%D0%B8%D1%81%D0%BE%D0%BA_%D0%BF%D1%80%D0%BE%D1%81%D1%82%D1%8B%D1%85_%D1%87%D0%B8%D1%81%D0%B5%D0%BB

4. Составные числа: https://ru.wikipedia.org/wiki/%D0%A1%D0%BE%D1%81%D1%82%D0%B0%D0%B2%D0%BD%D0%BE%D0%B5_%D1%87%D0%B8%D1%81%D0%BB%D0%BE
5. Полупростые числа: https://ru.wikipedia.org/wiki/%D0%9F%D0%BE%D0%BB%D1%83%D0%BF%D1%80%D0%BE%D1%81%D1%82%D0%BE%D0%B5_%D1%87%D0%B8%D1%81%D0%BB%D0%BE
6. Числа палиндромы: http://www.nkj.ru/archive/articles/17984/
7. Малая теорема Ферма: https://ru.wikipedia.org/wiki/%D0%9C%D0%B0%D0%BB%D0%B0%D1%8F_%D1%82%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%A4%D0%B5%D1%80%D0%BC%D0%B0
8. Геометрическое решето: http://pandia.ru/text/78/227/26249.php
9. Числа Ферма: https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%A4%D0%B5%D1%80%D0%BC%D0%B0
10. Простые числа Прота: https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%BE_%D0%9F%D1%80%D0%BE%D1%82%D0%B0

Слайд 2

Вся наша жизнь связанна с числами. Существуют виды чисел: Чётные, нечётные, простые, полупростые, составные. Из уроков математики мы знаем, что числовой ряд бесконечен.

Слайд 3

Поэтому тема моего проекта: Простые числа – дорога к бесконечности.

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

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

Слайд 4

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

Слайд 5

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

Слайд 6

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

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

Ещё есть числа, которые читаются одинаково как справа на лево, так и слева направо. Такие числа называются палиндромами.

Слайд 7

Есть несколько способов проверить, является ли натуральное число простым. Но при проверке довольно больших чисел понадобится очень много времени. Самый простой способ – поочерёдно пытаться делить число на простые числа, начиная с двойки. Или другой способ – проверки простоты числа по малой теореме Ферма.

Слайд 8

Но существуют составные числа, которые проходят тест по малой теореме Ферма. Такие числа были обнаружены математиком Робертом Кармайклом. На сегодняшний день известно только 2163 таких числа, они находятся среди 25 миллиардов натуральных чисел.

Слайд 9

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

Слайд 10

Для поиска всех простых чисел до числа “n”, можно использовать: решето Эратосфена, Слайд 11и геометрическое решето Матиясевича-Стечкина. Но для большого числа “n”, поиск простых чисел окажется очень трудным и долгим занятием.

Слайд 12

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

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