Эти непростые простые числа – Эти непростые простые числа. | Социальная сеть работников образования

Содержание

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

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

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

Созданием и анализом методов шифрования занимается наука криптография. Существует огромное количество таких методов. Например, в 1976 году американские математики Уитфилд Диффи и Мартин Хеллман выдвинули концепцию асимметричной криптосистемы, при которой шифрование и дешифрование осуществляются с помощью двух различных ключей — открытого и закрытого (секретного). Буквально через год американцы Рональд Ривест, Ади Шамир и Леонард Адлеман разрабатывают

асимметричную криптосистему RSA, названную по первым буквам фамилий её авторов (Rivest, Shamir, Adleman).

Слева направо: Ади Шамир, Рональд Линн Ривест, Леонард Макс Адлеман

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

Чтобы успешно вскрыть шифр, нужно уметь разложить числа на простые множители? Всего-то! Это может любой школьник!

Но хватит ли у вас терпения и времени разложить, например, число 1,409,305,684,859 на два простых множителя? Ответом будут простые числа 705,967 и 1,996,277. Чтобы их найти, придётся перебирать простые числа между числами 1 и 2,000,000, а их в этом списке немало — 148,933. Именно сложность обнаружения простых чисел стала причиной их широкого использования в криптографии.

Пример. Когда авторами криптосистемы RSA был объявлен конкурс на нахождение простых множителей числа, состоящего из 129 цифр, над проблемой работали около 600 математиков и 1600 добровольцев. В конце концов им удалось разложить это число на множители. Однако, чтобы взломать код из 1024 цифр, потребуется время, равное возрасту вселенной — 13,7 миллиарда лет, даже если над этим будут работать одновременно все компьютеры в мире.

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

oyla.xyz

секреты тайного общества ткачей / Habr

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

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

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

Есть множество способов оптимизации, которые намного быстрее простого перебора, однако даже если оптимизация ускорит поиск в 10 раз, достаточно увеличить число на 2 десятичных знака (т.е., в 100 раз), чтобы замедлить поиск в 100 раз.

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

К слову, математики не нашли ни доказательства, ни опровержения того, что нельзя найти алгоритм факторизации, сложность которого не была бы экспоненциально зависящей от длины числа. А доказав или опровергнув это, как верят некоторые математики, может быть получится, заодно, решить математическую проблему, известную как гипотеза Римана. За ее доказательство математический институт Клея обещает миллион долларов. Хотя может так оказаться, что задача факторизации окажется полиномиальной, но гипотезу Римана это ни докажет, ни опровергнет.

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

Идея составных чисел очень проста. Возьмем несколько натуральных чисел и перемножим их. Тем самым, мы получаем составное число.

Мы легко найдем бесконечность составных чисел, просто умножив n на 2.

То же касается умножения на 3.

Далее следует 4, но здесь мы новых чисел не найдем, все они уже равны 2n. Далее следуют 5n, потом 6n, которые нами найдены уже дважды, как 2n и 3n одновременно. Это не увеличивает количества составных чисел, но наводит нас на мысль, что закономерность составных чисел заключена в произведении простых.

Но если мы пройдем немного дальше, то обнаружим интересную закономерность: число 6 это произведение 2 и 3. Это значит, что у нас будет сразу много удобно расположенных в таблице составных чисел:

Глядя на таблицу, мы понимаем, что в строках 2, 3, 4 и 6 никогда не может быть простых чисел. А это значит, что вероятность найти простое число не может превышать 2/6. Мы понимаем, что чисел эта вероятность еще меньше, но как сильно?

Попробуем и дальше поискать удобную структуру составных чисел, а для этого, подумаем, что значит 2х3=6? Что если мы возьмем произведение из 2х3х5 за основу? Мы получаем следующую интересную таблицу (чтобы она не занимала много места, уменьшим шрифт):

Мы видим, что:
— 15 строк вида 2n,
— 5 строк вида 3n (плюс 5 вида 6n уже учтены в 2n)
— и 2 строки вида 5n (еще три вида 10n уже вычеркнуты в числах 2n и одна 15n среди строк 3n)
не могут содержать простых чисел (мы же этого и ожидали, верно?)

Остаются лишь восемь строк вида 30n + i, где i = 1, 7, 11, 13, 17, 19, 23, 29. Если приглядеться, в них можно увидеть симметрию. 1+29=7+23=11+19=13+17.

Поэтому компактно можно записать как 30n +- i, где i = 1, 7, 11, 13,17

И мы понимаем, что вероятность найти произвольное простое число не больше 8/30. На 2/30 стало меньше…

Что же дальше? Следуя логике, в следующей таблице должно быть 2х3х5х7=210 строк. Еще дальше 210х11=2310, потом 2310х13, и так мы будем последовательно перемножать простые числа, получая все большую и большую базу «строчной развертки», которая будет сохранять свою полосатость.

Это выглядит так, будто бы простые числа отбрасывают «тени» в бесконечность кратных им чисел, если их располагать в ряд соответственно базе числа, обозначим его П(i), равного последовательному произведению i простых чисел.

Можно заметить, что полоса строк, лежащих между первой и следующей, где могут содержаться простые числа, растет по очень простому закону: если строк 6, то есть 2х3, то простые числа могут быть в строке 5, если 2х3х5, то начиная со строки 7, что логично. Таким образом, в матрице с количеством строк 30 030 (2х3х5х7х11х13) после первой строки будет широкая полоса составных чисел, до строки, следующей от числа 17. А если мы возьмем матрицу на 9 699 690 строк (2х3х5х7х11х13х17х19), то полоса, где простых чисел нет, протянется до строки 21. Что характерно, из-за симметрии, внизу матрицы так же будет 20 строк с исключительно составными числами.

Но что такое эти произведения? 2х3 – это прямоугольник, площадью 6. 2х3х5 – параллелепипед, объемом 30. А дальше? 2х3х5х7 – гиперпараллелепипед в 4 измерениях, с гиперобъемом 210? А потом? 5 измерений, 6,… Бесконечность?

Только подумайте, что могли бы себе вообразить многомерный мир, в которых простые числа отбрасывают свои тени во всех измерениях…

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

Вот начальная грань:

А вот ее развертка с двух сторон:

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

Попробуем теперь развернуть картинку в четвертое измерение, в интересующую нас сторону, где можно находить простые числа:

Здесь коричневым цветом обозначены числа вида mn, которые составлены произведениями чисел от 11 до 19 (ближайшее целое, меньшее 210/11). Особенность этих чисел в том, что они сами не являясь простыми числами не «отбрасывают тени» вглубь следующего измерения.

Как мы видим, средний слой развертки снова становится тривиальным – здесь и далее простых чисел нет. А вот внешние грани гиперпаллелепипеда можно рассматривать и дальше. Каждый столбец раскладывается в матрицу 7х11, получаем 5 таких матриц для каждого из трех слоев матрицы 3х5 (здесь показана развертка одного столбца и фрагмент матрицы для второго столбца):

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

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

Но, пожалуй, наибольший интерес вызывает возможность уточнения оценки вероятности нахождения простых чисел все дальше и дальше. Если рассматривать матрицы, то мы видим, как вероятность падает, начиная с 4/6, далее до 7/24 (или усредненно 11/30), потом 36/180 (или 47/210), и т.д.

Кроме того, у автора есть алгоритм факторизации, оптимизация которого в многомерной матрице может заметно его ускорить (но он от этого не перестает иметь экспоненциальную степень сложности от количества знаков разлагаемого числа).

Сам алгоритм в основе очень прост.

Берем два последовательные нечетные числа, p и q, такие, что pq близко к X (используется округление корня из X до большего и меньшего нечетных чисел, при условии, что Х не является квадратом). Предварительно мы устраняем четность Х (делим на 2 до тех пор, пока результат четный), получая множитель 2^K. Далее же, в цикле, проверяем разницу между Х и pq. Если она равна нулю – результат получен. Если она больше нуля, мы уменьшаем q на 2. Если меньше нуля, увеличиваем p на 2q. В цикле используется только сложение, поэтому алгоритм довольно быстрый (зависит лишь от реализации функций работы с BigInteger).

Однако, у автора есть гипотеза, что шаг пересчета можно значительно увеличить, не теряя в аккуратности, если использовать базу кратности. Всякое число Х находится между двумя последовательными П(i) и П(i+1), где П(i) – произведение первых i простых чисел, поэтому можно определить, к какому из ребер число Х находится ближе и какой диапазон свободы у p и q в каждой из проекций) и тем самым образуемый p и q прямоугольник из одной плоскости развернуть в сечение гиперпараллелепипеда.

P.S. А при чем здесь тайное общество ткачей, спросит читатель, которого привлек оригинальный заголовок? Возможно, читатель помнит фильм «Особо опасен» В этом году обещают даже продолжение… В этом фильме ткацкий станок делает предсказания, укладывая нити и узелки… Посмотрите, как похоже это делают ниточки простых чисел…

В матрице 30х7:

И кусочек матрицы 210х11:

А управляют узелками этой машиной вот такие матрицы-перфокарты. Развертка матрицами 2х3:

И побольше, матрицами 6х5:

habr.com

Проект «Непростые задачи с простыми числами» 6 класс

Проект «Непростые задачи с простыми числами»

Содержание

Введение …………………………………………………………..4

Основная часть

Глава 1

1. Определение простых чисел …………………………………….6

1.1. Поиск простых чисел…………………………………………… 7

1.2. Числа — близнецы ………………………………………………….. 9

Глава 2.

2. Из истории простых чисел…………………………….. 10

2.1. Алгоритм Евклида…………………………………………10

2.2. Простые числа Мерсенна……………………………… 11

2.3. Простые числа Ферма…………………………………….12

2.4. Открытие Пафнутия Львовича Чебышева…………..13

2.5. Проблема Гольдбаха………………………………………15

Глава 3.

Задачи на НОК и НОД………………………………………… 17

Заключение. Выводы ……………………………………….22

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

Приложения ………………………………………………………24

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

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

Введение.

В этом учебном году на уроках математики мы познакомились с темой » Простые числа». Мы узнали, что числа бывают простые и составные.

Учитель объяснил нам принцип нахождения простых чисел. Представил нашему вниманию таблицу простых чисел до 997, помещённую на форзаце учебника » Математика 6 класс», которой мы пользовались в ходе выполнения упражнений и заданий, и нас настолько заинтересовала это тема, что мы решили ее исследовать.

При изучении научной литературы, мы наткнулись на интересное объяснение простых чисел.

О простых числах начнем рассказ с воображаемого путешествия из класса — в мировое пространство.

Это воображаемое путешествие придумал известный советский педагог — математик профессор Иван Кузьмич Андронов «…мысленно возьмем прямолинейный провод ,выходящий из классной комнаты в мировое пространство, пробивающий земную атмосферу, уходящий туда, где луна совершает вращение, и далее — за огненный шар Солнца, а далее — в мировую бесконечность;

* Мысленно подвесим на провод, через каждый метр электрические лампочки, нумеруя их, начиная с ближайшей:

1,2,3,4,…100,…,1000,…,100000,…;

* Мысленно включим ток с таким расчётом, что бы загорелись все лампочки с простыми номерами и только с простыми номерами;

* Мысленно полетим вблизи провода. Перед нами развернётся следующая картина: лампочка с номером 1 не горит. Почему? Потому, что 1 не является простым числом.

Две следующие лампочки с номерами 2 и 3 горят, т .к. 2 и 3 – оба простых числа. Почему? Всякое простое число кроме 2-есть число нечетное, а соседние с простым по ту и другую сторону будут числа — четные. Всякое четное, отличное от 2,является составным числом, т.к. делится на 2.

Далее наблюдаем пару лампочек, горящих через одну, с номерами 3 и 5, 5и7,т.д. Замечаем, что в дальнейшем они встречаются реже, все пары простых чисел имеют вид 6п+1;

Например: 6*3-1=17 и 6*3+1=19

6*5-1=29 и 6*5+1=31

6*20-1=119 и 6*20+1=121 — это пара не простые числа — это составные числа. Долетаем до пары 10016957 и 100169559 — это простые числа. Будут ли и дальше такие пары простых чисел? Современная наука пока ответа не даёт; неизвестно существует ли конечное или бесконечное множество пар простых чисел.

* Но вот начинает действовать закон большого промежутка заполненного только составными числами: летим в темноте, смотрим назад — темнота, и впереди не видно света. Вспоминаем свойство, открытое Евклида, и смело движемся вперед, т.к. впереди должны быть светящиеся лампочки и впереди их должно быть бесконечное множество.

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

Глава 1

1. Определение простых чисел

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

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

6=2*3, 9=3*3, 30=2*15=3*10

В то время как другие, например 3,7,13,37,не могут быть разложены подобным образом.

Определение. Простым называется число, которое делится только само на себя и на единицу.

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

В Казанском университете профессор Никольский с помощью единицы умудрился доказать существование Бога. Он говорил: « Как не могут существовать числа без единицы, так и вселенная без единого Владыки существовать не может ».

Единица и в самом деле — число уникальное по свойствам: она делится только сама на себя, но любое другое число на неё делится без остатка, любая её степень ровна тому же самому числу — единице. После деления на неё ни одно число не изменяется, а если и поделить любое число на само себя, получится опять же единица!

1 : 1 =1; а : 1=а; 1ⁿ=1*1*1….; а : а =1

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

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

У Эйлера учились все — и в Западной Европе, и в России. Диапазон его творчества широк: дифференциальное и интегральное исчисление, алгебра, механика, диоптрика, артиллерия, морская наука, теория движение планет и Луны, теория музыки — всего не перечислить. Во всей этой научной мозаики находится и теория чисел. Эйлер отдал ей немало сил и немалого добился.

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

Доказано, например, что число простых чисел неограниченно, т.е.: — нет самого большого простого числа;- нет последнего простого числа, после которого все числа были бы составными.

Первое доказательство этого положения принадлежит ученым древней Греции (V — III вв. до н.э.), второе доказательство — Эйлеру (1707-1783).

1.1. Поиск простых чисел. РЕШЕТО ЭРАТОСФЕНА.

Эратосфе́н Кире́нский

Для отыскания простых чисел греческий математик Эратосфен придумал такой способ. Он записал все числа от одного до какого – то числа, а потом вычеркнул единицу, которая не является ни простым, ни составным числом, затем вычеркнул через одно все числа, идущие после 2 (числа, кратные двум, т.е. 4, 6, 8 и т.д.).

Первым оставшимся числом после 2 было 3. Далее вычёркивались через два все числа, идущие после трёх (числа, кратные 3, т.е. 6, 9, 12, и т.д.) в конце концов, оставались не вычеркнутыми только простые числа.

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

Так как греки делали записи на покрытых воском табличках или на натянутом папирусе, а числа не вычеркивались, а выкалывали иглой, то таблица в конце вычислений напоминало решето. Поэтому метод Эратосфена называют «Решетом Эратосфена»: в этом решете «отсеиваются» простые числа от составных. Таким путем Эратосфен составил таблицу простых чисел до 1000 (таблица простых чисел в учебнике «математики 6 класс»). Эта таблица получила название «Решето Эратосфена».

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

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

1.2. Числа — близнецы

Среди простых чисел встречаются так называемые «близнецы» или пары простых чисел, разница между которыми составляет двойку (например, 11и 13). Именно эти пары чисел в таблице учебника выделены другим цветом.

«Близнецы» появляются с некой периодичностью, причём, чем больше числа, тем реже они встречаются (11и 13; 17 и 19; 29 и 31; 41 и 43; 59 и 61). То же происходит и с обычными простыми числами. В числах, близких к триллиону, лишь каждое 28 число является простым.

Ещё Евклидом было доказано, что простых чисел бесконечно много. Однако окончательного ответа на вопрос, конечно или бесконечно множество «близнецов», пока не существует.

Двое учёных утверждали, что нашли ключ к доказательству одной из самых знаменитых математических гипотез. Согласно ей, существует бесконечно много пар простых чисел, разность между которыми равна двум — так называемых чисел-близнецов. Это утверждение является одним из следствий фундаментальной гипотезы Римана, имеющей непосредственное отношение к современной криптографии.

Простые числа-близнецы это пара простых чисел, отличающихся на 2.

Все пары простых чисел-близнецов, кроме (3,5) имеют вид 6n ⁺_—1.

Действительно. Рассмотрим, например: 59 и 61. 59=6*10-1; 61=6*10+1.

Первые простые числа-близнецы:

(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).

Глава 2.

2. Из истории простых чисел

2.1. Алгоритм Евклида

Евклид

Простыми числами занимался и древнегреческий математик Евклид (IIIв. до н.э.). В своей книге «Начала», бывшей на протяжении двух тысяч лет основным учебником математики, доказал, что простых чисел бесконечно много, т.е. за каждым простым числом есть ещё большее простое число.

Отсюда следует гипотеза: мы можем найти простое число больше 997. Но предел простого числа не сумеем найти, т.к. они бесконечны.

В общем виде алгоритм Евклида выглядит так:

НОД (a; b)=НОД (b;r)=НОД (г₁;г₂)=…=НОД (r_n_;r_n+1)

a=bq₁+r₁

b=r₁q₂+r₂

r₁=r₂q₃+r₃

r_n=r_k+1*q_k+2+r_k+2

r_m=r_p+1*q_p+2+0

НОД ( a;b)=г_m,

Например, вычислим НОД (7975;2885) с помощью алгоритма Евклида. 7975=2585*3+220; 2585=220*11+165; 220=165*1+55; 165=55*3 НОД (7975;2585)=55, где 55 последний остаток от деления 7975 на 2885.

2.2. Простые числа Мерсенна

Марен Мерсенн

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

Среди простых чисел особую роль играют простые числа Мерсенна – числа вида М_р=2^р-1. Они называются простыми числами Мерсенна по имени французского монаха Мерена Мерсенна (1588-1648), одного из основателей Парижской Академии наук,который долго занимался проблемой простых чисел.

Если вычислять числа по этой формуле, получим:

М₂=2²-1=3 – простое;

М₃=2³-1=7 — простое;

……………………………..

М₇=2⁷ -1=127 – простое;

……………………………

М₁₁=2¹¹-1=2047.

Общий способ нахождения простых больших чисел Мерсенна состоит в проверке всех чисел М_p для различных простых чисел p. Эти числа очень быстро увеличиваются и столь же быстро увеличиваются затраты труда на их нахождение.

В исследовании чисел Мерсенна можно выделить раннюю стадию, достигшую своей кульминации в 1750г., когда Эйлер установил, что число М₃₁ является простым. К тому времени было найдено восемь простых чисел Мерсенна: p=2, p=3, p=5, p=7, p=13, p=17, p=19, p=31. Эйлерово число М₃₁ оставалось самым большим из известных простых более ста лет.

В 1876г французский математик Лукас установил, что огромное число М₁₂₇– с 39 цифрами – простое. 12 простых чисел Мерсенна были вычислены с помощью только карандаша и бумаги, а для вычисления следующих уже использовались механические настольные счётные машины.

Появление вычислительных машин с электрическим приводом позволило продолжить поиски, доведя их до P=257.

Однако результаты были неутешительными, среди них не оказалось новых простых чисел Мерсенна. Затем задача была предложена на ЭВМ. Самое большое известное в настоящее время простое число имеет 3376 цифр. Это число было найдено на ЭВМ в Иллинойском университете (США). Математический факультет этого университета был так горд своим достижением, что изобразил это число на своём почтовом штемпеле, таким образом, воспроизводя его на каждом отсылаемом письме для всеобщего обозрения.

2.3. Простые числа Ферма

Пьер де Ферма

Существует ещё один тип простых чисел с большой интересной историей. Они были впервые введены французским юристом Пьером Ферма (1601-1665), который прославился своими выдающимися математическими работами. Первыми простыми числами Ферма были числа, которые удовлетворяли формуле F_n=2^m+1, где m=2ⁿ

F₀=2^m+1=3, где m=2⁰

F₁=2^m+1=5, где m=2¹

F₂=2^m+1=17, где m=2²

F₃=2^m+1=257, где m=2³

Однако это предположение было сдано в архив не оправдавшихся математических гипотез, но после того, как Леонард Эйлер сделал ещё один шаг и показал, что следующее число Ферма P₅=6416700417 является составным.

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

Однако ни одного простого числа Ферма не было найдено, и сейчас многие математики склонны считать, что их больше нет.

2.4. Открытие Пафнутия Львовича Чебышева

Чебышев Пафнутий Львович

Итак, число простых чисел бесконечно. Мы уже видели, что простые числа, размещаются без какого — либо порядка. Проследим более подробно.

2 и 3 — простые числа. Это единственная пара простых чисел, стоящих рядом.

Затем идут З и 5,5 и 7, 11и 13, 17и19 и т.д. Это так называемые смежные простые числа или близнецы. Близнецов много: 29 и 31, 41 и 43, 59 и 61,71 и 73, 101 и 103, 827 и 829 и т. д. Самая большая известная пара близнецов такая: 10 016 957 и 10 016 959.

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

Как же распределены простые числа в натуральном ряду, в котором не будет ни одного простого числа? Есть ли какой-нибудь закон в их распределении или нет?

Если есть, то какой? Но ответ на эти вопросы не находился более 2000 лет.

Первый и очень большой шаг в разрешении этих вопросов сделал великий русский учёный Панфутий Львович Чебышев. В 1850г. он доказал, что между любым натуральным числом (не равным 1) и числом, в два раза большего его (т. е. между n и 2n) , находится хотя бы одно простое число.

Проверим это на несложных примерах.

Примем для п несколько произвольных значений п и найдём соответственно значение 2n :

n= 5, 2n=10 n=12, 2n= 24 n=37, 2n= 74 n=61, 2n=112

Мы видим, что для рассмотренных примеров теорема Чебышева верна. Чебышев доказал её для любого случая, для любого п. Открытый Чебышевым закон распределения простых чисел был поистине фундаментальным законом в теории чисел после закона, открытого Евклидом, о бесконечности количества простых чисел. Едва ли не самый добрый, самый восторженный отклик на открытие Чебышева пришёл из Англии от известного математика Сильвестр: «…Дальнейших успехов теории простых чисел можно ожидать тогда, когда родится некто, настолько превосходящий Чебышева своей проницательностью и вдумчивостью, насколько Чебышев превосходит этими качествами обыкновенных людей».

Более чем полвека спустя немецкий математик Э.Ландау, крупный специалист в теории чисел, добавил к этому высказыванию следующее: « Первым после Евклида Чебышев пошёл правильным путём при решении проблемы простых чисел и достиг важных результатов».

2.5. Проблема Гольдбаха

Иван Матвеевич Виноградов

Выпишем все простые числа от 1 до 50:

2,3,5,7,9,11,17,19,23,29,31,37,41,43,47,

А теперь попытаемся любое число от 4 до 50 представить в виде суммы двух или трёх простых чисел. Возьмём несколько чисел наугад:

50=47+3 46=43+3 32=29+3 22=19+ 3 18=13+5

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

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

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

«всякое число, больше единицы, является суммой не более трёх простых

чисел»

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

Но решение её, и почти и полностью, было найдено в 1937г. советским математиком И.М. Виноградовым.

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

За заслуги в области математики И.М. Виноградов всеми учеными мира признан одним из первых математиков современности.

Глава 3.

Задачи на НОК и НОД

Как НОК и НОД чисел помогают решать интересные разнообразные задачи?

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

При исследовании вопроса об использовании НОК и НОД чисел я распределил все задачи на следующие группы:

решение текстовых задач;
задачи на сократимость дробей;
задачи на вычисление НОК и НОД чисел;
решение уравнений;

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

Задачи на сократимость дробей можно решить несколькими способами:

Разложением на множители числителя и знаменателя;
Применение алгоритма Евклида;
На основе свойств НОК и НОД чисел;
Выделение целой части непосредственным делением числителя на знаменатель дроби.

Вычисление НОК и НОД чисел осуществляется на основе разложения чисел на простые множители и использовании свойств НОК и НОД чисел можно найти, используя алгоритм Евклида.

При решении уравнений нужно постараться применить метод разложения на множители, и сделать перебор возможных случаев. При решении систем уравнений постараться, как и в уравнениях осуществить разложение на множители в виде произведения двух натуральных чисел вида dn и dm, где а =dn, b= dm, где d-делитель чисел a и b, m и n –взаимно простые числа и, используя общие методы решения систем, а также свойства НОК и НОД чисел найти соответствующие пары решений системы. Напомним определение понятий и некоторые свойства.

Определение.

Число c называется наибольшим общим делителем для чисел a и b, если оно является наибольшим делителем и для числа a, и для b.

НОК (a; b)= c, a, b, c €N

Число c называется наименьшим общим кратным чисел a и b, если оно является наименьшим из чисел, кратных как для a, так и для b.

НОК (a; b) = c; a, b, c € N

Пример 1: Найдём НОД (16;24). Раскладываем числа 16 и 24 на простые множители.

16=2⁴ 24=2³*3 16=2*2*2*2* 24=2*2*2*3 НОД(16;24)=8

Пример 2: Найдём НОК (63;18).Раскладываем числа 63 и 18 на простые множители. 63=7*3*3 18=2*3*3 Возьмём любое из чисел и умножим на число недостающее этому числу. 63=3*3*7 18=3*3*2

НОК(63;18)=3*3*7*2=9*7*2=63*2=126 Для НОД и НОК чисел соответствуют некоторые утверждения:

Если a и b€N, причём a: b, то НОД (a: b)=b, a НОК (a; b)=a.
Если а и b€N такие, что a>b, то НОД (a; b)=НОД (a- b; b).
НОД (a; b)=ab.

На первых двух утверждениях основывается алгоритм Евклида.

Некоторые свойства НОД и НОК чисел.

Любое общее кратное чисел (€N) делится на НОК чисел.
Если НОК (a;b)=k и m€N, то НОК (am;bm)=bm.
Если НОД (a;b)=d то НОК (a/d;b/d)=k/d.
Если a:c и b:c, то ab/c — общее кратное чисел a и b.
Для любых a и bЭN выполняется равенство НОД (a;b) НОК (a;b)=ab.
Любой общий делитель чисел a и b являются делителем НОД (a; b).
Утверждения 1-3.
Если числа a и b разделить на НОД (a;b) они будут взаимно просты.
Если НОД (a;b)=1, то НОД (ac; b)=НОД (c; b),c- натуральное.
Справедливо НОД (a;b)=НОД (a+mb, b),где m-целое число.
Чтобы найти НОК (a. b, c.. .k) можно: обозначить НОК (a;b)=М₁НОКТ (М, с)=М_2….НОК (М; к)= М_n_-1 ,то НОК (a, b, c,….k)=M_n_-1

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

Определение.

Число а, которое имеет только 2 делителя: 1, а (не больше) называется простым.

Число а, которое имеет 3 делителя и более называется составным.

Например, 3-простое т.к. имеет 2 делителя: 1,3.

А число 18-составным т.к. имеет 6 делителей: 1,2,3,6,9,18.

Свойства:

Пусть a и b взаимно просты, то НОД (a; b)=1
Пусть a и b взаимно просты, то НОК (a; b)=ab
Два простых числа взаимно просты.
Пусть a-простое, b-составное и b не кратно a, то НОД (a;b)=1, НОК (a;b)=ab
Пусть a-простое, b-составное b<a,то НОД (a;b)=1, НОК (a;b)=ab

Любые 2 последовательных числа взаимно просты.

*Решение текстовых задач с помощью НОК и НОК чисел.

№1

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

Решение: Очевидно, нужно найти НОД (56;72) 56=2*2*2*7; 72=3*3*2*2*2 НОД (56;72)=8 Скорость равна 8 км/ч Ответ: 8 км/ч.

№2 На столе лежат книги, число которых меньше, чем 100. Сколько лежит книг, если известно, что их можно связывать пачки по 3, по 4, и по 5 штук?

Решение: Очевидно, нужно найти НОК (5;4;3) НОК (5;4;3)=3*4*5=3*20=60. Ответ: 60 штук.

№3 Теплоход «Суворов» свой рейс туда и обратно совершает за 8 дней, теплоход «Горький» за 12 дней, а теплоход «Киров» за 18 дней. Через сколько дней теплоходы снова встретятся в порту, если они ушли в рейс одновременно?

Решение: Найдём НОК (8;12;18), для этого разложим на множители числа 24=2х2х2х2х3, 18=2х3х3. Имеем: НОК (8;12)=24, а НОК (8;12;18)=НОК (24;18)=24х3=72 (дня). Ответ: теплоходы встретятся через 72 дня.

№4 В детском велосипеде шестерня заднего колеса имеет 21 зубец, а шестерня педали 44 зубца. Какое наименьшее число оборотов должна сделать педаль, чтобы шестерни вернулись в своё первоначальное положение?

Решение: Очевидно, нужно найти НОК (21;44). 21=3*7; 44=2*2*11. НОК (21;44)=924. Так как задача указывает на обороты педали, а не шестерни колеса, то 924:44=21 (оборот). Ответ: наименьшее число оборотов равно 21.

№5 Два автобуса одновременно отпраляются от одной площади по разным маршрутам. У одного рейс туда и обратно длится 48 минут, а у другого 1 час 12 минут. Через сколько времени автобусы снова встретятся на этой площади?

Решение: Найдём НОК (48;72). 48=2*2*2*2*3, 72=2*2*2*3*3, НОК (48;72)=2*2*2*2*3*3=144 (минуты). 144 минуты =2 часа 24 минуты. Ответ: автобусы снова встретятся на этой площади через 2 часа 24 минуты.

№6 Саша ходит в бассейн один раз в три дня, а Вася один раз в четыре дня, Ваня-в 5 дней. Они встретились в бассейне в этом понедельник. Через сколько дней и в какой день недели они встретятся снова?

Решение: Чтобы узнать через сколько дней они встретятся нужно найти НОК (3;4;5). Так как числа имеют только один общий делитель равный 1, то наименьшее общее кратное равно их произведению, есть НОК (3;4;5)=60 (дней). Так как они встретятся только в один день количество дней в неделю, то есть 60:7=8 (ост.4). Понедельник, вторник, среда, четверг, пятница, суббота, воскресенье.

0 1 2 3 4 Ответ: ребята встретятся через 60 дней, в пятницу.

№7 Если участники демонстрации построятся по 10 человек в ряд, то 1 человек останется лишним. Если они построятся по 9 человек в ряд, то опять один человек останется лишним. То же самое произойдёт, если они построятся по 8,7,6,5,4,3 и, наконец, по 2 человека в ряд. Всего их меньше 5 тысяч. Сколько их?

Решение: Пусть х-число демонстрантов. Число (х-1) делится на 2,3,4,5,6,7,8,9. Поэтому (х-1) кратно НОК чисел 2,3,4,5,6,7,8,9. НОК (2,3,4,5,6,7,8,9)=2³ -3² -5-7=2520. Тогда х-1=2521; х=2521. Больше решений нет т.к. число демонстратов меньше 5000. Ответ: 2521 человек.

Заключение

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

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

Многие математики искали магическую формулу, которая позволяла бы выделить простые числа из бесконечного множества чисел натурального ряда и ими доказано:

1) нет самого большого простого числа;

2) нет последнего простого числа, после которого все числа были бы составными.

Итак, число простых чисел бесконечно.

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

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

Учебник «Математика 6 класс», Н.Я.Виленкин, В.И. Жохова и др.изд. «Мнемозида», Москва 2007

Энциклопедия для детей Т.-2.

Главный редактор М.Д.Аксёнова, М.: Аванша плюс, 2000г. «Великий мастер индукции Леонард Эйлер»

infourok.ru

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

Министерство образования РФ

Муниципальное общеобразовательное учреждение

«Средняя общеобразовательная школа №5 «Многопрофильная»

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

Выполнил: ученик 6 «А» класса

Белых Н.

Проверила: учитель математики

Кибе И.А.

г. Нефтеюганск

2011 г.

Содержание

Введение	4
Теоретические сведения	5
Решето Эратосфена	6
Открытие Пафнутия Львовича Чебышева	8
Победитель простых чисел	9
Числа – близнецы	9
Совершенные числа	10
Таблица простых чисел до 1000	11
Работа с таблицей простых чисел	12
Теорема Евклида	13
Числа Мерсенна	14
Скатерть (спираль) Станислава Улама	15
Удивительные закономерности	17
Некоторые приемы определения простых чисел	18
Количество простых чисел	19
Современные исследования	20
Заключение	22
Использованная литература	23

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

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

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

Мартин Гарднер «Математические досуги»

Введение

Среди чисел существует такое

совершенство и согласие, что нам

надо размышлять дни и ночи над

их удивительной закономерностью…

Стевин

Число – одно из основных понятий математики – зародилось в глубокой древности. Понятие о натуральном числе, возникшее в связи с

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

Цели и задачи:

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

Выяснить, существует ли математическая формула для их отыскания.

Выяснить, существует ли самое большое простое число?

Изучить сопутствующую теорию и историческое развитие данной темы.

Исследовать современное состояние изучаемого вопроса.

Теоретические сведения

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

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

Простые числа-близнецы это пара простых чисел, отличающихся на 2.

Если натуральное число a делится на натуральное число b,то число b называют делителем числа a, а число а – кратным числа b.

Свойства делимости.

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

Основная теорема арифметики.

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

Решето Эратосфена

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

Для нахождения простых чисел Эратосфен придумал следующий способ

Выпишем все целые числа от 1 до 100 в виде прямоугольной таблицы.
Вычеркнем все числа, кратные 2 (за исключением самой 2), проведя вертикальные черты во втором, четвертом и шестом столбцах.
Вычеркнем все числа, кратные 3, (за исключением самой 3), проведя вертикальную черту в третьем столбце. Следующее за 3 не вычеркнутое число = 5.
Чтобы вычеркнуть все числа, кратные 5, проведем диагонали, идущие вниз и влево.
Чтобы вычеркнуть все числа, кратные 7, проведем диагонали, идущие с наклоном вправо и вниз.
Числа 8,9 и 10 – составные, их кратные уже были вычеркнуты раньше.
Наша работа по составлению списка простых чисел, не превосходящих 100, на этом заканчивается.
Следующее простое число 11, 11∙11=121. Если бы таблица была больше, то нам пришлось бы исключать кратные 11, проводя диагонали с более крутым наклоном. И так далее…

Оставшиеся числа – простые.

А почему решето? Во времена Эратосфена писали на восковых дощечках, а вместо того, чтобы числа вычеркивать, дощечку в нужном месте прокалывали. Отсюда и название способа – «решето Эратосфена».

Решето Эратосфена

Итак, Решето Эратосфена работает как своего рода аналоговая вычислительная машина. И, значит, вот что изобрел великий грек: он изобрел счетную машину. Простые числа располагаются на числовом ряду весьма причудливым образом, но, создав Решето Эратосфена достаточно большого размера, мы отсеем (построим) их ВСЕ без исключения. Все они окажутся в дырках совершенно правильного геометрически Решета!

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

Анализируя Решето видно, что все простые числа либо на 1 меньше, либо на 1 больше чисел, кратных 6.

Открытие Пафнутия Львовича Чебышева

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

Если есть, то какой? Но ответ на эти вопросы не находился более2000 лет. Первый и очень большой шаг в разрешении этих вопросов сделал великий русский ученый Пафнутий Львович Чебышев. В 1850г. он доказал, что между любым натуральным числом (не равным 1) и числом, в 2раза большего его (т.е. между n и 2n), находится хотя бы одно простое число.

Проверим это на несложных примерах.

Примем для n несколько произвольных значений n и найдем соответственно значение 2n:

n=5, 2n=10

n=12, 2n=24

n=37, 2n=74

n=61, 2n=122

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

Возможно из всех занимательных задач в теории простых чисел самая занимательная – это поиск простых чисел. Подобно золотым самородкам, они скрываются в «породе» остальных чисел.

Победитель простых чисел

За свои гениальные открытия в области теории простых чисел профессор Петербургского университета П.Л.Чебышев (1821-1894) вошел в историю математики под именем «победителя простых чисел».

Проблема распределения простых чисел в натуральном ряду стояла неподступной крепостью в течение двух тысячелетий. Первый большой шаг в разрешение этой проблемы сделал Пафнутий Львович Чебышев. Он доказал теорему: «Между любым натуральным числом, не равным единице, и его удвоением находится хотя бы одно простое число».

На самом деле, между 2 и 4 находится простое число 3, между 3 и 6 — 5, между 4 и 6 — 5 и 7 и т.д.

Числа — близнецы

Среди простых чисел встречаются так называемые «близнецы» или пары простых чисел, разница между которыми составляет двойку (например,11 и13).

«Близнецы» появляются с некой периодичностью, причем, чем больше числа, тем реже они встречаются (11 и 13; 17 и 19; 29 и 31; 41 и 43; 59 и 61).

То же происходит и с обычными простыми числами. В числах, близких к триллиону, лишь каждое 28 число является простым.

Еще Евклидом было доказано, что простых чисел бесконечно много. Однако, окончательного ответа на вопрос, конечно или бесконечно множество «близнецов» пока не существует.

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

Простые числа – близнецы это пара простых чисел, отличающихся на 2.

Все пары простых чисел-близнецов, кроме (3,5) имеют вид 6n+1или 6n-1.

Действительно. Рассмотрим, например: 59 и 61. 59= 6*10 — 1; 61=6*10+1.

Первые простые числа-близнецы:

(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).

Найдены гигантские числа — близнецы: 10016957 и 10016959. Числа 10999949 и 10999951 – самые большие, ныне известные, числа – близнецы.

До сих пор неизвестно, есть ли самые большие числа – близнецы или нет, до сих пор нет ответа на вопрос: существуют ли бесконечно много пар простых чисел – близнецов.

Совершенные числа

Не менее интересным свойством обладают другие числа. Еще в древности было замечено, что существуют числа, равные сумме своих делителей, кроме самого себя.

Делители числа 6 – это числа 1,2,3,6. Нетрудно проверить, что их сумма без самого числа 6 равна 6. Делители числа 28 – числа 1, 2, 4, 7, 14, 28. И здесь проверкой легко установит, что их сумма без самого числа 28 равна 28. Числа 496 и 8128 обладают таким же свойством.

Античные математики считали очень важным рассматривать число вместе с его делителем. При этом в качестве меры использовались не количество, а сумма собственных делителей, которую сравнивали с самим числом.

Делители числа 10: это 1, 2, 5. Их сумма равна 8. Считали, что это недостаток, т.к. меньше 10. Делители числа 12: это 1, 2, 3, 4, 6. Их сумма равна 16, что считали избытком. А числа, у которых сумма делителей равна самому числу, особенно ценили и считали их совершенными.

Точно неизвестно, где впервые обратили внимание на совершенные числа. Предполагают, что они были известны в Древнем Вавилоне и Древней Греции.

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

2	79	191	311	439	577	709	857
3	83	193	313	443	587	719	859
5	89	197	317	449	593	727	863
7	97	199	331	457	599	733	877
11	101	211	337	461	601	739	881
13	103	223	347	463	607	743	883
17	107	227	349	467	613	751	887
19	109	229	353	479	617	757	907
23	113	233	359	487	619	761	911
29	127	239	367	491	631	769	919
31	131	241	373	499	641	773	929
37	137	251	379	503	643	787	937
41	139	257	383	509	647	797	941
43	149	263	389	521	653	809	947
47	151	269	397	523	659	811	953
53	157	271	401	541	661	821	967
59	163	277	409	547	673	823	971
61	167	281	419	557	677	827	977
67	173	283	421	563	683	829	983
71	179	293	431	569	691	839	991
73	181	307	433	571	701	853	997

zakon.znate.ru

Простые числа

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

Последовательность простых чисел начинается так (от 2 до 10000 их 1229):

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 103 107 109 113

127 131 137 139 149 151

157 163 167 173 179 181

191 193 197 199 211 223

227 229 233 239 241 251

257 263 269 271 277 281

283 293 307 311 313 317

331 337 347 349 353 359

367 373 379 383 389 397

401 409 419 421 431 433

439 443 449 457 461 463

467 479 487 491 499 503

509 521 523 541 547 557

563 569 571 577 587 593

599 601 607 613 617 619

631 641 643 647 653 659

661 673 677 683 691 701

709 719 727 733 739 743

751 757 761 769 773 787

797 809 811 821 823 827

829 839 853 857 859 863

877 881 883 887 907 911

919 929 937 941 947 953

967 971 977 983 991 997

1009 1013 1019 1021 1031 1033

1039 1049 1051 1061 1063 1069

1087 1091 1093 1097 1103 1109

1117 1123 1129 1151 1153 1163

1171 1181 1187 1193 1201 1213

1217 1223 1229 1231 1237 1249

1259 1277 1279 1283 1289 1291

1297 1301 1303 1307 1319 1321

1327 1361 1367 1373 1381 1399

1409 1423 1427 1429 1433 1439

1447 1451 1453 1459 1471 1481

1483 1487 1489 1493 1499 1511

1523 1531 1543 1549 1553 1559

1567 1571 1579 1583 1597 1601

1607 1609 1613 1619 1621 1627

1637 1657 1663 1667 1669 1693

1697 1699 1709 1721 1723 1733

1741 1747 1753 1759 1777 1783

1787 1789 1801 1811 1823 1831

1847 1861 1867 1871 1873 1877

1879 1889 1901 1907 1913 1931

1933 1949 1951 1973 1979 1987

1993 1997 1999 2003 2011 2017

2027 2029 2039 2053 2063 2069

2081 2083 2087 2089 2099 2111

2113 2129 2131 2137 2141 2143

2153 2161 2179 2203 2207 2213

2221 2237 2239 2243 2251 2267

2269 2273 2281 2287 2293 2297

2309 2311 2333 2339 2341 2347

2351 2357 2371 2377 2381 2383

2389 2393 2399 2411 2417 2423

2437 2441 2447 2459 2467 2473

2477 2503 2521 2531 2539 2543

2549 2551 2557 2579 2591 2593

2609 2617 2621 2633 2647 2657

2659 2663 2671 2677 2683 2687

2689 2693 2699 2707 2711 2713

2719 2729 2731 2741 2749 2753

2767 2777 2789 2791 2797 2801

2803 2819 2833 2837 2843 2851

2857 2861 2879 2887 2897 2903

2909 2917 2927 2939 2953 2957

2963 2969 2971 2999 3001 3011

3019 3023 3037 3041 3049 3061

3067 3079 3083 3089 3109 3119

3121 3137 3163 3167 3169 3181

3187 3191 3203 3209 3217 3221

3229 3251 3253 3257 3259 3271

3299 3301 3307 3313 3319 3323

3329 3331 3343 3347 3359 3361

3371 3373 3389 3391 3407 3413

3433 3449 3457 3461 3463 3467

3469 3491 3499 3511 3517 3527

3529 3533 3539 3541 3547 3557

3559 3571 3581 3583 3593 3607

3613 3617 3623 3631 3637 3643

3659 3671 3673 3677 3691 3697

3701 3709 3719 3727 3733 3739

3761 3767 3769 3779 3793 3797

3803 3821 3823 3833 3847 3851

3853 3863 3877 3881 3889 3907

3911 3917 3919 3923 3929 3931

3943 3947 3967 3989 4001 4003

4007 4013 4019 4021 4027 4049

4051 4057 4073 4079 4091 4093

4099 4111 4127 4129 4133 4139

4153 4157 4159 4177 4201 4211

4217 4219 4229 4231 4241 4243

4253 4259 4261 4271 4273 4283

4289 4297 4327 4337 4339 4349

4357 4363 4373 4391 4397 4409

4421 4423 4441 4447 4451 4457

4463 4481 4483 4493 4507 4513

4517 4519 4523 4547 4549 4561

4567 4583 4591 4597 4603 4621

4637 4639 4643 4649 4651 4657

4663 4673 4679 4691 4703 4721

4723 4729 4733 4751 4759 4783

4787 4789 4793 4799 4801 4813

4817 4831 4861 4871 4877 4889

4903 4909 4919 4931 4933 4937

4943 4951 4957 4967 4969 4973

4987 4993 4999 5003 5009 5011

5021 5023 5039 5051 5059 5077

5081 5087 5099 5101 5107 5113

5119 5147 5153 5167 5171 5179

5189 5197 5209 5227 5231 5233

5237 5261 5273 5279 5281 5297

5303 5309 5323 5333 5347 5351

5381 5387 5393 5399 5407 5413

5417 5419 5431 5437 5441 5443

5449 5471 5477 5479 5483 5501

5503 5507 5519 5521 5527 5531

5557 5563 5569 5573 5581 5591

5623 5639 5641 5647 5651 5653

5657 5659 5669 5683 5689 5693

5701 5711 5717 5737 5741 5743

5749 5779 5783 5791 5801 5807

5813 5821 5827 5839 5843 5849

5851 5857 5861 5867 5869 5879

5881 5897 5903 5923 5927 5939

5953 5981 5987 6007 6011 6029

6037 6043 6047 6053 6067 6073

6079 6089 6091 6101 6113 6121

6131 6133 6143 6151 6163 6173

6197 6199 6203 6211 6217 6221

6229 6247 6257 6263 6269 6271

6277 6287 6299 6301 6311 6317

6323 6329 6337 6343 6353 6359

6361 6367 6373 6379 6389 6397

6421 6427 6449 6451 6469 6473

6481 6491 6521 6529 6547 6551

6553 6563 6569 6571 6577 6581

6599 6607 6619 6637 6653 6659

6661 6673 6679 6689 6691 6701

6703 6709 6719 6733 6737 6761

6763 6779 6781 6791 6793 6803

6823 6827 6829 6833 6841 6857

6863 6869 6871 6883 6899 6907

6911 6917 6947 6949 6959 6961

6967 6971 6977 6983 6991 6997

7001 7013 7019 7027 7039 7043

7057 7069 7079 7103 7109 7121

7127 7129 7151 7159 7177 7187

7193 7207 7211 7213 7219 7229

7237 7243 7247 7253 7283 7297

7307 7309 7321 7331 7333 7349

7351 7369 7393 7411 7417 7433

7451 7457 7459 7477 7481 7487

7489 7499 7507 7517 7523 7529

7537 7541 7547 7549 7559 7561

7573 7577 7583 7589 7591 7603

7607 7621 7639 7643 7649 7669

7673 7681 7687 7691 7699 7703

7717 7723 7727 7741 7753 7757

7759 7789 7793 7817 7823 7829

7841 7853 7867 7873 7877 7879

7883 7901 7907 7919 7927 7933

7937 7949 7951 7963 7993 8009

8011 8017 8039 8053 8059 8069

8081 8087 8089 8093 8101 8111

8117 8123 8147 8161 8167 8171

8179 8191 8209 8219 8221 8231

8233 8237 8243 8263 8269 8273

8287 8291 8293 8297 8311 8317

8329 8353 8363 8369 8377 8387

8389 8419 8423 8429 8431 8443

8447 8461 8467 8501 8513 8521

8527 8537 8539 8543 8563 8573

8581 8597 8599 8609 8623 8627

8629 8641 8647 8663 8669 8677

8681 8689 8693 8699 8707 8713

8719 8731 8737 8741 8747 8753

8761 8779 8783 8803 8807 8819

8821 8831 8837 8839 8849 8861

8863 8867 8887 8893 8923 8929

8933 8941 8951 8963 8969 8971

8999 9001 9007 9011 9013 9029

9041 9043 9049 9059 9067 9091

9103 9109 9127 9133 9137 9151

9157 9161 9173 9181 9187 9199

9203 9209 9221 9227 9239 9241

9257 9277 9281 9283 9293 9311

9319 9323 9337 9341 9343 9349

9371 9377 9391 9397 9403 9413

9419 9421 9431 9433 9437 9439

9461 9463 9467 9473 9479 9491

9497 9511 9521 9533 9539 9547

9551 9587 9601 9613 9619 9623

9629 9631 9643 9649 9661 9677

9679 9689 9697 9719 9721 9733

9739 9743 9749 9767 9769 9781

9787 9791 9803 9811 9817 9829

9833 9839 9851 9857 9859 9871

9883 9887 9901 9907 9923 9929

9931 9941 9949 9967 9973

mirurokov.ru

Better Explained: непростой взгляд на простые числа / Newtonew: новости сетевого образования

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

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

Простые числа — это строительный материал для всех остальных чисел. В химии знание химического состава вещества помогает спрогнозировать его свойства. С числами всё происходит точно так же!
У простых чисел есть особые свойства, например, трудность их определения. Да, порой такая черта может быть оказаться весьма положительной — в таких сферах, как криптография.

Так что такое простые числа?

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

• 9 = 3 * 3 = 3²
• 12 = 2 * 2 * 3 = 2² * 3
• 100 = 4 * 25 = 2 * 2 * 5 * 5 = 2² * 5²

Простые числа — это неделимые далее числа. Например, 3, 5, 7 или 23. И число 2 — тоже простое число.

А что насчёт единицы?

1 — особенное число, которое не принято считать простым, хотя бы чтобы избежать шизофрении вида 1 = 1 * 1 * 1 * 1 и так далее..

Джексон Поллок «Номер 1», 1950 г., образец абстрактного импрессионизма

Источник: flickr

Представление натурального числа в виде произведения простых называется факторизацией, или разложением на простые. Разложение на простые кажется простым. На самом деле не всё здесь так уж просто. Оказывается, что:

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

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

Аналогия: простые числа и химические формулы

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

H₂O = два атома водорода и один атом кислорода

Так и в математике мы записываем число с помощью простых чисел:

12 = 2 * 2 * 3 = 2² * 3 = две двойки и одна тройка

Разница только в том, что в химической формуле «степень» пишется снизу, а не сверху. Я писал Американской ассоциации химиков, чтобы они внесли необходимые изменения в свою систему обозначений, но они мне до сих пор не ответил.

Это интересное наблюдение. А вдруг периодическая система химических элементов помогла бы нам найти закономерность и во множестве простых чисел?

Периодическая система элементов Д. И. Менделеева 1871 г.

Источник: science-techno.ru

Давайте посмотрим, как там было дело с периодической таблицей у химиков:

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

Вот бы нам такую таблицу для простых чисел!

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

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

Органическая химия и функциональные группы

Да, мы сейчас будем искать сходства между химическими формулами и простыми числами.

Источник: flickr

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

Некоторые свойства химических элементов зависят от их положения в периодической таблице химических элементов:

Атомы в группе VIIIA — благородные газы. Они обладают очень низкой химической реактивностью и вряд ли когда-нибудь взорвутся перед вашим лицом.
Атомы в группе IVA (подгруппа углерода) отличаются хорошим уровнем химической активности. Они — прекрасный строительный материал для других элементов.
Атомы в группе I (подгруппа щелочных металлов) исключительно реактивны. Хотите взрыв? Опустите их в воду.

В органической химии есть понятие функциональной группы — когда несколько атомов определяют класс целой молекулы. К примеру:

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

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

Пример первый: угадываем чётность

Органическое вещество, как правило, содержит углерод (это не всегда так, но нужно же с чего-то начать). Какие бы элементы вы ни смешивали, без углерода органическое вещество вы не получите.

Чётность работает примерно так же. Число является чётным, если при его разложении на простые мы имеем хотя бы одну двойку. Есть двойка в качестве множителя — число чётное; нет — нечётное.

А теперь давайте вспомним несколько математических задачек о произведении чётных и нечётных чисел.

Что будет, если нечётное число умножить на чётное? (чётное или нечётное?)
Что будет, если чётное число умножить на чётное? (чётное или нечётное?)
Что будет, если нечётное умножить на нечётное? (чётное или нечётное?)

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

Произведение нечётного и чётного чисел даёт чётное число.
Произведение чётного и чётного чисел даёт чётное число.
Произведение нечётного и нечётного чисел даёт нечётное число.

Круто, да? Поскольку 2 — простое число, мы не можем получить двойку через соединение других чисел, и знаем об этом.

Ещё пример: заканчиваем нулём

Конечно, пора привести пример с функциональной группой.

Предположим, что у нас есть функциональная группа 2 * 5 — то есть в нашей «формуле числа» будет как минимум одна двойка и как минимум одна пятёрка:

10 = 2 * 5
40 = 2 * 2 * 2 * 5
90 = 3 * 3 * 2 * 5

Заметили модель поведения? Если у числа есть функциональная группа 2 * 5, число кратно десяти.

Почему? Ну что ж:

2 * 5 = 10
2 * 2 * 2 * 5 = (2 * 2) * 10

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

И ещё один пример: сумма цифр

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

Представим функциональную группу 3 * 3. Если у числа есть эта функциональная группа, оно обладает следующими свойствами:

Оно делится на 9
Сумма его цифр делится на 9 (просто поверьте мне на слово)

Привожу пример:

18 = 2 * 3 * 3. Функциональная группа есть. Сумма его цифр 1 + 8 = 9, что делится на 9 без остатка.
279 = 31 * 3 * 3. Сумма его цифр 2 + 7 + 9 = 18, что делится на 9 без остатка.

Простые числа в реальном мире

У простых чисел есть поистине полезные свойства.

Большие числа сложно разложить на простые. Выше я уже говорили, что мы до сих пор действуем методом перебора, когда совершаем факторизацию числа. Этот факт применяется в криптографии.
Простые числа не пересекаются с обычными. Что я имею в виду? Например, 4 и 6 в итоге пересекутся уже на 12, а не на 24. 5 и 7 пересекутся только на 35. Для природы такая особенность может стать значительным преимуществом. Есть такие удивительные насекомые — семнадцатилетние цикады. Они находятся в коконе 17 лет, и только потом вылупляется. Это позволяет им значительно вырастить популяцию, поскольку их жизненный цикл не пересекается с жизненным циклом хищников, который обычно составляет 2-4 года.
Простые числа и в Африке простые. Последовательность простых чисел сложно сгенерировать случайным образом. Последовательность 1, 0, 1, 0 может быть произведена маятником. Ряд 2, 3, 5, 7, 11, 13 выстроится случайно с очень малой вероятностью. Более того, простые числа являются простыми в любой системе счисления. Везде найдутся числа, которые невозможно разделить на другие числа. В единичной системе счисления:

II
III
IIIII
IIIIIII

В заключение

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

Нашли опечатку? Выделите фрагмент и нажмите Ctrl+Enter.

newtonew.com

Непростые простые числа: секреты тайного общества ткачей

Непростые простые числа

Есть множество способов оптимизации, которые намного быстрее простого перебора, однако даже если оптимизация ускорит поиск в 10 раз, достаточно увеличить число на 2-3 десятичных знака (например, в 100 раз), чтобы замедлить поиск в 10^100 раз.

К слову, математики не нашли ни доказательства, ни опровержения того, что нельзя найти алгоритм факторизации, сложность которого не была бы экспоненциально зависящей от длины числа. А доказав или опровергнув это, можно, заодно, решить математическую проблему, известную как гипотеза Римана. За ее доказательство математический институт Клея обещает миллион долларов.

Отбрасывают ли числа тени?

Мы легко найдем бесконечность составных чисел, просто умножив n на 2.

То же касается умножения на 3.

Мы видим, что
— 15 строк вида 2n,
— 5 строк вида 3n (плюс 5 вида 6n уже учтены в 2n)
— и 2 строки вида 5n (еще три вида 10n уже вычеркнуты в числах 2n и одна 15n среди строк 3n)
не могут содержать простых чисел (мы же этого и ожидали, верно?)

Остаются лишь восемь строк вида 30n + i, где i = 1, 7, 11, 13, 17, 19, 23, 29. Если приглядеться, в них можно увидеть симметрию. 1+29=7+23=11+19=13+7.

Поэтому компактно можно записать как 30n +- i, где i = 1, 7, 11, 13,17

И мы понимаем, что вероятность найти произвольное простое число не больше 8/30. На 2/30 стало меньше…

Многомерные матрицы и гиперреалистичные фракталы?

А вот ее развертка с двух сторон

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

Заключение

Сам алгоритм в основе очень прост.

В матрице 30х7

И кусочек матрицы 210х11

А управляют узелками этой машиной вот такие матрицы-перфокарты
Развертка матрицами 2х3

И побольше, матрицами 6х5

Автор: realbtr

Источник