Самое большое простое число какое: Математики назвали самое большое простое число // Смотрим

«Существует ли самое большое простое число? Как его вычислили? » — Яндекс Кью

Популярное

Сообщества

МатематикаПростые числа+2

Анонимный вопрос

22 февраля 2019  ·

9,3 K

ОтветитьУточнить

Алексей Савватеев

Математика

93

Доктор физико-математических наук, популяризатор математики, МФТИ, ЦЭМИ РАН, ректор…  · 7 мар 2019  · youtube.com/punkmathematics

Самого большого простого числа не существует. Доказательство достаточно простое.

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

Это я воспроизвёл один в один доказательство самого Евклида!

1 эксперт согласен

Азат Ибрагимов

23 августа 2021

А вот и нет, число Райо как раз является самым большим простым числом, а прибавить к нему +1 ничего не изменится… Читать дальше

Комментировать ответ…Комментировать…

Ирина

324

Специалист по подбору персонала в прошлом.
Люблю книги и хорошее кино.  · 22 февр 2019

По теореме Евклида количество простых чисел бесконечно.
Однако, известно наибольшее известное простое число открыл Патрик Ларош, в декабре 2018 года. Оно содержит 24862048 десятичных цифр. Хотя количество простых чисел, превышающих наибольшее известное, остаётся бесконечным.

Комментарий был удалён за нарушение правил

Комментировать ответ…Комментировать…

Вы знаете ответ на этот вопрос?

Поделитесь своим опытом и знаниями

Войти и ответить на вопрос

1 ответ скрыто(Почему?)

23 миллиона знаков: открыто самое большое простое число

06. 01.2018 в 20:33

Наука

37846

Поделиться

Международная коллаборация GIMPS объявила, что 26 декабря 2017 года ей удалось обнаружить новое саое большое простое число. Оно состоит из 23 249 425 знаков, и представляет собой двойку, возведённую в степень 77 232 917, минус 1.

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

На первый взгляд может показаться, что количество простых чисел ограничено, однако существует довольно изящное доказательство, что это не так. Сколько бы простых чисел не было известно человечеству, если умножить их все друг на друга и прибавить 1, новое число также будет простым – при делении на все известные «простые» знаменатели будет оставаться остаток 1. Это доказательство приписывается древнегреческому математику Евклиду и названо в его честь.

Впрочем, новые простые числа современные математики, как правило, ищут не при помощи перемножения известных. Чаще всего они ищутся среди так называемых чисел Мерсенна, получаемые путём возведения двойки в степень n и вычитанием из полученного результата единицы. В прошлом учёные обнаружили, что в случае, если n является простым числом, то с довольно высокой вероятностью простым оказывается и соответствующее число Мерсенна. Именно к этому ряду относятся девять из десяти самых больших простых чисел, известных на сегодняшний день. 31 172 165 + 1. Все остальные крупнейшие простые числа, включая новое, были открыты в рамках проекта GIMPS.

С открытия предыдущего крупнейшего простого числа, состоявшего из 22 338 618 цифр, прошло всего два года, и специалисты GIMPS отмечают, что это данный рекорд был побит неожиданно быстро.

Самое интересное за день в «МК» — в одной вечерней рассылке: подпишитесь на наш канал в Telegram.

Подписаться

Авторы:

• Дмитрий Ерусалимский

Что еще почитать

Что почитать:Ещё материалы

В регионах

• Зерновая сделка приостанавливается из-за теракта в Севастополе

  57249

  Крым

  Фото: Pixabay. com

• Уже 15 погибших: число жертв в развлекательном центре «Полигон» продолжает расти

  Фото

  23335

  Кострома

• Виновником пожара в костромском «Полигоне» оказался военнослужащий из Екатеринбурга?

  18162

  Кострома

• «Вот и извиняшки подъехали»: обматеривший русских и прославлявший Украину в соцсетях бизнесмен с Ямала попросил прощения за свои слова.

  Видео

  14191

  Ямал

  Галина Чебыкина

• Глава Ярославской области рассказал ярославцам, что делать с полученными повестками

  14156

  Ярославль

• Проехала 3000 км: псковичка пытается вернуть домой мобилизованного мужа с правом на отсрочку

  Фото

  11658

  Псков

  Светлана Пикалёва

В регионах:Ещё материалы

50-е известное простое число Мерсенна, когда-либо найденное на компьютере, добровольно участвовало в совместном проекте — ScienceDaily

Новости науки

от исследовательских организаций

2

50-е известное простое число Мерсенна, когда-либо найденное, на компьютере добровольно участвовало в совместном проекте

Дата:

4 января 2018 г.

Источник:

Великий поиск простых чисел Мерсенна в Интернете (GIMPS)

Резюме:

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

Поделиться:

ПОЛНАЯ ИСТОРИЯ

Великий поиск простых чисел Мерсенна в Интернете (GIMPS) обнаружил самое большое известное простое число, 2 ^{77 232 917} -1, имеющее 23 249,425 цифр. Компьютер, предоставленный Джонатаном Пейсом, сделал находку 26 декабря 2017 года. Джонатан — один из тысяч добровольцев, использующих бесплатное программное обеспечение GIMPS.

Новое простое число, также известное как M77232917, вычисляется путем умножения 77 232 917 двоек и последующего вычитания единицы. Это почти на миллион цифр больше, чем предыдущее рекордное простое число, относящееся к особому классу чрезвычайно редких простых чисел, известных как простые числа Мерсенна. Это всего лишь 50-е известное простое число Мерсенна из когда-либо обнаруженных, и найти каждое из них становится все труднее. Простые числа Мерсенна были названы в честь французского монаха Марина Мерсенна, изучавшего эти числа более 350 лет назад. GIMPS, основанная в 1996, обнаружил последние 16 простых чисел Мерсенна. Добровольцы загружают бесплатную программу для поиска этих простых чисел, а каждому, кому посчастливится найти новое простое число, предлагается денежное вознаграждение. Профессор Крис Колдуэлл поддерживает авторитетный веб-сайт, посвященный крупнейшим известным простым числам, и имеет превосходную историю простых чисел Мерсенна.

Доказательство простоты заняло шесть дней безостановочных вычислений на ПК с процессором Intel i5-6600. Чтобы доказать отсутствие ошибок в процессе обнаружения прайма, новый прайм был независимо проверен с использованием четырех разных программ на четырех разных аппаратных конфигурациях.

• Аарон Блоссер проверил это с помощью Prime95 на сервере Intel Xeon за 37 часов.
• Дэвид Стэнфилл проверил это с помощью gpuOwL на графическом процессоре AMD RX Vega 64 за 34 часа.
• Андреас Хеглунд проверил простое число с помощью CUDAlucas, работающего на графическом процессоре NVidia Titan Black, за 73 часа.
• Эрнст Майер также проверил это с помощью собственной программы Mlucas на 32-ядерном сервере Xeon за 82 часа. Андреас Хеглунд также подтвердил, что Mlucas работал на инстансе Amazon AWS за 65 часов.

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

Клиентское программное обеспечение GIMPS Prime95 было разработано основателем Джорджем Вольтманом. Скотт Куровски написал системное программное обеспечение PrimeNet, которое координирует работу компьютеров GIMPS. Аарон Блоссер теперь является системным администратором, обновляя и поддерживая PrimeNet по мере необходимости. У добровольцев есть шанс получить вознаграждение за исследовательское открытие в размере 3000 или 50 000 долларов, если их компьютер обнаружит новое простое число Мерсенна. Следующей важной целью GIMPS является получение награды в размере 150 000 долларов США от Electronic Frontier Foundation за поиск 100-миллионного простого числа.

Заслуга в этом прайме принадлежит не только Джонатану Пейсу за запуск программного обеспечения Prime95, Вольтману за написание программного обеспечения, Куровски и Блоссеру за их работу на сервере Primenet, но и тысячам добровольцев GIMPS, которые просеивали миллионы неосновных кандидаты. В знак признания всех вышеперечисленных людей, официальная заслуга в этом открытии принадлежит «Дж. Пейсу, Г. Вольтману, С. Куровски, А. Блоссеру и др.».

The Great Internet Mersenne Prime Search (GIMPS) была создана 19 января.96 Джорджа Вольтмана, чтобы открыть новый мировой рекорд размера простых чисел Мерсенна. В 1997 году Скотт Куровски позволил GIMPS автоматически использовать мощь тысяч обычных компьютеров для поиска этих «иголок в стоге сена». Большинство участников GIMPS присоединяются к поиску острых ощущений от возможного открытия рекордного, редкого и исторического нового простого числа Мерсенна. Поиск других простых чисел Мерсенна уже начался. Могут быть меньшие, еще не открытые простые числа Мерсенна, и почти наверняка есть более крупные простые числа Мерсенна, ожидающие своего открытия. Любой, у кого есть достаточно мощный компьютер, может присоединиться к GIMPS и стать крупным охотником за праймом, а также, возможно, получить денежную награду за исследования. Все необходимое программное обеспечение можно бесплатно загрузить на сайте www.mersenne.org/download/.

изменить ситуацию: спонсируемая возможность

Источник истории:

Материалы предоставлены Great Internet Mersenne Prime Search (GIMPS) . Примечание. Содержимое можно редактировать по стилю и длине.

Цитировать эту страницу :

• MLA
• АПА
• Чикаго

Великий поиск простых чисел Мерсенна в Интернете (GIMPS). «Самое большое известное простое число обнаружено: 50-е известное простое число Мерсенна, когда-либо найденное на компьютере, добровольно участвовало в совместном проекте». ScienceDaily. ScienceDaily, 4 января 2018 г. .

Великий поиск простых чисел Мерсенна в Интернете (GIMPS). (2018, 4 января). Обнаружено самое большое известное простое число: 50-е известное простое число Мерсенна, когда-либо найденное на компьютере, добровольно участвовало в совместном проекте. ScienceDaily . Получено 13 ноября 2022 г. с сайта www.sciencedaily.com/releases/2018/01/180104164507.htm

Great Internet Mersenne Prime Search (GIMPS). «Самое большое известное простое число обнаружено: 50-е известное простое число Мерсенна, когда-либо найденное на компьютере, добровольно участвовало в совместном проекте». ScienceDaily. www.sciencedaily.com/releases/2018/01/180104164507.htm (по состоянию на 13 ноября 2022 г.).

реклама

Самое большое в мире простое число состоит из 23 249 425 цифр.

Вот почему вы должны заботиться.

Шифрование RSA, один из стандартных способов шифрования данных в сети, требует, чтобы пользователь придумал два больших простых числа и перемножил их.

Eyematrix/Thinkstock

Обновление от 4 января 2018 г.: В среду Great Internet Mersenne Prime Search объявил, что компьютер, принадлежащий Джонатану Пейсу в Джермантауне, штат Теннесси, обнаружил новое простое число. В 23 249425 цифр, число, известное как M77232917, теперь является самым большим известным простым числом.

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

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

Оригинал, 22 января 2016 г. : Ранее на этой неделе BBC News сообщила о важном математическом открытии, поделившись новостью под заголовком «Самое большое известное простое число обнаружено в Миссури». Эта формулировка звучит так, будто это новое простое число — между прочим, это 2 ^{74 207 281} -1 — было найдено посреди какой-то дороги под уличным фонарем. На самом деле это не плохой способ думать об этом.

Мы знаем об этом огромном простом числе благодаря Великому поиску простых чисел Мерсенна в Интернете. Охота Мерсенна, известная как GIMPS, представляет собой крупный проект распределенных вычислений, в рамках которого добровольцы запускают программное обеспечение для поиска простых чисел. Возможно, самым известным аналогом является SETI@home, который ищет признаки внеземной жизни. GIMPS добился более ощутимого успеха, чем SETI: на данный момент обнаружено 15 простых чисел. Блестящее новое простое число, получившее очаровательное прозвище M74207281, является четвертым, найденным математиком из Университета Центрального Миссури Кертисом Купером с помощью программного обеспечения GIMPS. Этот состоит из 22 338 618 цифр.

Простое число — это целое число, единственными делителями которого являются 1 и само себя. Числа 2, 3, 5 и 7 простые, а 4 — нет, потому что его можно разложить на множители как 2 x 2. (Из соображений удобства мы не считаем 1 простым.) М в GIMPS и в M74207281 означает Марина Мерсенна, французского монаха 17 ^-го -го века, изучавшего числа, носящие его имя. Числа Мерсенна на 1 меньше, чем степень числа 2. Простые числа Мерсенна, по логике вещей, — это числа Мерсенна, которые также являются простыми. Число 3 — простое число Мерсенна, потому что оно на единицу меньше, чем 2·9.0035 2 , что равно 4. Следующие несколько простых чисел Мерсенна — 7, 31 и 127.

M74207281 — это 49 ^-е известное простое число Мерсенна. Следующее по величине известное простое число 2 ^{57 885 161} -1 также является простым числом Мерсенна. Так и тот, что после этого. И следующий. И следующий. В целом, 11 крупнейших известных простых чисел — это числа Мерсенна.

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

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

Во-первых, мы знаем, что лишь несколько чисел Мерсенна являются кандидатами на то, чтобы быть простыми числами Мерсенна. Показатель степени n в 2 ⁿ -1 должен быть простым, поэтому нам не нужно проверять, например, 2 ⁶ -1. простые показатели более заманчивы, чтобы попробовать. Наконец, есть специальный тест на простоту — тест Лукаса-Лемера, который можно использовать только для чисел Мерсенна.

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

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

Вы не можете просто найти 300-значное простое число в таблице. (Их около 10 ²⁹⁷ . Даже если бы мы захотели, мы физически не смогли бы записать их все.) Чтобы найти большие простые числа для использования в шифровании RSA, нам нужно проверить случайно сгенерированные числа на простоту. Один из способов сделать это — пробное деление: разделите число на меньшие числа и посмотрите, получится ли когда-нибудь обратно целое число. Для больших простых чисел это занимает слишком много времени. Следовательно, существуют тесты простоты, которые могут определить, является ли число простым, фактически не разлагая его на множители. Тест Лукаса-Лемера — один из лучших.

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

Сколько простых чисел мы пропустили, ища их в основном под уличным фонарем Лукаса-Лемера? Мы не знаем точного ответа, но теорема о простых числах подводит нас достаточно близко. Имеет смысл, что простые числа становятся менее распространенными по мере того, как мы блуждаем по числовой прямой. Целых 40 процентов однозначных чисел являются простыми, 22 процента двузначных чисел являются простыми и только 16 процентов трехзначных чисел. Теорема о простых числах, впервые доказанная в конце 1800-х годов, дает количественную оценку этого падения. Это говорит о том, что в общем случае количество простых чисел меньше n стремится к n/ln(n) по мере увеличения n . (Здесь вместо — натуральный логарифм.)

Мы можем использовать теорему о простых числах, чтобы оценить, сколько пропущенных простых чисел находится между M74207281 и следующим наименьшим простым числом. Мы просто подставляем 2 ^{74 207 281} -1 в n/ln(n) и получаем действительно большое число. Мы можем записать его наиболее компактно, сложив экспоненты: 10 ^{10 7,349} . Это число состоит примерно из 22 338 610 цифр, плюс-минус пара, поэтому мы также можем записать его как 10 9.0035 22 338 610 .

com/_components/slate-paragraph/instances/cq-article-bfed748c5afea437eac5b800efefbb9c-component-17@published»> Еще одно обращение к теореме о простых числах показывает, что существует примерно на 10 ^{17 425 163} простых чисел меньше, чем следующее по величине известное простое число. Это звучит впечатляюще, пока вы не поймете, что 10 ^{17 425 163} меньше 0,0000000000001 процента от 10 ^{22 338 610} .

Остановись и подумай об этом на мгновение. Существует около 10 ^{22 338 610} простых чисел, меньших, чем M74207281, и примерно все они находятся между ним и следующим по величине известным простым числом. Если вы хотите быть милосердным, вы могли бы сказать, что у нас есть некоторые пробелы в наших знаниях о простых числах. Но на самом деле имеет смысл сказать, что у нас есть пробелы в недостатке знаний.