Распечатать запись Распечатать запись

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

Простые числа и их свойства впервые активно начали изучать математики Древней Греции.

Математики школы Пифагора (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 “Начал” Евклид доказывает, что существует бесконечно много простых чисел. Это одно из первых известных доказательств, которое для того, чтобы установить результат, использует метод от противного. Евклид дает также доказательство основной теоремы арифметики: каждое целое число в сущности единственным способом можно представить в виде произведения простых чисел.

Евклид показал также, что если число 2^n – 1 простое, то число 2^{n-1} (2^n – 1) совершенное. Эйлеру (уже гораздо позже, в 1747 г.) удалось доказать, что все четные совершенные числа имеют такой вид. До сих пор неизвестно, существуют ли нечетные совершенные числа.

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

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

Следующие важные достижения были сделаны Ферма в начале XVII века. Он доказал гипотезу Альбера Жирара, что каждое простое число вида 4n + 1 единственным образом представимо в виде суммы двух квадратов и смог показать, как любое число может быть представлено в виде суммы четырех квадратов. Он разработал новый метод факторизации больших чисел, который продемонстрировал на примере числа 2027651281 = 44021 \cdot 46061. Он доказал теорему, которая стала известна как малая теорема Ферма (чтобы отличить ее от его так называемой последней, или большой теоремы).

Она утверждает, что если p простое, то для любого целого a а^{p} \equiv a\pmod{p}.

Это доказывает в одну сторону утверждение, которое называется китайской гипотезой, появившееся примерно на 2000 лет раньше, что целое число n является простым тогда и только тогда, когда число 2^n – 2 делится на n. В обратную сторону это утверждение неверно, так как, например, 2^{341} – 2 делится на 341, хотя 341 = 31 \cdot 11 является составным числом. Малая теорема Ферма является основой для многих других результатов в теории чисел, а также для методов, позволяющих проверить простоту числа, которые до сих пор используются в современных компьютерных программах.

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

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

Не все числа вида 2^n – 1 с простым n являются простыми. Например 2^{11} – 1 = 2047 = 23 \cdot 89 является составным, однако это было впервые отмечено еще в 1536 году.

В течение многих числа такого вида были самыми большими известными простыми числами. Катальди (Cataldi) в 1588 году доказал простоту числа M_{19}, и это было самое большое из известных простых чисел в течение примерно 200 лет, пока Эйлера не доказал, что число M_{31} простое. Этот рекорд рекорд продержался в течение следующего века, а когда Лукас (Lucas) показал, что M_{127} (состоящее из 39 цифр) – простое число, это стало рекордом до появления ЭВМ.

В 1952 году Робинсоном с помощью раннего компьютера была доказана простота чисел Мерсенна M_{521}, M_{607}, M_{1279}, M_{2203} и M_{2281}, и электронный век начался.

К 2005 году было найдено в общей сложности 42 простых числа Мерсенна. Самое большое из них – M_{25964951}, которое состоит из 7816230 десятичных цифр.

Работы Эйлера оказали большое влияние на теорию чисел в целом и ни теорию простых чисел в частности.

Он обобщил малую теорему Ферма и ввел функцию Эйлера \varphi. Как уже говорилось выше, он разложил на множители пятое число Ферма 2^{32} + 1, обнаружил 60 пар дружественных чисел, определенных ранее, и предположил (но не смог доказать) то, что стало известно как квадратичный закон взаимности.

Он был первым, кто понял, что теория чисел может изучаться с помощью инструментов анализа, и, таким образом, положил начало аналитической теории чисел. Ему удалось показать, что не только так называемый гармонический ряд \displaystyle Σ \left(\frac{1}{n}\right) расходится, но и ряд

\displaystyle\frac{1}{2} +\frac{1}{3} + \frac{1}{5} + \frac{1}{7} +\frac{1}{11} + \ldots,

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

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

\pi (n) = n / (\log (n) – 1,08366),

а оценка Гаусса дана в терминах логарифмического интеграла:

\displaystyle\pi (N) = \int_2^n1/\log (t) dt.

Утверждение, что плотность простых чисел равна 1/\log n известно как теорема о распределении простых чисел. Попытки доказать ее продолжалось на протяжении XIX-го века с заметным прогрессом, достигнутым Чебышевым и Риманом, который смог связать эту проблему с тем, что называется гипотезой Римана: до сих пор недоказанной результат о нулях в комплексной плоскости дзета-функции Римана. В конечном итоге утверждение доказали (используя мощные методы комплексного анализа) Адамар и Ла Валле Пуссен в 1896 году.

Есть еще много открытых вопросов (некоторым из них уже сотни лет), связанных с простыми числами.

Вот некоторые нерешенные проблемы

1. Гипотеза простых чисел – близнецов о том, что имеется бесконечно много пар простых чисел, отличающихся на 2.

2. Гипотеза Гольдбаха (выдвинутая в письме C. Гольдбаха к Эйлеру в 1742 г.), что каждое четное число больше 2 можно представить в виде суммы двух простых чисел.

3. Имеется ли бесконечно много простых чисел вида n^2 + 1?
(Дирихле доказал, что каждая арифметическая прогрессия an+b, где a и b взаимно простые, содержит бесконечно много простых членов.)

4. Всегда ли есть простое число между n^2 и (n + 1) 2?
(Тот факт, что всегда есть простое между n и 2n, назывался гипотезой Бертрана и был доказан Чебышевым.)

5. Имеется ли бесконечно много простых чисел Ферма? Действительно, есть ли простое число Ферма после четвертого числа?

6. Существует ли арифметическая прогрессия последовательных простых чисел для любой (конечной) длины? Например, последовательность простых чисел 251, 257, 263, 269, имеет длину 4. Самая большая такая последовательность, которая известна, имеет длину 10.

7. Имеется ли бесконечно много наборов 3 последовательных простых чисел в арифметической прогрессии? (Это верно, если мы опустим слово “последовательных”.)

8. Число n^2-n + 41 простое число при 0 \le n \le 40. Имеется ли бесконечно много простых чисел такого вида? Тот же вопрос относится к числам вида n^2 – 79n + 1601 которое простые при 0\le n \le 79.

9. Существует ли бесконечно много простых чисел вида n\# + 1? (Здесь n\# – это произведение всех простых чисел, не превосходящих n.)

10. Существует ли бесконечно много простых чисел вида n\# – 1?

11. Существует ли бесконечно много простых чисел вида n! + 1?

12. Существует ли бесконечно много простых чисел вида n! – 1?

13. Если p – простое число, 2^p – 1 всегда ли будет свободным от квадратов (т.е. не делится на квадрат простого числа)?

14. Содержит ли последовательность Фибоначчи бесконечно много простых чисел?

Вот последние простые числа, которые мы знаем.

Наибольшее известное простое число (найдено GIMPS [Great Internet Mersenne Prime Search] в августе 2008 года) было 45-м числом Мерсенна – M_{43112609}, которое состоит из 1209780189 десятичных цифр. Совсем недавно было обнаружено новое простое число Мерсенна (сентябрь 2008) M_{37156667}.

Самые большие известные простые числа-близнецы – это 2003663613 \cdot 2195000 ± 1. Они состоят из 58711 цифр, и были объявлены Вотье, Мак-Киббоном и Грибенко в 2007 году.

Наибольшее известное факториальное простое число (простое число вида n! ± 1) – это 34790! – 1. Это число содержит 142891 цифр и было объявлено Маршалем, Кармоди и Куоса в 2002 году.

Наибольший известный простой примориал (простое число вида n\# ± 1, где n\# – произведение всех простых чисел \le n) – это 392113\# + 1. Это число состоит из 169966 цифр и было объявлено Хоером (Heuer) в 2001 году.

J.J. O’Connor, E.F. Robertson, Prime numbers. Перевод статьи http://www-history.mcs.st-and.ac.uk/HistTopics/Prime_numbers.html

Один комментарий

  1. 1 Геннадий:

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

    [Ответить]

Оставьте свой отзыв

Добавить изображение