Числа Ферма

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Числа Ферма — числа вида F_n=2^{2^n}+1, где n — неотрицательное целое число.

Числа Ферма для n=0, 1, 2, 3, \dots образуют последовательность:

3, 5, 17, 257, 65537, 4294967297, 18446744073709551617, … (последовательность A000215 в OEIS)

История[править | править вики-текст]

Изучение чисел такого вида начал Ферма, который выдвинул гипотезу, что все они простые. Однако, эта гипотеза была опровергнута Эйлером в 1732 году, нашедшим разложение числа F_5 на простые делители:

 F_5 = 4294967297 = 641 \cdot 6700417

Свойства[править | править вики-текст]

2^n+1=(2^m+1)(1-2^m+2^{2m}-\cdots+2^{n-m}),
и поэтому 2^n+1 не является простым.
  • Простоту чисел Ферма можно эффективно установить с помощью теста Пепина.
  • На июль 2014 года известно лишь 5 простых чисел Ферма: 3, 5, 17, 257, 65537 (последовательность A019434 в OEIS). Существование других простых чисел Ферма является открытой проблемой.
  • Известно, что F_n являются составными при 5 \le n \le 32.
  • Десятичная запись чисел Ферма, больших 5, оканчивается на 7.
  • Каждый делитель числа F_n при n>2 имеет вид k \cdot 2^{n+2} + 1 (Эйлер, Люка, 1878).

Разложение на простые[править | править вики-текст]

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 (262814145745 \cdot 2^{6+2}+1) = 274177 \cdot 67280421310721
\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}
\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}
\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) \cdot \\ && (16975143302271505426897585653131126520182328037821729720833840187223 \cdot 17338437577121 \cdot 40644377 \cdot 26813 \cdot 1129 \cdot 2^{9+2}+1) =\\ & = & 2424833 \cdot 7455602825647884208337395736200454918783366342657  \cdot 741640062627530801524787141901937474059940781097519023905821316144415759504705008092818711693940737\end{array}

Обобщённые числа Ферма[править | править вики-текст]

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

Ссылки[править | править вики-текст]