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

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

Рассмотрим сейчас две формулы, имеющие совсем простой вид:

Очевидно, что формула (8) не всегда даёт простые числа; например, если n — составное число, n = kl, k>1, l>1, то p делится на 2^k — 1 и на 2^l — 1. Но и при простом n получающееся по формуле (8) число может оказаться составным:

2¹¹ – 1 = 2047 = 23 · 89.

Простые числа, получающиеся по формуле (8), называются числами Мерсенна в честь Марена Мерсенна, который ещё в 1664 году указал все простые значения n, не превосходящие 257, для которых, по его мнению, формула (8) даёт простые числа. Однако Мерсенн не дал доказательства; впоследствии выяснилось, что его предсказание было частично ошибочным.

Интерес к числам Мерсенна вызван их связью с так называемыми совершенными числами — числами, равными сумме всех своих делителей, отличных, конечно, от самого числа. Ещё Евклид доказал (докажите и вы), что если простое число p имеет вид, указанный в формуле (8), то число p(p+1)/2 является совершенным. Например,

3 = 2² – 1, 7 = 2³ – 1

простые числа, и соответственно

— совершенные числа. Спустя несколько столетий Леонард Эйлер доказал (попробуйте и здесь свои силы), что все чётные совершенные числа имеют вид, указанный Евклидом. Таким образом, вопрос, конечно или бесконечно множество чётных совершенных чисел, свёлся к вопросу, конечно или бесконечно множество простых чисел Мерсенна, то есть к вопросу, реализует ли формула (8) нашу программу-минимум. Ответ на этот вопрос не известен до сих пор ³.

Формула (9) также не всегда даёт простые числа, например, если n имеет простой нечётный делитель m, то p делится на 2^n/m + 1, а если n само нечётно, то p делится на 3. Таким образом, вместо n в формулу (9) имеет смысл подставлять только 0 и степени числа 2. При n=0, 2⁰, 2¹, 2², 2³ и 2⁴ формула (9) действительно даёт простые числа, и Пьер Ферма, живший в XVII веке, высказал предположение, что и при любом n вида 2^k формула (9) даёт простое число; в его честь простые числа вида 2^(2^k )+1 получили название чисел Ферма. Гипотезу Ферма опроверг Эйлер, указавший, что число 2^(2^5 )+1 делится на 641. В настоящее время известно несколько значений n вида 2^k, при которых по формуле (9) получаются составные числа, но не найдено ни одного нового простого числа Ферма, отличного от указанных выше.

Простые числа Ферма обнаруживают неожиданную связь с геометрией. Выдающийся немецкий математик Карл Фридрих Гаусс доказал, что правильный p-угольник можно построить циркулем и линейкой при простом p в том и только том случае, когда p — число Ферма . Более общий результат таков: правильный m-угольник допускает построение циркулем и линейкой тогда и только тогда, когда m = 2^s· p₁ p₂ ...p_k , где p₁, p₂, ..., p_k — попарно различные простые числа Ферма.