Число Ферма

Числа Ферма́ — числа вида [math]\displaystyle{ F_n=2^{2^n}+1 }[/math], где [math]\displaystyle{ n\geqslant 0 }[/math] (последовательность A000215 в OEIS).

При [math]\displaystyle{ n\in\{0,1,2,3,4\} }[/math] числа Ферма простые и равны [math]\displaystyle{ \ 3,\, 5,\, 17,\, 257,\, 65537 }[/math]. Пока других простых чисел Ферма не обнаружено, и неизвестно, существуют ли они при n > 4 или же все прочие числа Ферма — составные.

История

Изучение чисел такого вида начал Ферма, который выдвинул гипотезу, что все они простые. Однако эта гипотеза была опровергнута Эйлером в 1732 году, когда тот нашёл разложение числа [math]\displaystyle{ F_5 }[/math] на простые сомножители:

[math]\displaystyle{ F_5 = 4294967297 = 641 \cdot 6700417 }[/math].

Во времена Ферма считалось верным утверждение, что если [math]\displaystyle{ 2^n \equiv 2~(\text{mod}~n) }[/math], то [math]\displaystyle{ n }[/math] — простое. Это утверждение оказалось неверным (контрпример: [math]\displaystyle{ n=341 }[/math]), однако, по мнению Тадеуша Банахевича, именно оно могло побудить Ферма выдвинуть свою гипотезу, так как утверждение [math]\displaystyle{ 2^{F_n} \equiv 2~(\text{mod}~F_n) }[/math] верно при всех [math]\displaystyle{ n }[/math].

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

На 2022 год известны только 5 простых чисел Ферма — при [math]\displaystyle{ n \in \{0,1,2,3,4\}\colon }[/math]

[math]\displaystyle{ F_0=2^{2^0}+1=2^1+1 = 3; }[/math]

[math]\displaystyle{ F_1=2^{2^1}+1=2^2+1 = 5; }[/math]

[math]\displaystyle{ F_2=2^{2^2}+1=2^4+1 = 17; }[/math]

[math]\displaystyle{ F_3=2^{2^3}+1=2^8+1 = 257; }[/math]

[math]\displaystyle{ F_4=2^{2^4}+1=2^{16}+1 = 65537. }[/math]

Существование других простых чисел Ферма является открытой проблемой. Известно, что [math]\displaystyle{ F_n }[/math] являются составными при [math]\displaystyle{ 5 \le n \le 32. }[/math]

Свойства

• Правильный [math]\displaystyle{ n }[/math]-угольник можно построить с помощью циркуля и линейки тогда и только тогда, когда [math]\displaystyle{ n=2^r\cdot p_1\cdot p_2\cdot\ldots\cdot p_k }[/math] ([math]\displaystyle{ r=0, 1, 2, ... }[/math]), где [math]\displaystyle{ p_1,\dots,p_k }[/math] — различные простые числа Ферма (теорема Гаусса — Ванцеля).
• Среди чисел вида [math]\displaystyle{ 2^n+1 }[/math] простыми могут быть только числа Ферма (то есть число n обязано быть степенью 2). Действительно, если у n есть нечётный делитель [math]\displaystyle{ d\gt 1 }[/math] и [math]\displaystyle{ n/d=m }[/math], то

[math]\displaystyle{ 2^n+1=(2^m+1)(1-2^m+2^{2m}-\cdots+2^{n-m}), }[/math]

и поэтому [math]\displaystyle{ 2^n+1 }[/math] не является простым.

• Простоту некоторых чисел Ферма можно эффективно установить с помощью теста Пепина. Однако числа Ферма сильно растут, и этот тест был удачно применён только для 8 чисел, составность которых ранее не была доказана. По мнению Майера, Пападопулоса и Крэндалла, чтобы выполнить тесты Пепина на последующих числах Ферма, понадобится несколько десятилетий.
• Десятичная запись чисел Ферма, больших 5, оканчивается на 17, 37, 57 или 97.
• Каждый делитель числа [math]\displaystyle{ F_n }[/math] при [math]\displaystyle{ n\gt 2 }[/math] имеет вид [math]\displaystyle{ k \cdot 2^{n+2} + 1 }[/math] (Эйлер, Люка, 1878).
• Числа Ферма растут очень быстро: 9-е число больше гугола, а 334-е число больше гуголплекса.

Разложение на простые

Всего по состоянию на июнь 2022 года найдено 360 простых делителя чисел Ферма. Для 316 чисел Ферма доказано, что они составные, при этом для 2 из них (F₂₀ и F₂₄) до сих пор неизвестно ни одного делителя. Несколько новых делителей чисел Ферма находят каждый год.

Ниже приведено разложение чисел Ферма на простые сомножители, при [math]\displaystyle{ n \in \{5,6,7,8,9\}\colon }[/math]

[math]\displaystyle{ 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; }[/math]

[math]\displaystyle{ F_6=2^{2^6}+1=2^{64}+1 = 18446744073709551617 = (1071 \cdot 2^{6+2}+1) \cdot (262814145745 \cdot 2^{6+2}+1) = 274177 \cdot 67280421310721; }[/math]

[math]\displaystyle{ \begin{array}{lll}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;\end{array} }[/math]

[math]\displaystyle{ \begin{array}{lll}F_8=2^{2^8}+1=2^{256}+1 & = & 115792089237316195423570985008687907853269984665640564039457584007913129639937=\\ & = & (3853149761 \cdot 157 \cdot 2^{8+3}+1) \cdot (1057372046781162536274034354686893329625329 \cdot 31618624099079 \cdot 13 \cdot 7 \cdot 5 \cdot 3 \cdot 2^{8+3}+1) =\\ & = & 1238926361552897 \cdot 93461639715357977769163558199606896584051237541638188580280321;\end{array} }[/math]

[math]\displaystyle{ \begin{array}{lll}F_9=2^{2^9}+1=2^{512}+1 & = & 13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084097=\\ & = & (37 \cdot 2^{9+7}+1) \cdot (43226490359557706629 \cdot 1143290228161321 \cdot 82488781 \cdot 47 \cdot 19 \cdot 2^{9+2}+1) \times \\ && \times (16975143302271505426897585653131126520182328037821729720833840187223 \cdot 17338437577121 \cdot 40644377 \cdot 26813 \cdot 1129 \cdot 2^{9+2}+1) =\\ & = & 2424833 \cdot 7455602825647884208337395736200454918783366342657 \cdot 741640062627530801524787141901937474059940781097519023905821316144415759504705008092818711693940737.\end{array} }[/math]

Обобщённые числа Ферма

Обобщённое число Ферма — число вида [math]\displaystyle{ a^{2^n} + b^{2^n} }[/math]. Числа Ферма являются их частным случаем для [math]\displaystyle{ a = 2 }[/math] и [math]\displaystyle{ b = 1. }[/math]

Ссылки

• Леонид Дурман. Гонки по вертикали. Числа Ферма от Эйлера до наших дней: 1, 2, 3 // Компьютерра, 2001, № 393—395.
• TOP-20 Наибольших делителей чисел Ферма (англ.)
• Леонид Дурман, Luigi Morelli. Координирующий проект FERMATSEARCH (англ.)  (итал.)  (рус.)
• Wilfrid Keller. Prime Factors of Fermat Numbers (англ.)