какое простое число самое большое простое число
Числа. Простые числа.
Натуральные числа, большие единицы и числа, которые не являются простыми, называют составными числами. Т.о., все натуральные числа делятся на 3 класса: единица (имеет 1 делитель), простые числа (имеют 2 делителя) и составные числа (имеют больше 2-х делителей).
Начало последовательности простых чисел выглядит так:
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, …
Если представить натуральные числа как произведение простых, то это будет называться разложение на простые либо факторизация числа.
Самое большое простое число, которое известно.
Некоторые свойства простых чисел.
Допустим, p — простое, и p делит ab, тогда p делит a либо b.
Кольцо вычетов Zn будет называться полем только в случае, если n — простое.
Характеристика всех полей — это нуль либо простое число.
Когда G — конечная группа, у которой порядок |G| делят на p, значит, у G есть элемент порядка p (теорема Коши).
Натуральное p > 1 будет простым лишь в случае, если (p-1)! + 1 можно подулить на p (теорема Вильсона).
Когда n > 1 — натуральное, значит, есть простое p: n 1 — целые взаимно простые числа, содержит нескончаемое число простых чисел (Теорема Дирихле о простых числах в арифметической прогрессии).
Любое простое число, которое большее тройки, можно представить как 6k+1 либо 6k-1, где k — натуральное число. Исходя из этого, когда разность нескольких последовательных простых чисел (при k>1) одинаковая, значит, она точно делится на шесть — к примеру: 251-257-263-269; 199-211-223; 20183-20201-20219.
Теорема Грина-Тао. Есть бесконечные арифметические прогрессии, которые состоят из простых чисел.
Ни одно простое число нельзя представить как n 2k+1 +1, где n>1, k>0. Другими словами, число, которое предшествует простому, не может быть кубом либо более высокой нечётной степенью с основанием, которое больше единицы.
Есть многочлены, у которых множество неотрицательных значений при положительных значениях переменных совпадает с множеством простых чисел. Пример:
Открыто самое большое простое число
Математик из США Кертис Купер получил самое большое из известных на настоящий момент простых чисел — так называемое число Мерсенна. Об открытии сообщается на сайте проекта распределенных вычислений GIMPS (Great Internet Mersenne Prime Search), в рамках которого число и было обнаружено.
Его запись в десятичной системе счисления состоит из 17 425 170 знаков. Для сравнения длина предыдущего рекордсмена составляла 12 978 189 знаков. Простым, напомним, называется число, которое делится только на себя и на единицу.
На проверку простоты нового числа ушло 39 дней работы персонального компьютера в Университете Центрального Миссури, где работает Купер. Независимая проверка была осуществлена сразу тремя исследователями на разных машинах, включая сервер, предоставленный компанией Новартис.
Для Кертиса Купера новый рекорд стал уже третьим — ранее самые большие простые числа ему удавалось обнаруживать в 2005 и 2006 годах. В 2008 году математики из Калифорнийского университета в Лос-Анджелесе побили рекорд Купера, открыв уже упоминавшееся простое число, записываемое 12 978 189 знаками.
За предыдущее открытие проект GIMPS получил премию в 100 тысяч долларов от фонда EFF, обещанную за открытие первого простого числа, записываемого более чем 10 миллионами знаков. Полученные деньги проект разделил на небольшие премии для поощрения следующих открытий — так, Купер с числом Мерсенна претендует на 3 тысячи долларов.
Простые числа Мерсенна — простые числа вида 2 p — 1, где p в свою очередь также простое число. Для нового числа этот показатель равен 57 885 161. Популярность эти числа получили в связи с тем, что к ним удобно применять критерий простоты Люка-Лемера. До настоящего времени бесконечность множества простых чисел Мерсенна не доказана.
Существует ли самое большое простое число? Как его вычислили?
Самого большого простого числа не существует. Доказательство достаточно простое.
Предположим, что есть самое большое простое число. Тогда простых чисел всего должно быть конечное количество: начиная от самого большого, и вниз до числа 2. Возьмем все эти простые числа, и перемножим. Если я перемножаю конечный набор чисел, то получается какое-то конечное число. Может быть, безумное, грандиозное, гротескное: 10 в 10-й в 10-й степени и так далее, многоэтажные башни степеней, но все-таки конечное. Прибавляем к нему единицу. Вопрос: на какие числа может делиться это огромное число плюс один? Прежде всего заметим, что если оно делится хоть на какое-то число, то постепенно, выделяя все меньшие и меньшие делители, мы в конце концов дойдём до простого делителя нашего числа. Тем самым мы установили, что любое число либо само является простым, либо делится на какое-то из простых меньших чисел. Но дело в том, что это число по построению не может делиться ни на одно из простых чисел, потому что предыдущее перед ним число делилось на них все. Но ведь делимость на фиксированное (простое или нет — неважно) число наступает через промежутки, равные этому числу. Получается, что построенное нами число не может быть ни составным (ибо оно не делится ни на какое простое), ни простым (потому что простые мы уже все перебрали). Таким образом мы приходим к математическому (логическому) противоречию, доказывающему, что самого большого простого числа существовать не может.
Это я воспроизвёл один в один доказательство самого Евклида!
10 самых больших и важных чисел
Дети часто задают вопрос: «Какое число самое большое?». Этот вопрос — важный шаг в процессе перехода в мир абстрактных понятий. Ответ, конечно, прост: числа, скорее всего, бесконечны, но есть определенный порог, за которым числа становятся настолько большими, что в них нет смысла, кроме того, что технически они могут существовать. Давайте возьмем десятку гигантских чисел, известных нам, но ограничимся крайне важными понятиями в мире чисел.
Десять в восьмидесятой степени — 1 с 80 нулями — это довольно массивное число, обозначающее примерное число элементарных частиц в известной вселенной, и, говоря элементарные частицы, мы не имеем в виду микроскопические частицы — мы говорим о куда меньших вещах вроде кварков и лептонов — о субатомных частицах. Это число в США и современной Великобритании называют «сто квинквавигинтиллионов». Вроде бы, несложно понять, что это число обозначает количество мельчайших частиц в нашей Вселенной, однако это самое маленькое и простое число в нашем списке.
Один гугол
Слово гугол, несколько измененное, стало часто используемым в современности, благодаря популярной поисковой системе. У этого числа есть интересная история — достаточно просто погуглить. Термин был придуман Милтоном Сироттой в 1938 году, когда ему было 9 лет. И хотя это относительно абстрактное число, и его существование объясняется необходимостью технического существования, ему все-таки нашли применение.
Алексис Лемер поставил мировой рекорд, рассчитав корень тринадцати из стозначного числа. Гугол — это стозначное число, число с сотней нулей. Также предполагается, что от одного до полутора гугол лет с момента Большого Взрыва взорвется самая массивная черная дыра. И тогда Вселенная вступит в так называемую «темную эпоху» — конец той научной вселенной, какой мы ее знаем.
8,5 х 10^185
Длина Планка — это очень маленькая длина, примерно 1,616199 x 10-35, или 0,00000000000000000000000000000616199 метра. В дюймовом кубе этих длин примерно с гугол. Длина и объем Планка играют важную роль в отраслях квантовой физике — например, теории струн — поскольку позволяют производить вычисления на самых мельчайших масштабах. Во вселенной примерно 8,5 x 10^185 объемов Планка. Это достаточно большое число, и ему все же нет практического применения, но оно остается достаточно простым в нашем списке.
2^43,112,609 – 1
Третье по величине число в этом списке — это число всех планковых объемов во Вселенной, и в нем 185 цифр. А в этом числе почти 13 миллионов цифр. Чем это число важно? Это самое большое из известных сегодня простых чисел. Его обнаружили в августе 2008 года в ходе Great Internet Messene Prime Search (GIMPS).
Гуголплекс
Вы наверняка слышали это слово, хотя бы в фильме «Назад в будущее», когда доктор Эммет Браун бормотал «она одна на миллион, одна на миллиард, одна на гуголплекс». Что такое гуголплекс? Помните длину гугола? Единица и сто нулей. А гуголплекс — это десять в степени гугол. Это больше, чем число всех частиц в известной нам части вселенной.
Вы можете отметить, что можно возводить десять в степень гуголплекс и будет еще больше, и так далее, и окажетесь совершенно правы.
Числа Скьюза
Число Скьюза — это верхний предел для математической задачи π(x) > Li(x), хоть и просто выглядящей, но крайне сложной на самом деле. По существу, число Скьюза доказывает, что число x существует и нарушает это правило, если предположить, что гипотеза Римана верна, а число x меньше, чем 10^10^10^36, первое число Скьюза. Даже первое число Скьюза больше гуголплекса. Есть также и самое большое число Скьюза: x меньше, чем 10^10^10^963.
Время возвращения Пуанкаре
Это очень сложная вещь, но основная концепция относительно проста: при наличии достаточного времени, все возможно. Теорема Пуанкаре о возвращении предполагает количество времени, которого было бы достаточно для того, чтобы однажды вся Вселенная вернулась в свое нынешнее состояние, вызванное случайными квантовыми флуктуациями. Короче, «история повторится». Предполагается, что это займет 10^10^10^10^10^1,1 лет.
Число Грэма
В 80-х годах это число попало в Книгу рекордов Гиннесса как самое массивное конечное число, когда-либо использованное в математических доказательствах. Оно было выведено Роном Грэмом как верхний предел для проблем теории Рамси о многоцветных гиперкубах. Число настолько большое, что для его записи используется стрелочная нотация Кнута (метод записи больших чисел) и собственное уравнение Грэма. Метод Кнута и принцип работы стрелок сложно объяснить, но вы можете представить себе это так. 3↑3 превращается в 3^3 или 27, 3↑↑3 превращается в 3^3^3 или 7,625,597,484,987. Вы можете добавить еще одну стрелку к 3↑↑↑3 и выйти на 7,5 триллионов уровней. Само по себе это число значительно больше, чем время возвращения Пуанкаре, поскольку вы можете добавить бесконечное число стрелок, и каждая стрелка будет невероятно увеличивать число.
Число Грэма выглядит так: G=f64(4), где f(n)=3↑^n3. Лучший способ его представить — разложить по полочкам. Первый слой — это 3↑↑↑↑3, что уже невероятно много. Следующий слой — это множество стрелок между тройками. Возьмите эти стрелки и поместите между следующими тройками. Это умножается в 64 раза. Даже сам Грэм не знает первое число, но последние десять вот: 2464195387. Вся наблюдаемая вселенная слишком мала, чтобы вместить в себя обыкновенную десятичную запись числа Грэма.
∞. Бесконечность
Это число известно всем и каждому, оно часто используется для преувеличений — как какой-нибудь «многоллион». Однако это число намного сложнее, чем большинство может представить, и если вы могли представить числа, идущие до этого пункта, именно это число очень странное и противоречивое. Согласно правилам бесконечности, есть бесконечное число нечетных и четных чисел в бесконечности, однако только половина от всех чисел может быть четной. Бесконечность плюс один равна бесконечности, бесконечность минус один равна бесконечности, бесконечность плюс бесконечность равна бесконечности, деленная пополам — тоже бесконечность, бесконечность минус бесконечность — никто не знает, бесконечность, деленная на бесконечность, будет, скорее всего, 1.
Ученые полагают, что в известной вселенной около 10^80 субатомных частиц, но это только известная вселенная. Некоторые предполагают, что вселенная бесконечна. Если это так, то математически достоверно, что есть другая Земля где-то там, где каждый атом складывается таким же образом, как и мы, и наша Земля. Шанс того, что копия Земли существует, невероятно мал, но в бесконечной вселенной это не только может произойти, но и бесконечно много раз.
В бесконечность верят не все. Израильский профессор математики Дорон Зильбергер утверждает, что по его мнению, числа не будут продолжаться вечно, и найдется настолько большое число, что когда вы добавите к нему единицу, вы придете к нулю. И хотя это число едва ли когда будет обнаружено и едва ли кто сможет его вообразить, бесконечность является важной частью математической философии.
Новый год, новые рекорды: найдено 50-е простое число Мерсенна
Новое простое число, также известное как M77232917, вычислено перемножением 77 232 917 двоек и вычитанием единицы. Оно примерно на один миллион разрядов больше, чем предыдущее рекордное простое число, в особом классе исключительно редких простых, известных как числа Мерсенна. Это всего пятидесятое открытое простое число Мерсенна; вычисление каждого последующего становится сложнее. Простые числа Мерсенна названы по имени французского монаха Марина Мерсенна, изучавшего эти числа больше 350 лет назад. Основанная в 1996 году GIMPS обнаружила последние 16 простых чисел Мерсенна. Волонтёры скачивают бесплатную программу для поиска этих простых чисел и имеют шанс выиграть денежный приз, если им повезёт найти новое число.
У профессора Криса Колдуэлла есть авторитетный веб-сайт, посвящённый самым большим известным простым числам с замечательной историей простых чисел Мерсенна.
Проверка простоты заняла шесть дней безостановочных вычислений на PC с процессором Intel i5-6600. Чтобы доказать, что в процессе обнаружения простых чисел нет ошибок, новое простое число проверяется в четырёх разных программах на четырёх различных конфигурациях оборудования.
Клиентское ПО Prime95 разработано основателем GIMPS Джорджем Уолтманом. Скотт Куровски написал системное ПО PrimeNet, координирующее компьютеры GIMPS. Аарон Блоссер теперь работает системным администратором и при необходимости выполняет обновление и обслуживание PrimeNet. Волонтёры имеют шанс получить вознаграждение в 3 000 или 50 000 долларов, если их компьютер откроет новое простое число Мерсенна. Следующей крупной целью GIMPS является выигрыш учреждённой Electronic Frontier Foundation награды в 150 000 долларов, которая будет вручена за нахождение простого числа со 100 000 000 разрядов.
Мы признательны за нахождение этого простого числа не только Джонатану Пейсу, выполнявшему на своём компьютере ПО Prime95: Уолтману за написанное ПО, Куровски и Блоссеру за их работу с сервером Primenet, а также тысячам добровольцев GIMPS, просеявшим миллионы вариантов чисел. В благодарность всем этим людям официально это открытие приписывается «Дж. Пейсу, Дж. Уолтману, С. Куровски, А. Блоссеру и коллегам».
Про Great Internet Mersenne Prime Search
Организация Great Internet Mersenne Prime Search (GIMPS) была сформирована в январе 1996 года Джорджем Уолтмана для нахождения новых мировых рекордов простых чисел Мерсенна. В 1997 году Скотт Куровски обеспечил GIMPS возможность использовать мощь тысяч обычных компьютеров для поиска этих «иголок в стоге сена». Большинство участников GIMPS вступило в организацию ради захватывающей возможности обнаружения рекордного, редкого и исторического нового простого числа Мерсенна. Поиск следующих простых чисел Мерсенна уже продолжается. Возможно, существуют и меньше, но пока ненайденные простые, и почти абсолютно точно есть бОльшие, ждущие своего обнаружения. Любой человек с достаточно мощным компьютером может присоединиться к GIMPS и стать охотником за большими простыми числами с возможностью получить денежную награду за своё открытие. Всё необходимое ПО можно бесплатно скачать по адресу www.mersenne.org/download/. GIMPS сформирована как Mersenne Research, Inc., некоммерческая научная благотворительная организация 501(с)(3). Подробнее об этом можно прочитать на www.mersenneforum.org и www.mersenne.org; также принимаются добровольные пожертвования.
Дополнительная информация о простых числах Мерсенна
Простые числа давно восхищали и любителей, и профессионалов математики. Целое число больше единицы называется простым числом, если его единственными делителями являются единица и оно само. Первые простые числа: 2, 3, 5, 7, 11 и т.д. Например, число 10 не является простым, потому что делится на 2 и 5. Простое число Мерсенна — это простое число, имеющее вид 2 P — 1. Первыми простыми числами Мерсенна являются 3, 7, 31 и 127, соответствующие P = 2, 3, 5 и 7. Пока известно 50 простых чисел Мерсенна.
Простые числа Мерсенна были в центре внимания теории чисел с тех пор, когда их впервые рассмотрел Евклид около 350 до нашей эры. Человек, именем которого назвали эти числа, французский монах Марин Мерсенн (1588-1648 гг.), создал знаменитую гипотезу о том, при каких значениях P можно получить простое число. Чтобы подтвердить эту гипотезу, потребовались 300 лет и несколько важных открытий.
Сегодня есть мало практических применений этого простого числа, что заставляет некоторых задаваться вопросом: «Зачем вообще искать такие большие простые числа»? Подобные сомнения существовали и несколько десятилетий назад, пока наконец не были разработаны важные криптографические алгоритмы на основе простых чисел. Ещё семь хороших причин для поиска больших простых чисел изложены здесь.
Предыдущие открытия простых чисел Мерсенна в рамках GIMPS были совершены участниками из разных стран.
В январе 2016 года Кёртис Купер с коллегами обнаружили 49-е известное простое число Мерсенна в США.
В январе 2013 года тот же Кёртис Купер с коллегами нашли 48-е известное простое число Мерсенна.
В апреле 2009 года Одд Магнар Стриндмо с коллегами обнаружили 47-е известное простое число Мерсенна в Норвегии.
В сентябре 2008 году Ханс-Микаел Эльвених с коллегами открыли 46-е известное простое число Мерсенна в Германии.
В августе 2008 года Эдсон Смит с коллегами нашли 45-е число в США.
В сентябре 2006 года Кёртис Купер, Стивен Бун и коллеги обнаружили 44-е простое число Мерсенна.
В декабре 2005 года Кёртис Купер, Стивен Бун и коллеги нашли 43-е число Мерсенна.
В феврале 2005 года доктор Мартин Новак с коллегами вычислили в Германии 42-е известное простое число Мерсенна.
В мае 2004 года Джош Финдли с коллегами обнаружили 41-е простое число Мерсенна.
В ноябре 2003 года Майкл Шэфер с коллегами нашли 40-е известное простое число Мерсенна в США.
В ноябре 2001 года Майкл Кэмерон с коллегами вычислили 39-е простое число Мерсенна в Канаде.
В июне 1999 года Найан Хаджратвала с коллегами обнаружили 38-е простое число Мерсенна в США.
В январе 1998 года Роланд Кларксон с коллегами обнаружили 37-е простое число Мерсенна в США.
В августе 1997 года Гордон Спенс с коллегами нашли 36-е простое число Мерсенне в США.
В ноябре 1996 года Жоэль Арменго с коллегами обнаружили 35-е известное простое число Мерсенна во Франции.
Арифметические алгоритмы, лежащие в основе проекта GIMPS, имеют уникальную историю. Программы, нашедшие последние большие простые числа Мерсенна, основаны на специальном алгоритме. В начале 1990-х ныне покойный Ричард Крэндэлл, выдающийся учёный из Apple, обнаружил способы удвоения скорости выполнения свёрток — очень больших операций умножения. Этот метод применим не только ко поиску простых чисел, но и к другим аспектам вычислений. В процессе работы над этим проектом он также запатентовал систему шифрования Fast Elliptic Encryption, которая теперь принадлежит Apple Computer. В ней для быстрой шифровки и дешифровки сообщений используются простые числа Мерсенна. Джордж Уолтман реализовал алгоритм Крэндэлла на языке ассемблера, создав таким образом программу поиска простых чисел с беспрецедентной эффективностью. Эта работа привела к созданию успешного проекта GIMPS.
Школьные учителя используют GIMPS, чтобы заинтересовать своих учеников математикой. Студенты, запустившие на своих компьютерах ПО, вносят свой вклад в математические исследования.
Дополнение из поста Джона Д. Кука.
Это число содержит состоит из 23 249 425 разрядов при записи в десятичном виде.
В двоичном виде 2 p – 1 является последовательностью из p единиц. Например, 31 = 2 5 — 1 равно в двоичном виде 11111. То есть в двоичном виде новое рекордное простое число является строкой из 77 232 917 единиц.
Двоичное число можно преобразовать в шестнадцатеричное (основание 16), начав с правого конца и преобразуя блоки из четырёх бит в шестнадцатеричные числа. Например, для преобразования 101101111 в HEX, мы разобьём число на три блока: 1, 0110 и 1111. Эти блоки преобразуются в 1, 6 и F, то есть двоичное 101101111 соответствует шестнадцатеричному 16F.
Далее, 77 232 917 = 19 308 229 * 4 + 1, то есть мы разбиваем нашу строку из 77 232 917 единиц в группы из четырёх цифр, получив один оставшийся бит, за которым следуют 19 308 229 групп из четырёх цифр. Это значит, что в шестнадцатеричной записи новое рекордное простое число имеет вид 1FFF…FFF — единица, за которой следуют 19 308 229 F.
Новый рекорд — это 50-е простое число Мерсенна. Простое число Мерсенна — это простое число на единицу меньше степени двойки, т.е. имеет вид 2 p – 1. Оказалось, что для простоты 2 p – 1 число p тоже должно быть простым. В случае нового рекорда 77 232 917 является простым.
Неизвестно, существует ли бесконечное количество простых чисел Мерсенна. Но теперь мы знаем, что их как минимум 50.
Все последние рекорды простых чисел были числами Мерсенна, потому что существует алгоритм проверки того, является ли число вида 2 p – 1 простым (тест Люка — Лемера).