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

Числа Ферма — числа вида $F_n=2^{2^n}+1$. Изучение чисел такого вида начал Ферма, который выдвинул гипотезу, что все они простые. Однако, эта гипотеза была опровергнута Эйлером в 1732 году, нашедшим разложение числа F₅ на простые делители:

$F_5 = 4294967297 = 641 \cdot 6700417$

Последовательность чисел Ферма начинается так (последовательность A000215 в OEIS):

$F_0=2^{2^0}+1=2^1+1 = 3$;

$F_1=2^{2^1}+1=2^2+1 = 5$;

$F_2=2^{2^2}+1=2^4+1 = 17$;

$F_3=2^{2^3}+1=2^8+1 = 257$;

$F_4=2^{2^4}+1=2^{16}+1 = 65537$;

$F_5=2^{2^5}+1=2^{32}+1 = 4294967297 = (5 \cdot 2^{5+2}+1) \cdot (52347 \cdot 2^{5+2}+1) = 641 \cdot 6700417$;

$F_6=2^{2^6}+1=2^{64}+1 = 18446744073709551617 = (1071 \cdot 2^{6+2}+1) \cdot (262'814'145'745 \cdot 2^{6+2}+1) = 274177 \cdot 67280421310721$;

$F_7=2^{2^7}+1=2^{128}+1 = 340282366920938463463374607431768211457 = (116'503'103'764'643 \cdot 2^{7+2}+1) \cdot (11'141'971'095'088'142'685 \cdot 2^{7+2}+1) = 59'649'589'127'497'217 \cdot 5'704'689'200'685'129'054'721$;

...

Свойства

• Правильный n-угольник можно построить с помощью циркуля и линейки тогда и только тогда, когда $n=2^r p_1 p_2\dots p_k$, где p_i — различные простые числа Ферма. См. Теорема Гаусса — Ванцеля.
• Среди чисел вида 2ⁿ + 1 простыми могут быть только числа Ферма (т.е. n обязано быть степенью 2-ки). Действительно, если у n есть нечетный делитель m > 1, то по теореме Безу:

$2^n+1=(2^m+1)(1-2^m+2^{2m}-\cdots+2^{n-m}),$

и поэтому 2ⁿ + 1 не является простым.

• На данный момент известно только 5 простых чисел Ферма: 3;5;17;257;65537. Известно, что F_n являются составными при $5 \le n \le 32$.
• Простоту чисел Ферма можно эффективно установить с помощью теста Пепина.

Ссылки

• Леонид Дурман «Гонки по вертикали. Числа Ферма от Эйлера до наших дней: начало, продолжение, окончание». Компьютерра, №№ 393-395, 2001. (альтернативная ссылка)