Математика, которая мне нравится. Простые большие числа

Какое самое большое число (простое или натуральное)

Иногда люди, не связанные с математикой, задаются вопросом: какое самое большое число? С одной стороны, ответ очевиден – бесконечность. Зануды даже уточнят, что «плюс бесконечность» или «+∞» в записи математиков. Вот только самых въедливых этот ответ не убедит, тем более, что это не натуральное число, а математическая абстракция. Но хорошо разобравшись в вопросе, они могут открыть перед собой интереснейшую проблему.

Действительно, предела размера в данном случае не существует, но существует предел человеческой фантазии. Для каждого числа есть название: десять, сто, миллиард, секстиллиард и так далее. Но где же заканчивается фантазия людей?

Гугол

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

Забавно, что придумал его ребенок - племянник математика Эдварда Казнера. В 1938 году дядюшка развлекал младших родственников рассуждениями об очень больших числах. К возмущению ребенка оказалось, что такое замечательное число не имеет названия, и он привел свой вариант. Позже дядюшка вставил его в одну из своих книг, и термин прижился.

Теоретически, гугол – это натуральное число, ведь его можно использовать для счета. Вот только вряд ли у кого-то хватит терпения досчитать до его конца. Поэтому, только теоретически.

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

Гуголплекс

Это число – производная от гугола, но ощутимо больше его. Приставка «плекс» означает, возведениее десятки в степень, равную основному числу, таким образом, гулоплекс – это 10 в степени 10 в степени 100 или 101000.

Получившееся число – превышает количество частиц в обозримой Вселенной, которое оценивается где-то в 1080 степени. Но это не помешало ученым увеличивать число простым добавлением к нему приставки «плекс»: гуголплексплекс, гуголплексплексплекс и так далее. А для особо извращенных математиков изобрели вариант увеличения без бесконечного повторения приставки «плекс» - перед ней просто ставят греческие числа: тетра (четыре), пента (пять) и так далее, вплоть до дека (десять). Последний вариант звучит как гуголдекаплекс и означает десятикратное накопительное повторение процедуры возведения числа 10 в степень его основания. Главное, не представлять себе результат. Осознать его все равно не получится, но получить травму психики – запросто.

48-ое число Мерсена

Главные герои: Купер, его компьютер и новое простое число

Сравнительно недавно, около года назад, удалось открыть очередное, 48-ое число Мерсена. На данный момент оно - самое большое простое число в мире. Напомним, что простые числа – это те, которые делятся без остатка только на единицу и на себя. Простейшие примеры – 3, 5, 7, 11, 13, 17 и так далее. Проблема в том, что чем дальше в дебри, тем реже такие числа встречаются. Но тем ценнее обнаружение каждого следующего. К примеру, новое простое число состоит из 17 425 170 знаков, если его представить в виде привычной нам десятичной системы счисления. В предыдущем было около 12 миллионов знаков.

Обнаружил его американский математик Кертис Купер, который уже в третий раз обрадовал математическую общественность подобным рекордом. Только на то, чтобы проверить его результат и доказать, что это число действительно простое, потребовалось 39 дней работы его персонального компьютера.

Число Грэма

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

Хорошая формула, только непонятная

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

Внимание! Следующая информация опасна для вашего психического здоровья! Читая её, вы принимаете на себя ответственность за все последствия!

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

Представьте себе 33. Это довольно легко – получается 3*3*3=27. А если теперь возвести тройку в это число? Получится 33 в 3 степени, или 327. В десятичной записи это равно 7 625 597 484 987. Много, но пока это можно осознать.

В стрелочной нотации Кнута это число можно отобразить несколько проще - 3↑↑3. Но если прибавить только одну стрелочку, получится уже сложнее: 3↑↑↑3, что означает 3↑↑3 в степень 3↑↑3 или в степенной записи . Если развернуть в десятичную запись, получим 7 625 597 484 9877 625 597 484 987. Ещё получается следить за мыслью?

Советуем почитать статью:Какой самый быстро работающий браузер?

Следующий этап: 3↑↑↑↑3= 3↑↑↑↑33↑↑↑↑3. То есть, нужно высчитать это дикое число из предыдущего действия и возвести его в такую же степень.

А 3↑↑↑↑3 – это только первый из 64 членов числа Грэма. Чтобы получить второй, нужно высчитать результат этой зубодробительной формулы, и подставить в схему 3(↑…↑)3 соответствующее количество стрелочек. И так далее, ещё 63 раза.

Интересно, у кого-то кроме него и ещё десятка суперматематиков получится добраться хотя бы до середины последовательности и не сойти при этом с ума?

Вы что-то поняли? Мы – нет. Но какой кайф!

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

megatopof.ru

Как найти простые числа? :: SYL.ru

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

Какие числа называют английским словом “симпл”?

Очень часто школьники на один из самых несложных на первый взгляд вопросов математики, о том что такое простое число, не знают, как ответить. Они часто путают простые числа с натуральными (то есть числа, которые используются людьми при счете предметов, при этом в некоторых источниках они начинаются с нуля, а в других - с единицы). Но это совершенно два разных понятия. Простые числа - это, натуральные, то есть целые и положительные числа, которые большее единицы и которые имеют всего лишь 2 натуральных делителя. При этом один из этих делителей - это данное число, а второй – единица. Например, три - это простое число, поскольку он не делится без остатка ни на какое другое число, кроме себя самого и единицы.

Составные числа

Противоположностью простых чисел являются составные. Они также являются натуральным, также больше единицы, но имеют не два, а большее количество делителей. Так, например, числа 4, 6, 8, 9 и т. д. являются натуральными, составными, но не простыми числами. Как видите – это в основном четные числа, но не все. А вот “двойка” – четное число и “первый номер” в ряду простых чисел.

Последовательность

Чтобы построить ряд простых чисел, необходимо совершить отбор из всех натуральных чисел с учетом их определения, то есть нужно действовать методом от противного. Необходимо рассмотреть каждое из натуральных положительных чисел на предмет того, имеет ли оно более двух делителей. Давайте постараемся построить ряд (последовательность), который составляют простые числа. Список начинается с двух, следующим идет три, поскольку оно делится только на себя и на единицу. Рассмотрим число четыре. Имеет ли оно делители, кроме четырех и единицы? Да, это число 2. Значит, четыре не является простым числом. Пять также является простым (оно, кроме 1 и 5, ни на какое другое число не делится), а вот шесть – делится. И вообще, если проследить за всеми четными числами, то можно заметить, что кроме “двух”, ни одно из них не является простым. Отсюда сделаем вывод, что четные числа, кроме двух, не являются простыми. Еще одно открытие: все числа, делящиеся на три, кроме самой тройки, будь то четные или нечетные, также не являются простыми (6, 9, 12, 15, 18, 21, 24, 27 и т.д.). То же самое касается и чисел, которые делятся на пять и на семь. Все их множество также не является простым. Давайте подведем итоги. Итак, к простым однозначным числам относятся все нечетные числа, кроме единицы и девятки, а из четных – только “два”. Сами десятки (10, 20,... 40 и др.) не являются простыми. Двузначные, трехзначные и т. д. простые числа можно определить, исходя из вышеизложенных принципов: если они не имеют других делителей, кроме их самих и единицы.

Теории о свойствах простых чисел

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

Простые числа — “строительные блоки” натуральных чисел

В арифметике есть теорема, которая называется основной. Согласно ей, любое натуральное число, кроме единицы, можно представить в виде произведения, множителями которого являются простые числа, причем порядок следования множителей единственен, этот означает, что и способ представления единственен. Он называется разложением натурального числа на простые множители. Есть и другое название этого процесса – факторизация чисел. Исходя из этого, простые числа можно назвать “строительным материалом”, "блоками" для построения натуральных чисел.

Поиск простых чисел. Тесты простоты

Множество ученых разных времен пытались найти какие-то принципы (системы) для нахождения списка простых чисел. Науке известны системы, которые называются решето Аткина, решето Сундартама, решето Эратосфена. Однако они не дают каких-то существенных результатов, и для нахождения простых чисел используется простая проверка. Также математиками были созданы алгоритмы. Их принято называть тестами простоты. Например, существует тест, разработанный Рабином и Миллером. Его используют криптографы. Также существует тест Каяла-Агравала- Саскены. Однако он, несмотря на достаточную точность, очень сложен в вычислении, что принижает его прикладное значение.

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

О том, что множество простых является бесконечностью, писал в книге “Начала” древнегреческий ученый Евклид. Он говорил так: “Давайте на минуту представим, что простые числа имеют предел. Тогда давайте перемножим их друг с другом, а к произведению прибавим единицу. Число, полученное в результате этих простых действий, не может делиться ни на одно из ряда простых чисел, потому что в остатке всегда будет единица. А это значит, что существует какое-то другое число, которое еще не включено в список простых чисел. Следовательно, наше допущение не верно, и это множество не может иметь предела. Помимо доказательства Евклида, существует более современная формула, данная швейцарским математиком восемнадцатого века Леонардом Эйлером. Согласно ему, сумма, обратная сумме первых n чисел растет неограниченно с ростом числа n. А вот формула теоремы относительно распределения простых чисел: (n) растёт, как n/ln (n).

Какое наибольшее простое число?

Все тот же Леонард Эйлер смог найти самое большое для своего времени простое число. Это 231 – 1 = 2147483647. Однако к 2013 году было вычислено другое наиболее точное самое большое в списке простых чисел – 257885161 – 1. Его называют числом Мерсенна. Оно содержит около 17 миллионов десятичных цифр. Как видите, число, найденное ученым из восемнадцатого века, в несколько раз меньше этого. Так и должно было быть, ведь Эйлер вел данный подсчет вручную, нашему же современнику наверняка помогала вычислительная машина. Более того, это число было получено на факультете математики в одном из американских факультетов. Числа, названные в честь этого ученого, проходят через тест простоты Люка-Лемера. Однако наука не желает останавливаться на достигнутом. Фонд Электронных рубежей, который был основан в 1990 году в Соединенных Штатах Америки (EFF), назначил за нахождение больших простых чисел денежную награду. И если до 2013 года приз полагался тем ученным, которые найдут их из числа 1 и 10 миллионов десятичных чисел, то сегодня это цифра достигла от 100 миллионов до 1 миллиарда. Размер призов составляет от 150 до 250 тысяч долларов США.

Названия специальных простых чисел

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

1. Мерссена.

2. Вудаа.

3. Ферма.

4. Каллена.

5. Прота.

6. Миллса и др.

Простота этих чисел, названных в честь вышеперечисленных ученых, устанавливается с использованием следующих тестов:

1. Люка-Лемера.

2. Пепина.

3. Ризеля.

4. Биллхарта – Лемера – Селфриджа и др.

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

www.syl.ru

Самые большие числа во Вселенной

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

Когда я говорю “наибольшее число во Вселенной’’, в действительности я имею в виду самое большое значимое число, максимально возможное число, которое в некотором роде полезно. Есть много претендентов на этот титул, но я сразу же предупреждаю вас: в самом деле существует риск того, что попытка понять все это взорвет ваш мозг. И кроме того, с излишком математики, вы получите мало удовольствия.

Гугол и гуголплекс

Эдвард Каснер

Мы могли бы начать с двух, весьма вероятно, самых больших чисел, о которых вы когда-либо слышали, и это действительно два самых больших числа, которые имеют общепринятые определения в английском языке. (Имеется довольно точная номенклатура, применяемая для обозначения чисел столь больших, как вам хотелось бы, но эти два числа в настоящее время вы не найдете в словарях.) Гугол, с тех пор как он стал всемирно известным (хотя и с ошибками, примеч. в самом деле это googol) в виде Google, родился в 1920 году как способ заинтересовать детей большими числами.

С этой целью математик Эдвард Каснер (на фото), взял двух своих племянников, Мильтона и Эдвина Сиротт, на прогулку по Нью-Джерси Palisades. Он предложил им выдвигать любые идеи, и тогда девятилетний Мильтон предложил “гугол’’. Откуда он взял это слово, неизвестно, но Каснер решил, что или число, в котором за единицей стоят сто нулей отныне будет называться гугол.

Но молодой Мильтон на этом не остановился, он предложил еще большее число, гуголплекс. Это число, по мнению Мильтона, в котором на первом месте стоит 1, а затем столько нулей, сколько вы могли бы написать до того как устанете. Хотя эта идея очаровательна, Каснер решил, что необходимо более формальное определение. Как он объяснил в своей книге 1940 года издания “Математика и воображение’’, определение Мильтона оставляет открытой рискованную возможность того, что случайный шут может стать математиком, превосходящим Альберта Эйнштейна просто потому, что он обладает большей выносливостью.

Таким образом, Каснер решил, что гуголплекс будет равен , или 1, а затем гугол нулей. Иначе, и в обозначениях, аналогичных тем, с которыми мы будем иметь дело для других чисел, мы будем говорить, что гуголплекс — это . Чтобы показать, насколько это завораживает, Карл Саган однажды заметил, что физически невозможно записать все нули гуголплекса, потому что просто не хватит места во Вселенной. Если заполнить весь объем наблюдаемой Вселенной мелкими частицами пыли размером приблизительно в 1,5 микрона, то число различных способов расположения этих частиц будет примерно равно одному гуголплексу.

Лингвистически говоря, гугол и гуголплекс, вероятно, два самых больших значащих числа (по крайней мере, в английском языке), но, как мы сейчас установим, способов определения “значимости’’ бесконечно много.

Реальный мир

Если мы будем говорить о самом большом значащем числе, существует разумный аргумент, что это в самом деле означает, что нужно найти наибольшее число с реально существующим в мире значением. Мы можем начать с текущей человеческой популяции, которая в настоящее время составляет около 6920 миллионов. Мировой ВВП в 2010 году, по оценкам, составил около 61960 миллиардов долларов, но оба эти числа незначительны по сравнению с примерно 100 триллионами клеток, составляющих организм человека. Конечно, ни одно из этих чисел не может сравниться с полным числом частиц во Вселенной, которое, как правило, считается равным примерно , и это число настолько велико, что наш язык не имеет соответствующего ему слова.

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

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

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

Часть трудностей состоит в том, чтобы придумать хорошее определение того, что такое “значащее’’ число. Один из способов состоит в том, чтобы рассуждать в терминах простых и составных чисел. Простое число, как вы, наверное, помните из школьной математики, — это любое натуральное число (примеч. не равное единице), которое делится только на и самого себя. Итак, и — простые числа, а и — составные числа. Это означает, что любое составное число может в конечном счете быть представлено своими простыми делителями. В некотором смысле число является более важным, чем, скажем, , потому что нет никакого способа выразить его через произведение меньших чисел.

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

Математики Древней Греции имели понятие о простых числах, по крайней мере, уже в 500 году до нашей эры, а 2000 лет спустя люди все еще знали, какие числа простые только примерно до 750. Мыслители времен Евклида увидели возможность упрощения, но вплоть до эпохи Возрождения математики не могли действительно использовать это на практике. Эти числа известны как числа Мерсенна, они названы в честь французского ученого XVII века Марина Мерсенна. Идея достаточно проста: число Мерсенна — это любое число вида . Так, например, , и это число простое, то же самое верно и для .

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

Компьютеры с тех пор были на охоте, и в настоящее время -е число Мерсенна является самым большим простым числом, известным человечеству. Обнаруженное в 2008 году, оно составляет — число с почти миллионами цифр. Это самое большое известное число, которое не может быть выражено через какие-либо меньшие числа, и если вы хотите помочь найти еще большее число Мерсенна, вы (и ваш компьютер) всегда можете присоединиться к поиску на сайте http://www.mersenne.org/.

Число Скьюза

Стэнли Скьюз

Снова обратимся к простым числам. Как я уже говорил, они ведут себя в корне неправильно, это означает, что нет никакого способа предсказать, каким будет следующее простое число. Математики были вынуждены обратиться к некоторым довольно фантастическим измерениям, чтобы придумать какой-нибудь способ предсказать будущие простые числа даже каким-нибудь туманным способом. Наиболее успешной из этих попыток, вероятно, является функция, считающая простые числа, которую придумал в конце XVIII века легендарный математик Карл Фридрих Гаусс.

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

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

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

Охота была на точку начала скачков, и вот тут появился Стэнли Скьюз (см. фото). В 1933 году он доказал, что верхняя граница, когда функция, приближающая количество простых чисел впервые дает меньшее значение — это число . Трудно по-настоящему понять даже в наиболее абстрактном смысле, что на самом деле представляет собой это число, и с этой точки зрения это было наибольшее число, когда-либо использованное в серьезном математическом доказательстве. С тех пор математики смогли уменьшить верхнюю границу до относительно маленького числа , но исходное число осталось известно как число Скьюза.

Итак, насколько велико число , которое делает карликом даже могучий гуголплекс? В словаре The Penguin Dictionary of Curious and Interesting Numbers Дэвид Уэллс рассказывает об одном способе, с помощью которого математику Харди удалось осмыслить размер числа Скьюза:

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

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

Проблема величины

Прежде чем мы перейдем к числу, рядом с которым даже число Скьюза выглядит крошечным, нам нужно немного поговорить о масштабе, потому что иначе у нас нет возможности оценить, куда мы собираемся идти. Сначала давайте возьмем число — это крошечное число, настолько малое, что люди могут действительно иметь интуитивное понимание того, что оно значит. Есть очень мало чисел, которые соответствуют этому описанию, так как числа больше шести перестают быть отдельными числами и становятся “несколько’’, “много’’ и т.д.

Теперь давайте возьмем , т.е. . Хотя мы в действительности не можем интуитивно, как это было для числа , понять, что такое , представить себе то, чем является очень легко. Пока все идет хорошо. Но что произойдет, если мы перейдем к ? Это равно , или . Мы очень далеки от способности представить себе эту величину, как и любую другую, очень большую — мы теряем способность постигать отдельные части где-то около миллиона. (Правда, безумно большое количество времени заняло бы, чтобы действительно досчитать до миллиона чего бы то ни было, но дело в том, что мы все еще способны воспринимать это число.)

Тем не менее, хотя мы не можем представить , мы по крайней мере в состоянии понять в общих чертах, что такое 7600 млрд, возможно, сравнивая его с чем-то таким, как ВВП США. Мы перешли от интуиции к представлению и к простому пониманию, но по крайней мере у нас еще есть некоторый пробел в понимании того, что такое число. Это вот-вот изменится, по мере нашего продвижения на еще одну ступень вверх по лестнице.

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

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

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

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

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

Число Грэма (Грехема)

Рональд Грэм

Вот как вы получите число Грэма, которое занимает место в Книге рекордов Гиннеса как самое большое число, которое когда-либо использовали в математическом доказательстве. Совершенно невозможно представить, насколько оно велико, и столь же трудно точно объяснить, что это такое. В принципе, число Грэма появляется, когда имеют дело с гиперкубами, которые являются теоретическими геометрическими формами с более чем тремя измерениями. Математик Рональд Грэм (см. фото) хотел выяснить, при каком наименьшем числе измерений определенные свойства гиперкуба будут оставаться устойчивыми. (Простите за такое расплывчатое объяснение, но я уверен, что нам всем нужно получить по крайней мере две ученые степени по математике, чтобы сделать его более точным.)

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

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

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

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

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

К бесконечности

Так есть числа больше, чем число Грэма? Есть, конечно, для начала есть число Грэма . Что касается значащего числа… хорошо, есть некоторые дьявольски сложные области математики (в частности, области, известной как комбинаторика) и информатики, в которых встречаются числа даже большие, чем число Грэма. Но мы почти достигли предела того, что, как я могу надеяться, когда-либо смогут разумно объяснить. Для тех, кто достаточно безрассуден достаточно, чтобы пойти еще дальше, предлагается литература для дополнительного чтения на свой страх и риск.

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

“Я вижу скопления смутных чисел, которые скрывается там, в темноте, за небольшим пятном света, которое дает свеча разума. Они шепчутся друг с другом; сговариваясь кто знает о чем. Возможно, они нас не очень любят за захват их меньших братишек нашими умами. Или, возможно, они просто ведут однозначный числовой образ жизни, там, за пределами нашего понимания’’.

Источник: http://io9.com/5807256/whats-the-biggest-number-in-the-universe

Там же можно найти и книги, чтобы узнать больше.

hijos.ru

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

Вглядись в них!

Простые числа (OEIS последовательность A000040) — в математике это такие натуральные числа, которые имеют ровно два делителя: себя и единицу[1]. Встречаются повсеместно, но ИРЛ являются не простыми, а очень даже сложными объектами для технарей и других любителей матана.

[править] Давным-давно в далекой галактике

«	Простые числа созданы для того, чтобы их умножать	»
— Лев Давидович Ландау

Хозяйке на заметку

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

Как и многие другие долгие математические истории, простые числа начались в Древней Греции[2]. Древние греки вообще начали обдумывать аксиоматику и, в частности, пришли к понятию числа. Числам натуральным и рациональным (отношениям натуральных) отводилась важная и б-жественная роль в мироздании, что ещё приведёт к своим трудностям.

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

[править] Сколько?

Открывши «Начала» Евклида, в 9-й книге, предложении номер 20, анон может невозбранно ознакомиться с доказательством того, что простых чисел бесконечно много.

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

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

К слову, возникает естественное предположение, что число, полученное нами в доказательстве бесконечности множества простых чисел — само простое. Увы, но это не всегда так. Простая калькуляция показывает, что уже число (спойлер: 2 ⋅ 3 ⋅ 5 ⋅ 7 ⋅ 11 ⋅ 13 + 1) будет составным. Более того, неизвестно, бесконечно ли много простых чисел такого вида. Та же самая ситуация и с числами, которые получаются вычитанием единицы из последовательного произведения простых чисел.

[править] Основная теорема арифметики

О природе хвалебных отзывов я по природной скромности умолчу, а ругают меня за то, <…> что я проявил редкостное невежество, причислив единицу к простым числам

В. В. Ткачук, «Математика — абитуриенту»

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

Четкая формулировка этой теоремы справедливости ради впервые встречается у Гаусса, но, судя по тексту всё тех же «Начал», греки это утверждение интуитивно понимали.

В известном смысле именно из этой теоремы растут ноги почти всей дискретной математики и, конечно, криптографии.

Эта теорема породила, кстати, достаточно забавную дисциплину математической спецолимпиады, а именно, считать единицу составным или простым числом? Ну, в самом деле, если единица — простое число, то разложение на простые множители неединственно, так как (спойлер: 1 ⋅ 1) = 1. А если единица не простое число, то вроде как составное, но это уж какой-то бред, потому что она делится нацело только на единицу и себя. Поэтому у многих авторов получается костыль: множество натуральных чисел разбивается на простые числа, составные и единицу. Ну, а некоторые причисляют-таки единицу к простым числам и запиливают соответствующий костыль в формулировку основной теоремы арифметики. Nuff said.

[править] Решето Эратосфена

Следующий вполне логичный и важный вопрос о поиске простых чисел был изучен, по всей видимости, в Александрийской библиотеке Эратосфеном Киренским.

Решето Эратосфена можно изобразить, например, так

Метод прост как пробка: выписываем все числа. Дальше берём двойку и вычеркиваем все остальные чётные числа как заведомо непростые. Следующее невычеркнутое число — это тройка. Запоминаем и вычеркиваем все остальные числа, которые делятся на 3. Следующее ещё невычеркнутое число — снова простое, это пятерка. Вычёркиваем всё, что делится на 5 и т. д… В результате остаются только подряд идущие числа, они и будут простыми. Win. Способ хорош, и ничего более разумного для перечисления всех-всех-всех простых чисел человечество не придумало. Современные способы поиска больших простых чисел в основном сводятся к поиску простых чисел определенного вида.

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

Кроме того, сей древнегреческий муж ещё занимался грамматикой, астрономией, филологией и внёс значимый вклад в развитие Александрийской библиотеки. Себя он позиционировал как… филолога.

[править] Классическая эпоха

После заката эпохи античности наступили времена высокой духовности и религиозности, также известные как тёмные века. Никаких особо интересных достижений, связанных с простыми числами, в те времена не зафиксировано, так что мы сразу перенесёмся на полторы тысячи лет вперёд, в конец XVI века. Многие вопросы, зачастую не имеющие ответов и поныне, были заданы именно тогда. В целом направлений для размышлений было два. Первое — нельзя ли придумать какую-нибудь формулу, которая задавала бы исключительно (и лучше бы все) простые числа. Второе — как они распределены среди натуральных, так как довольно быстро стало понятно, что это распределение не совсем случайно. Многое за 500 лет человечество узнало, но далеко не всё. Вот краткое описание основных достижений.

[править] Марен Мерсенн

Марен Мерсенн смотрит на тебя как на последовательность A000668

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

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

Среди научных результатов в рамках данной статьи нас интересует одна гипотеза, выдвинутая Мареном, а именно, он предположил, что числа вида 2n − 1, как правило, являются простыми. Из не вполне ясных соображений Мерсенн мамой клялся, что при n = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127, 257 соответствующие числа Мерсенна будут простыми, а все остальные числа Мерсенна до n = 257 совершенно точно будут составными. Впрочем, выяснилось, что инфометр у святого отца барахлил. Некоторые из не включенных в этот список чисел оказались простыми, а некоторые включенные — составными. Фейл? Не совсем. Гипотеза Мерсенна оказалась крайне продуктивной, именно последовательность из его чисел по сей день исправно поставляет самые большие простые числа. Недавно очередной рекорд был поставлен Кёртисом Купером, выяснившим, что число Мерсенна для n, равного 74 207 281, является простым.

Впрочем, до сих пор неизвестно, бесконечно ли множество простых чисел Мерсенна. Может, ты, анон, найдёшь ответ?

Иван Михеевич Первушин недоволен твоими познаниями в математике и слове б-жьем

Иронично, что одним из тех, кто насрал в компот Мерсенну, был простой русский священник Иван Михеевич Первушин, который выяснил, что при n = 61 число Мерсенна таки простое, хоть и не было включено в изначальный список. Кроме шуток, Иван Михеевич сделал серьёзную работу и неспроста был избран в Петербургскую и Неаполитанскую академии. А 61-е число Мерсенна ныне известно как число Первушина.

Стоит отметить довольно забавную историю, связанную с числом Мерсенна для n = 67. Доказательство того, что это число составное, уже было известно, однако не было известно, на какие же простые сомножители оно раскладывается. Фрэнк Коул вручную (sic!) вычислил разложение на простые множители (ни компьютеров, ни калькуляторов в те времена не было). Во время своего доклада, длившегося час, он молча вышел к доске, после чего… взял и вычислил, так и не сказав ни слова во время доклада, что 267 − 1 = 193 707 721 ⋅ 761 838 257 287. Кстати, Коул был правда неплохим математиком, а не каменножопым вычислителем, и отметился ещё и в теории простых групп и других разделах математики.

[править] Пьер Ферма

А что ты сделал для поиска простых чисел в последовательности A000215?

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

Гипотеза была в следующем: среди чисел вида 22n + 1 бесконечно много простых. Увы, но до сих пор неизвестно ни одного простого числа Ферма начиная с n = 5. Причём, чтобы получить ответ уже для n = 5, потребовалось применить целого Леонарда Эйлера. Среди прочего на этой же ниве отметился и уже упомянутый Первушин, который доказал, что не являются простыми несколько чисел Ферма. За сие сельский священник был поощрён: «Академия наук в поощрение трудов П. исхлопотала у святейшего синода высылки ему математических книг на 190 руб»!

Остается только подчеркнуть, что поиск простых чисел Ферма до сих пор не привёл ни к каким определённым результатам. Так что современное состояние этого вопроса состоит в писькомере на тему, у кого круче комп, а значит, кто может проверить на простоту самое большое число. На данный момент (результат 2014 года) самое большое точно составное число Ферма при n = 3 329 780.

[править] Многочлены и простые числа

Вообще, сказанное выше демонстрирует одно из самых популярных направлений мысли XVIII—XIX веков. Это идея описания всего и вся при помощи формул. Математики понимали, что простые числа распределены не совсем случайно, а значит, их наверняка можно описать каким-то разумным способом. Наиболее логичным было предположение о том, что какой-нибудь не слишком сложный многочлен (или другое выражение такого же сорта) при подстановке разных чисел будет давать исключительно простые числа. Может быть, не все, может быть, не по порядку, но зато исключительно простые. Именно эту идею и пытались реализовать Ферма и Мерсенн.

Полевые испытания Эйлера показали, что многочлен n2 − n + 41 — почти хороший. Для первых сорока натуральных чисел получаются простые значения. Но увы, последователи Эйлера доказали, что среди многочленов от одной переменной не бывает так, чтобы все значения многочлена были простыми. Некий итог в поиске точных формул для перечисления всех простых чисел поставил в конце XX века Матиясевич. Ответ оказался не очень приятный. Да, такие многочлены существуют, но вот выглядят они, скажем так, не очень. Сам Матиясевич привёл в качестве примера многочлен степени 15 905. Позже были предъявлены и примеры попроще, например многочлен степени 25, от 26 переменных…

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

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

[править] Проблема Гольдбаха

Кристиан Гольдбах смотрит на тебя как на нечётное число

Леонард Эйлер посмотрел бы на тебя как на говно, но на этом портрете он уже слеп

Шнирельман невысокого мнения о тебе

Иван Матвеич как бы интересуется, не жидо́к ли ты

Харальд Хельфгот недоволен этой статьей

Возьмем два множества натуральных чисел A и B и всевозможные попарные суммы A + B из этих множеств. Насколько большое множество мы получим? Несложно привести примеры, когда будет получено множество всех натуральных чисел (значит, множества достаточно жирные) и когда нет (множества мелковаты или неудачно распределены). Именно с этой конструкцией связана самая знаменитая, оставшаяся неразрешенной до сих пор проблема теории чисел, то есть проблема Гольдбаха.

В переписке Кристиана Гольдбаха (тогда ещё работавшего в рiдном Кенигсбергском университете, а в будущем перебравшегося на работу в Министерство иностранных дел той ещё Российской Империи) с Эйлером (также перебравшегося в Петербург на ПМЖ) было высказано две гипотезы: тернарная проблема Гольдбаха о том, что любое нечётное число может быть представлено в виде суммы не более чем трёх простых чисел, а также бинарная проблема, гласящая, что любое чётное число может быть представлено в виде суммы двух простых чисел.

Довольно долго никаких значимых продвижений в решении обеих проблем Гольдбаха не наблюдалось, пока наконец на проблему не набижали советские математики. Сначала в 1930 году Шнирельман доказал, что для некоторой константы k любое натуральное число может быть представлено в виде суммы не более чем k простых. После доработки напильником эта константа была доведена до 67. Fail? Как бы не так. Этот результат вселил уверенность, что проблема Гольдбаха в принципе разрешима.

Пятиминутка жидоборчества

Иван Матвеевич, кстати, был весьма интересной личностью. Будучи правда блестящим и выдающимся математиком, а также директором математического института, он был ещё и дичайшим, лютым антисемитом и жидоборцем. Впрочем, с этим связаны и определенные лулзы. Так, когда пришло распоряжение уволить академика Шафаревича, по словам очевидцев, сидевших под кроватью, произошёл примерно такой диалог с «компетентными органами»: — Нужно уволить Шафаревича! — Я проверил, он не еврей. — Уволить его надо, какая разница еврей он, или нет? Он враг советской власти! — Да нет, что вы! Я тщательно всё проверил, он точно не еврей! — !!!??? В общем, Шафаревича так и не уволили. Также злые языки утверждают, что своим главным административным достижением Виноградов считал «очистку математического института от евреев». Впрочем, не исключено, что истории про антисемитизм Виноградова сильно преувеличены.

Мощный ход в 1937 сделал Иван Матвеевич Виноградов, который доказал справедливость тернарной проблемы Гольдбаха для всех натуральных чисел, больших некоторой константы. Win? Теоретически да, но есть нюанс. Константа, до которой нужно перебрать, оказалась не просто большой, а пиздец какой большой, а именно сопоставимой с числом атомов во Вселенной… Ясное дело, что ни о каком переборе речь идти не могла. Многие допиливали и уточняли доказательство, заметно уменьшив константу, но так и не сделали её обозримой.

В результате тернарную проблему окончательно доковырял несколько иным методом перуанец Хельфготт в 2013 году.

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

[править] Распределение простых чисел

Красная линия — та самая асимптотика

Ещё одно направление размышлений о простых числах такое. С одной стороны, среди натуральных чисел бывают сколь угодно длинные промежутки, на которых нет ни одного простого числа (это задача для 7-го класса). С другой стороны, иногда простые числа бывают очень близко друг к другу. Нет ли какого-нибудь способа узнать, насколько часто встречаются простые числа?

[править] Проблема близнецов

Если начать изучать последовательность простых чисел, то видно, что иногда (и не так уж и редко) попадаются простые числа, между которыми расстояние равно двум, например 11 и 13, 17 и 19. Такие числа называются близнецами. Самые большие найденные на данный момент близняшки — это 2 996 863 034 895 ⋅ 21 290 000 ± 1.

Печаль в том, что по сей день неизвестно, конечно ли множество пар близнецов. Хочется верить, что нет. Самый сильный результат по этому поводу принадлежит одному китайцу (подробности тут). Вкратце доказано, что существует бесконечно много пар простых чисел, расстояние между которыми не превышает всего лишь 70 миллионов.

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

[править] Постулат Бертрана

Достаточно быстро (ещё Эйлеру) стало понятно, что простые числа распределены не так уж и редко. Так что, если отвлечься от близнецов и совсем уж «соседних» простых чисел, сосредоточившись на их распределении в среднем, станет ясно, что какой-то ответ рано или поздно появится.

Самый первый результат от дедушки Эйлера состоял в том, что количество простых чисел среди натуральных растёт медленнее, чем линейная функция.

Пафнутий Львович смотрит на тебя как-то недовольно, свирепо и в то же время грустно и с недоумением

Вскоре возникла гипотеза, высказанная Бертраном, о том, что между числами n и 2n есть хотя бы одно простое. Доказал это утверждение Пафнутий Львович Чебышёв (кстати, первый научный руководитель этой вашей Софьи Ковалевской). Интересно отметить, что самое простое доказательство этой теоремы ещё лет через 50 придумал Эрдёш.

Вообще, в классической теории чисел шаг вправо, шаг влево — нерешенная проблема. Вот и с постулатом Бертрана та же хуйня. Неизвестно до сих пор, верно ли, что между любыми двумя соседними квадратами чисел — n2 и (n + 1)2 — есть хотя бы одно простое число (гипотеза Лежандра).

[править] Распределение

Как уже было сказано, Эйлер доказал, что количество простых чисел π(n), не превышающих n, растёт медленнее, чем линейная функция. Так что довольно быстро математики стали подозревать, что где-то тут зарыт логарифм. Первым заподозрил что-то такое Гаусс, потом Лежандр и Вега.

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

Однако точно сформулировал гипотезу и почти (установил очень и очень узкий коридор, в котором может быть колебание) доказал Пафнутий наш Львович Чебышёв. Гипотеза была, что π(x) ≈ x/ln(x). Чуть позже Риман связал эту самую функцию со своей дзета-функцией (о которой пара слов будет сказана ниже), и, наконец, в 1896 году Адамар и Валле-Пуссен окончательно доказывают теорему о распределении простых чисел.

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

[править] Гипотеза Римана

Первое равенство — это определение дзета-функции Римана, а второе равенство — утверждение, доказанное Эйлером

Тесно связана с распределением простых чисел и такая очень известная математическая конструкция, как дзета-функция Римана, которую в своё время придумал Эйлер и активно изучал Чебышёв. За определением этой функции и её свойствами марш в Вику. Мы же отметим, что тот, кто докажет, что все нетривиальные нули этой функции имеют действительную часть, равную 0,5, будет ба-а-альшой молодец. И даже получит лям баксов от института Клея за решение проблемы тысячелетия.

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

«	Криптография бывает двух типов: криптография, которая помешает читать ваши файлы вашей младшей сестре, и криптография, которая помешает читать ваши файлы людям из правительства.	»
— Брюс Шнайер, «Прикладная криптография» (Applied Cryptography), 2-е издание.

Всё, о чем мы толковали выше, это пусть и почтенные задачи, но пик интереса к ним остался в прошлом. Дело в том, что, если (когда?) будет доказана бинарная проблема Гольдбаха, это не приблизит человечество к алгоритму представления числа в виде суммы двух простых. То же можно сказать и о других задачах. Знание тонкостей распределения простых чисел интересно и важно с теоретической точки зрения, но едва ли даст нам что-то по-настоящему новое. Передний фронт современных математических интересов ушёл далеко (и ты, дорогой читатель, даже не представляешь себе, НАСКОЛЬКО), а равно и фронт интересов практических, также известных как прикладная математика. Однако интерес к простым числам отнюдь не праздный.

Дело в том, что очень многие криптографические алгоритмы основаны, очень грубо говоря, на том, что если есть очень большое число, которое является произведением двух очень больших простых чисел, то найти это разложение, не зная одного из сомножителей, очень трудно. Поэтому знание очень больших (действительно ОЧЕНЬ БОЛЬШИХ) простых чисел необходимо, чтобы обеспечивать криптостойкость.

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

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

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

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

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

Разумная версия состоит в том, что простые (да и вообще натуральные) числа — очень не геометричный объект. То есть если бы была какая-то их разумная геометрическая интерпретация, более разумная, чем нули дзета-функции, то и решались бы соответствующие задачи гораздо проще. Неспроста многие задачи теории чисел решаются последние лет 70 такими далёкими, на первый взгляд, от теории чисел инструментами, как комплексный анализ, алгебраическая геометрия и прочий зубодробительный матан, в котором разве что Перельман разберётся.

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

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

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

[править] Что почитать по теме

1. ↑ Более простым языком для школьников, прокуривших уроки математики в туалете: простыми называются числа, которые можно разделить без остатка (это важно) только на единицу и на самих себя. Допустим, 5 делится лишь на 5 (получаем 1) и на 1 (получаем 5). А вот девятку, помимо самой себя и единицы, можно безо всяких дробей в ответе поделить ещё и на тройку. Такие дела.
2. ↑ Потому что всем похуй на арабов^Wегиптян и папирус Ахмеса, конечно же.

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

lurkmore.to

история и факты / Хабр

Свойства простых чисел впервые начали изучать математики Древней Греции. Математики пифагорейской школы (500 — 300 до н.э.) в первую очередь интересовались мистическими и нумерологическими свойствами простых чисел. Они первыми пришли к идеям о совершенных и дружественных числах.

У совершенного числа сумма его собственных делителей равна ему самому. Например, собственные делители числа 6: 1, 2 и 3. 1 + 2 + 3 = 6. У числа 28 делители — это 1, 2, 4, 7 и 14. При этом, 1 + 2 + 4 + 7 + 14 = 28.

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

Ко времени появления работы Евклида «Начала» в 300 году до н.э. уже было доказано несколько важных фактов касательно простых чисел. В книге IX «Начал» Эвклид доказал, что простых чисел бесконечное количество. Это, кстати, один из первых примеров использования доказательства от противного. Также он доказывает Основную теорему арифметики – каждое целое число можно представить единственным образом в виде произведения простых чисел.

Также он показал, что если число 2n-1 является простым, то число 2n-1 * (2n-1) будет совершенным. Другой математик, Эйлер, в 1747 году сумел показать, что все чётные совершенные числа можно записать в таком виде. По сей день неизвестно, существуют ли нечётные совершенные числа. В году 200 году до н.э. грек Эратосфен придумал алгоритм для поиска простых чисел под названием «Решето Эратосфена».

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

Следующие открытия были сделаны уже в начале 17-го века математиком Ферма. Он доказал гипотезу Альбера Жирара, что любое простое число вида 4n+1 можно записать уникальным образом в виде суммы двух квадратов, и также сформулировал теорему о том, что любое число можно представить в виде суммы четырёх квадратов.

Он разработал новый метод факторизации больших чисел, и продемонстрировал его на числе 2027651281 = 44021 × 46061. Также он доказал Малую теорему Ферма: если p – простое число, то для любого целого a будет верно ap = a modulo p.

Это утверждение доказывает половину того, что было известно как «китайская гипотеза», и датируется 2000 годами ранее: целое n является простым тогда и только тогда, если 2n-2 делится на n. Вторая часть гипотезы оказалась ложной – к примеру, 2341 — 2 делится на 341, хотя число 341 составное: 341 = 31 × 11.

Малая теорема Ферма послужила основой множества других результатов в теории чисел и методов проверки чисел на принадлежность к простым – многие из которых используются и по сей день.

Ферма много переписывался со своими современниками, в особенности с монахом по имени Марен Мерсенн. В одном из писем он высказал гипотезу о том, что числа вида 2n+1 всегда будут простыми, если n является степенью двойки. Он проверил это для n = 1, 2, 4, 8 и 16, и был уверен, что в случае, когда n не является степенью двойки, число не обязательно получалось простым. Эти числа называются числами Ферма, и лишь через 100 лет Эйлер показал, что следующее число, 232 + 1 = 4294967297 делится на 641, и следовательно, не является простым.

Числа вида 2n — 1 также служили предметом исследований, поскольку легко показать, что если n – составное, то и само число тоже составное. Эти числа называют числами Мерсенна, поскольку он активно их изучал.

Но не все числа вида 2n — 1, где n – простое, являются простыми. К примеру, 211 — 1 = 2047 = 23 * 89. Впервые это обнаружили в 1536 году.

Многие годы числа такого вида давали математикам наибольшие известные простые числа. Что число M19, было доказано Катальди в 1588 году, и в течение 200 лет было наибольшим известным простым числом, пока Эйлер не доказал, что M31 также простое. Этот рекорд продержался ещё сто лет, а затем Люкас показал, что M127 — простое (а это уже число из 39 цифр), и после него исследования продолжились уже с появлением компьютеров.

В 1952 была доказана простота чисел M521, M607, M1279, M2203 и M2281.

К 2005 году найдено 42 простых чисел Мерсенна. Наибольшее из них, M25964951, состоит из 7816230 цифр.

Работа Эйлера оказала огромное влияние на теорию чисел, в том числе и простых. Он расширил Малую теорему Ферма и ввёл φ-функцию. Факторизовал 5-е число Ферма 232+1, нашёл 60 пар дружественных чисел, и сформулировал (но не смог доказать) квадратичный закон взаимности.

Он первым ввёл методы математического анализа и разработал аналитическую теорию чисел. Он доказал, что не только гармонический ряд ∑ (1/n), но и ряд вида

1/2 + 1/3 + 1/5 + 1/7 + 1/11 +…

получаемый суммой величин, обратных к простым числам, также расходится. Сумма n членов гармонического ряда растёт примерно как log(n), а второй ряд расходится медленнее, как log[ log(n) ]. Это значит, что, например, сумма обратных величин ко всем найденным на сегодняшний день простым числам даст всего 4, хотя ряд всё равно расходится.

На первый взгляд кажется, что простые числа распределены среди целых довольно случайно. К примеру, среди 100 чисел, идущих прямо перед 10000000, встречается 9 простых, а среди 100 чисел, идущих сразу после этого значения – всего 2. Но на больших отрезках простые числа распределены достаточно равномерно. Лежандр и Гаусс занимались вопросами их распределения. Гаусс как-то рассказывал другу, что в любые свободные 15 минут он всегда подсчитывает количество простых в очередной 1000 чисел. К концу жизни он сосчитал все простые числа в промежутке до 3 миллионов. Лежандр и Гаусс одинаково вычислили, что для больших n плотность простых чисел составляет 1/log(n). Лежандр оценил количество простых чисел в промежутке от 1 до n, как

π(n) = n/(log(n) — 1.08366)

А Гаусс – как логарифмический интеграл

π(n) = ∫ 1/log(t) dt

с промежутком интегрирования от 2 до n.

Утверждение о плотности простых чисел 1/log(n) известно как Теорема о распределении простых чисел. Её пытались доказать в течение всего 19 века, а прогресса достигли Чебышёв и Риман. Они связали её с гипотезой Римана – по сию пору не доказанной гипотезой о распределении нулей дзета-функции Римана. Плотность простых чисел была одновременно доказана Адамаром и Валле-Пуссеном в 1896 году.

В теории простых чисел есть ещё множество нерешённых вопросов, некоторым из которых уже многие сотни лет:

• гипотеза о простых числах-близнецах – о бесконечном количестве пар простых чисел, отличающихся друг от друга на 2
• гипотеза Гольдбаха: любое чётное число, начиная с 4, можно представить в виде суммы двух простых чисел
• бесконечно ли количество простых чисел вида n2 + 1 ?
• всегда ли можно найти простое число между n2 and (n + 1) 2? (факт, что между n и 2n всегда есть простое число, было доказан Чебышёвым)
• бесконечно ли число простых чисел Ферма? есть ли вообще простые числа Ферма после 4-го?
• существует ли арифметическая прогрессия из последовательных простых чисел для любой заданной длины? например, для длины 4: 251, 257, 263, 269. Максимальная из найденных длина равна 26.
• бесконечно ли число наборов из трёх последовательных простых чисел в арифметической прогрессии?
• n2 — n + 41 – простое число для 0 ≤ n ≤ 40. Бесконечно ли количество таких простых чисел? Тот же вопрос для формулы n2 — 79 n + 1601. Эти числа простые для 0 ≤ n ≤ 79.
• бесконечно ли количество простых чисел вида n# + 1? (n# — результат перемножения всех простых чисел, меньших n)
• бесконечно ли количество простых чисел вида n# -1 ?
• бесконечно ли количество простых чисел вида n! + 1?
• бесконечно ли количество простых чисел вида n! – 1?
• если p – простое, всегда ли 2p-1 не содержит среди множителей квадратов простых чисел
• содержит ли последовательность Фибоначчи бесконечное количество простых чисел?

Текущие рекорды среди простых чисел

Самое большое простое число, вычисленное проектом GIMPS [Great Internet Mersenne Prime Search], можно посмотреть в таблице на официальной странице проекта.www.mersenne.org/primes

Самые большие близнецы среди простых чисел – это 2003663613 × 2195000 ± 1. Они состоят из 58711 цифр, и были найдены в 2007 году.

Самое большое факториальное простое число (вида n! ± 1) – это 147855! — 1. Оно состоит из 142891 цифр и было найдено в 2002.

Наибольшее праймориальное простое число (число вида n# ± 1) – это 1098133# + 1.

habr.com

Простое число | Математика | FANDOM powered by Wikia

Просто́е число́ — это натуральное число, большее единицы, имеющее ровно два натуральных делителя: 1 и само себя. Изучением свойств простых чисел занимается теория чисел.

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

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, бесконечно. (последовательность A000040 в OEIS, см. также список простых чисел)

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

Разложение натуральных чисел в произведение простых Править

Основная теорема арифметики утверждает, что каждое натуральное число, большее единицы (1), представимо в виде произведения простых чисел, причём единственным способом (с точностью до порядка следования сомножителей). Таким образом, простые числа — «элементарные строительные блоки» натуральных чисел.

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

Файл:Eratosthenes.jpg

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

Однако на практике обычно возникает необходимость проверить, является ли число простым, а не получать список простых чисел. Алгоритмы такого рода называются тестами простоты. Существует множество полиномиальных тестов простоты. Большинство таких алгоритмов являются вероятностными (например, тест Миллера — Рабина) и используются для нужд криптографии. Только в 2002 году было доказано, что задача проверки на простоту в общем виде полиномиально разрешима, но предложенный детерминированный алгоритм имеет довольно большую сложность, что затрудняет его практическое применение.

Для некоторых классов чисел существуют специализированные эффективные тесты простоты. Например, для проверки на простоту чисел Мерсенна используется тест Люка — Лемера.

Сколько существует простых чисел? Править

Простых чисел бесконечно много. Самое старое известное доказательство этого факта было дано Евклидом в «Началах» (книга IX, утверждение 20). Его доказательство может быть кратко воспроизведено так:

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

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

Известная теорема о распределении простых чисел утверждает, что количество простых чисел меньших $ n $, обозначаемое $ \pi(n) $, растет как $ n/\ln(n) $.

Наибольшее известное простое Править

Наибольшим известным простым числом по состоянию на январь 2018 года является $ 2^{77232917} - 1 $. Оно является 50-м известным простым числом Мерсенна. Компьютер волонтёра Джонатана Пейса вычислил его 26 декабря 2017 года. Джонатан — один из тысяч добровольцев, использующих бесплатное ПО GIMPS.

Новое простое число, также известное как M77232917, вычислено перемножением 77 232 917 двоек и вычитанием единицы. Оно примерно на один миллион разрядов больше, чем предыдущее рекордное простое число, в особом классе исключительно редких простых, известных как числа Мерсенна. Это всего пятидесятое открытое простое число Мерсенна; вычисление каждого последующего становится сложнее.

Числа Мерсенна выгодно отличаются от остальных наличием эффективного теста простоты: теста Люка — Лемера. Благодаря ему простые числа Мерсенна давно удерживают рекорд как самые большие известные простые. За нахождение простого числа из более чем 107 десятичных цифр EFF назначила награду в 100000 долларов США.

Некоторые свойства Править

• Если $ p $ — простое, и $ p $ делит $ a b $, то $ p $ делит $ a $ или $ b $. Доказательство этого факта было дано Евклидом и известно как лемма Евклида. Оно используется в доказательстве основной теоремы арифметики.
• Кольцо вычетов $ \mathbb{Z}_n $ является полем тогда и только тогда, когда $ n $ — простое.
• Характеристика каждого поля — это ноль или простое число.
• Если $ p $ — простое, а $ a $ — натуральное, то $ a^p - a $ делится на $ p $ (малая теорема Ферма).
• Если $ G $ — конечная группа с $ p^n $ элементов, то $ G $ содержит элемент порядка $ p $.
• Если $ G $ — конечная группа, и $ p^n $ — максимальная степень $ p $, которая делит $ |G| $, то $ G $ имеет подгруппу порядка $ p^n $, называемую силовской подгруппой, более того, количество силовских подгрупп равно $ pk+1 $ для некоторого целого $ k $ (теоремы Силова).
• Натуральное $ p > 1 $ является простым тогда и только тогда, когда $ (p - 1)! + 1 $ делится на $ p $ (теорема Вильсона).
• Если $ n > 1 $ — натуральное, то существует простое $ p $, такое, что $ n < p < 2 n $ (постулат Бертрана).
• Ряд чисел, обратных к простым, расходится. Более того,
$ \lim_{x\to\infty} \sum_{p<x} \frac{1}{p}\ \sim\ \ln \ln x $

Открытые вопросы Править

До сих пор существует много открытых вопросов относительно простых чисел. Например:

• Проблема Гольдбаха: верно ли, что каждое чётное число больше двух может быть представлено в виде суммы двух простых чисел? Верно ли, что каждое нечётное число больше 5 может быть представлено в виде суммы трёх простых чисел?
• Простые близнецы — это простые числа, разность между которыми равна 2. Верно ли, что существует бесконечно много простых близнецов?
• Содержит ли последовательность чисел Фибоначчи бесконечное количество простых?
• Конечно ли количество простых чисел Ферма (то есть чисел вида $ 2^{2^n}+1 $)?
• Всегда ли найдется простое число между $ n^2 $ и $ (n + 1)^2 $?
• Бесконечно ли количество простых вида $ n^2 + 1 $?
• Гипотеза Буняковского: верно ли, что любой неприводимый целозначный многочлен, НОД всех значений которого равен 1, принимает простые значения сколь угодно много раз?

Приложения простых чисел Править

Большие простые числа (порядка $ 10^{300} $) используются в криптографии с открытым ключом. Простые числа также используются в хеш-таблицах и для генерации псевдослучайных чисел.

• Г. Гальперин, «Просто о простых числах», «Квант», № 4, 1987
• «Алгоритмические проблемы теории чисел», глава из книги «Введение в криптографию» под редакцией В. В. Ященко
• О. Н. Василенко, «Теоретико-числовые алгоритмы в криптографии»
• А. В. Черемушкин, «Лекции по арифметическим алгоритмам в криптографии»
• К.Кноп «В погоне за простотой»
• Б. А. Кордемский Математическая смекалка. - М.:ГИФ-МЛ, 1958.-576 с. (стр. 344-345).
• Генри С. Уоррен, мл. Глава 16. Формулы для простых чисел // Алгоритмические трюки для программистов = Hacker's Delight. — М.: «Вильямс», 2007. — С. 288. ISBN 0-201-91465-4

Шаблон:Хорошая статья

af:Priemgetal ang:Frumtæl ar:عدد أولي be-x-old:Просты лік bg:Просто число bn:মৌলিক সংখ্যা br:Niveroù kentael ca:Nombre primer cs:Prvočíslo cy:Rhif cysefin da:Primtalel:Πρώτος αριθμόςeo:Primoet:Algarv eu:Zenbaki lehen fa:اعداد اولgl:Número primo he:מספר ראשוני hr:Prost broj ht:Nonm premyé hu:Prímszámok id:Bilangan prima is:Frumtalaka:მარტივი რიცხვიla:Numerus primus lb:Primzuel lmo:Nümar primm lt:Pirminis skaičius lv:Pirmskaitlis nds:Primtall nl:Priemgetal nn:Primtal no:Primtall pl:Liczby pierwszescn:Nùmmuru primu simple:Prime number sk:Prvočíslo sl:Praštevilo sr:Прост број sv:Primtal ta:பகா எண் th:จำนวนเฉพาะuk:Просте число ur:مفرد عدد vi:Số nguyên tố vls:Priemgetal yi:פרימצאל yo:Nọ́mbà àkọ́kọ́zh-min-nan:Sò͘-sò͘

ru.math.wikia.com

Просто про простые числа - Мастерок.жж.рф

Свойства простых чисел впервые начали изучать математики Древней Греции. Математики пифагорейской школы (500 — 300 до н.э.) в первую очередь интересовались мистическими и нумерологическими свойствами простых чисел. Они первыми пришли к идеям о совершенных и дружественных числах.

Простые числа делятся без остатка на единицу и на самих себя. Они - основа арифметики и всех натуральных чисел. То есть тех, которые возникают естественным образом при счете предметов, например, яблок. Любое натуральное число это произведение каких-нибудь простых чисел.

И тех и других - бесконечное множество.

Простые числа, кроме 2 и 5, заканчиваются на 1, на 3, на 7 или на 9. Считалось, что они распределены случайным образом. И за простым числом, оканчивающимся, к примеру, на 1 может с равной вероятностью - в 25 процентов - следовать простое число, которое оканчивается на 1, 3, 7, 9.Простые числа — это целые числа больше единицы, которые не могут быть представлены как произведение двух меньших чисел. Таким образом, 6 — это не простое число, так как оно может быть представлено как произведение 2×3, а 5 — это простое число, потому что единственный способ представить его как произведение двух чисел — это 1×5 или 5×1. Если у вас есть несколько монет, но вы не можете расположить их все в форме прямоугольника, а можете только выстроить их в прямую линию, ваше число монет — это простое число.

У совершенного числа сумма его собственных делителей равна ему самому. Например, собственные делители числа 6: 1, 2 и 3. 1 + 2 + 3 = 6. У числа 28 делители — это 1, 2, 4, 7 и 14. При этом, 1 + 2 + 4 + 7 + 14 = 28.

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

Ко времени появления работы Евклида «Начала» в 300 году до н.э. уже было доказано несколько важных фактов касательно простых чисел. В книге IX «Начал» Эвклид доказал, что простых чисел бесконечное количество. Это, кстати, один из первых примеров использования доказательства от противного. Также он доказывает Основную теорему арифметики – каждое целое число можно представить единственным образом в виде произведения простых чисел.

Также он показал, что если число 2n-1 является простым, то число 2n-1 * (2n-1) будет совершенным. Другой математик, Эйлер, в 1747 году сумел показать, что все чётные совершенные числа можно записать в таком виде. По сей день неизвестно, существуют ли нечётные совершенные числа.

В году 200 году до н.э. грек Эратосфен придумал алгоритм для поиска простых чисел под названием «Решето Эратосфена».

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

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

После греков серьезное внимание простым числам снова уделили в XVII веке. С тех пор многие известные математики внесли важный вклад в наше понимание простых чисел. Пьер де Ферма совершил множество открытий и известен благодаря Великой теореме Ферма, 350-летней проблеме, связанной с простыми числами и решенной Эндрю Уайлсом в 1994 году. Леонард Эйлер доказал много теорем в XVIII веке, а в XIX веке большой прорыв был сделан благодаря Карлу Фридриху Гауссу, Пафнутию Чебышёву и Бернхарду Риману, особенно в отношении распределения простых чисел. Кульминацией всего этого стала до сих пор не решенная гипотеза Римана, которую часто называют важнейшей нерешенной задачей всей математики. Гипотеза Римана позволяет очень точно предсказать появление простых чисел, а также отчасти объясняет, почему они так трудно даются математикам.

Открытия сделаные в начале 17-го века математиком Ферма, доказали гипотезу Альбера Жирара, что любое простое число вида 4n+1 можно записать уникальным образом в виде суммы двух квадратов, и также сформулировал теорему о том, что любое число можно представить в виде суммы четырёх квадратов.

Он разработал новый метод факторизации больших чисел, и продемонстрировал его на числе 2027651281 = 44021 × 46061. Также он доказал Малую теорему Ферма: если p – простое число, то для любого целого a будет верно ap = a modulo p.

Это утверждение доказывает половину того, что было известно как «китайская гипотеза», и датируется 2000 годами ранее: целое n является простым тогда и только тогда, если 2n-2 делится на n. Вторая часть гипотезы оказалась ложной – к примеру, 2341 — 2 делится на 341, хотя число 341 составное: 341 = 31 × 11.

Малая теорема Ферма послужила основой множества других результатов в теории чисел и методов проверки чисел на принадлежность к простым – многие из которых используются и по сей день.

Ферма много переписывался со своими современниками, в особенности с монахом по имени Марен Мерсенн. В одном из писем он высказал гипотезу о том, что числа вида 2n+1 всегда будут простыми, если n является степенью двойки. Он проверил это для n = 1, 2, 4, 8 и 16, и был уверен, что в случае, когда n не является степенью двойки, число не обязательно получалось простым. Эти числа называются числами Ферма, и лишь через 100 лет Эйлер показал, что следующее число, 232 + 1 = 4294967297 делится на 641, и следовательно, не является простым.

Числа вида 2n — 1 также служили предметом исследований, поскольку легко показать, что если n – составное, то и само число тоже составное. Эти числа называют числами Мерсенна, поскольку он активно их изучал.

Но не все числа вида 2n — 1, где n – простое, являются простыми. К примеру, 211 — 1 = 2047 = 23 * 89. Впервые это обнаружили в 1536 году.

Многие годы числа такого вида давали математикам наибольшие известные простые числа. Что число M19, было доказано Катальди в 1588 году, и в течение 200 лет было наибольшим известным простым числом, пока Эйлер не доказал, что M31 также простое. Этот рекорд продержался ещё сто лет, а затем Люкас показал, что M127 — простое (а это уже число из 39 цифр), и после него исследования продолжились уже с появлением компьютеров.

В 1952 была доказана простота чисел M521, M607, M1279, M2203 и M2281.

К 2005 году найдено 42 простых чисел Мерсенна. Наибольшее из них, M25964951, состоит из 7816230 цифр.

Работа Эйлера оказала огромное влияние на теорию чисел, в том числе и простых. Он расширил Малую теорему Ферма и ввёл φ-функцию. Факторизовал 5-е число Ферма 232+1, нашёл 60 пар дружественных чисел, и сформулировал (но не смог доказать) квадратичный закон взаимности.

Он первым ввёл методы математического анализа и разработал аналитическую теорию чисел. Он доказал, что не только гармонический ряд ∑ (1/n), но и ряд вида

1/2 + 1/3 + 1/5 + 1/7 + 1/11 +…

получаемый суммой величин, обратных к простым числам, также расходится. Сумма n членов гармонического ряда растёт примерно как log(n), а второй ряд расходится медленнее, как log[ log(n) ]. Это значит, что, например, сумма обратных величин ко всем найденным на сегодняшний день простым числам даст всего 4, хотя ряд всё равно расходится.

На первый взгляд кажется, что простые числа распределены среди целых довольно случайно. К примеру, среди 100 чисел, идущих прямо перед 10000000, встречается 9 простых, а среди 100 чисел, идущих сразу после этого значения – всего 2. Но на больших отрезках простые числа распределены достаточно равномерно. Лежандр и Гаусс занимались вопросами их распределения. Гаусс как-то рассказывал другу, что в любые свободные 15 минут он всегда подсчитывает количество простых в очередной 1000 чисел. К концу жизни он сосчитал все простые числа в промежутке до 3 миллионов. Лежандр и Гаусс одинаково вычислили, что для больших n плотность простых чисел составляет 1/log(n). Лежандр оценил количество простых чисел в промежутке от 1 до n, как

π(n) = n/(log(n) — 1.08366)

А Гаусс – как логарифмический интеграл

π(n) = ∫ 1/log(t) dt

с промежутком интегрирования от 2 до n.

Утверждение о плотности простых чисел 1/log(n) известно как Теорема о распределении простых чисел. Её пытались доказать в течение всего 19 века, а прогресса достигли Чебышёв и Риман. Они связали её с гипотезой Римана – по сию пору не доказанной гипотезой о распределении нулей дзета-функции Римана. Плотность простых чисел была одновременно доказана Адамаром и Валле-Пуссеном в 1896 году.

В теории простых чисел есть ещё множество нерешённых вопросов, некоторым из которых уже многие сотни лет:

• гипотеза о простых числах-близнецах – о бесконечном количестве пар простых чисел, отличающихся друг от друга на 2
• гипотеза Гольдбаха: любое чётное число, начиная с 4, можно представить в виде суммы двух простых чисел
• бесконечно ли количество простых чисел вида n2+ 1 ?
• всегда ли можно найти простое число между n2and (n + 1) 2? (факт, что между n и 2n всегда есть простое число, было доказан Чебышёвым)
• бесконечно ли число простых чисел Ферма? есть ли вообще простые числа Ферма после 4-го?
• существует ли арифметическая прогрессия из последовательных простых чисел для любой заданной длины? например, для длины 4: 251, 257, 263, 269. Максимальная из найденных длина равна 26.
• бесконечно ли число наборов из трёх последовательных простых чисел в арифметической прогрессии?
• n2— n + 41 – простое число для 0 ≤ n ≤ 40. Бесконечно ли количество таких простых чисел? Тот же вопрос для формулы n2 — 79 n + 1601. Эти числа простые для 0 ≤ n ≤ 79.
• бесконечно ли количество простых чисел вида n# + 1? (n# — результат перемножения всех простых чисел, меньших n)
• бесконечно ли количество простых чисел вида n# -1 ?
• бесконечно ли количество простых чисел вида n! + 1?
• бесконечно ли количество простых чисел вида n! – 1?
• если p – простое, всегда ли 2p-1 не содержит среди множителей квадратов простых чисел
• содержит ли последовательность Фибоначчи бесконечное количество простых чисел?
Некоторые считают, что простые числа не стоят глубокого изучения, но они имеют фундаментальное значение для математики. Каждое число может быть представлено уникальным способом в виде простых чисел, умноженных друг на друга. Это значит, что простые числа — это «атомы умножения», маленькие частички, из которых может быть построено что-то большое.

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

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

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

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

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

Как правило, математики не ищут отдельных простых чисел на компьютере, однако они очень заинтересованы в простых числах с особыми свойствами. Есть две известные проблемы: существует ли бесконечное количество простых чисел, которые на один больше, чем квадрат (например, это имеет значение в теории групп), и существует ли бесконечное количество пар простых чисел, отличающихся друг от друга на 2.

Самое большое простое число, вычисленное проектом GIMPS [Great Internet Mersenne Prime Search], можно посмотреть в таблице на официальной странице проекта.

Самые большие близнецы среди простых чисел – это 2003663613 × 2195000 ± 1. Они состоят из 58711 цифр, и были найдены в 2007 году.

Самое большое факториальное простое число (вида n! ± 1) – это 147855! — 1. Оно состоит из 142891 цифр и было найдено в 2002.

Наибольшее праймориальное простое число (число вида n# ± 1) – это 1098133# + 1.

Чтобы записать новое простое число, найденное математиками, потребовалась бы книга более, чем в 7 тысяч страниц. Оно – это небывало большое число – состоит из 23 249 425 цифр. Обнаружить его удалось благодаря проекту распределенных вычислений GIMPS (Great Internet Mersenne Prime Search).

Простые числа – это такие, которые делятся на единицу и на самих себя. И больше ни на что. Найденное ныне относится еще и к так называемым числам Мерсенна, которые имеют вид 2 в степени n минус 1. Выразить рекордное число можно как 2 в степени 77232917 минус 1. Оно стало 50 известным числом Мерсенна.

Простые числа используют в криптографии – для шифрования. Они стоят немалых денег. Например, в 2009 году за одно из простых чисел было выплачена премия в $100 тысяч.

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

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

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

Самым серьезным вызовом для практического применения является сложность нахождения всех простых множителей числа. Если взять число 15, можно быстро определить, что 15=5х3. Но если взять 1000-значное число, вычисление всех его простых множителей займет больше миллиарда лет даже у самого мощного суперкомпьютера в мире. Интернет-безопасность во многом зависит от сложности таких вычислений, потому для безопасности коммуникации важно знать, что кто-то не может просто взять и придумать быстрый способ найти простые множители.

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

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

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

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

[источники]Источники:https://habrahabr.ru/post/276037/https://postnauka.ru/faq/66114

masterok.livejournal.com

---

• 
  Вертолет как работает
• 
  Галактики вселенной названия
• 
  Самые тонкие часы в мире
• 
  Самозавязывающиеся кроссовки найк
• 
  Как доказать что земля имеет форму шара
• 
  Образец emdrive
• 
  Страна лего
• 
  Самая точная в мире винтовка
• 
  Вселенная когда возникла
• 
  Канаверо о пересадке головы
• 
  Астрономические наблюдения выполненные в космосе