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

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

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

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

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

Мерсенн был в определенном смысле центром науки в свое время, переписываясь с Галилео Галилеем, Рене Декартом, Этьеном Паскалем, Пьером де Ферма и другими коллегами-учеными и философами того времени.

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

Люди пытались доказать, что числа в списке были простыми числами (некоторые на самом деле не были), но задача была сложной из-за размера чисел.

Мерсенн, например, утверждал, что 2¹²⁷ - 1 - простое число. В 1876 году Эдуард Лукас доказал, что это правда. Пройдет 75 лет, прежде чем кто-нибудь найдет более крупное число, и это все еще самое крупное простое число, найденное вручную.

Геометрическая сумма

Предположим, что у нас есть сумма вида

s(x) = 1 + x + x² + x³ + ⋅⋅⋅ x^(n-1)

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

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

Прежде чем двигаться дальше, давайте определим простое число Мерсенна.

Простое число Мерсенна — простое число вида 2^n - 1.

Конечно, не все числа в этой форме являются простыми числами, но оказывается, что верно следующее.

Если число вида 2^n - 1 простое, то n - также простое.

Докажем эту теорему, доказав контрпозитивное (и, следовательно, эквивалентное) утверждение.

Если n не является простым, то 2^n - 1 также не простое.

Доказательство:

Предположим, что n - составное число. Тогда мы можем записать n = ab для некоторых a, b ∈ ℕ с a, b> 1. В силу замкнутой формы суммы степеней, приведенной выше, мы теперь имеем:

что, конечно, доказывает теорему.

Число этой формы, простое или нет, называется числом Мерсенна.

Обратите внимание, что обратное утверждение неверно. У вас может быть число Мерсенна с простой экспонентой, которое является составным, например. 2¹¹ - 1 = 23 ⋅ 89.

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

Загадка

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

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

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

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

Оригинал: Mersenne Primes