Русская Википедия:Число Ферма
Числа Ферма́ — числа вида <math>F_n=2^{2^n}+1</math>, где <math>n\geqslant 0</math> (Шаблон:OEIS).
При <math>n\in\{0,1,2,3,4\} </math> числа Ферма простые и равны <math>\ 3,\, 5,\, 17,\, 257,\, 65537; </math>.
Пока других простых чисел Ферма не обнаружено, и неизвестно, существуют ли простые числа при Шаблон:Число или же все прочие числа Ферма — составные.
История
Изучение чисел такого вида начал Ферма, который выдвинул гипотезу, что все они простые. Однако эта гипотеза была опровергнута Эйлером в 1732 году, когда тот нашёл разложение числа <math>F_5</math> на простые сомножители:
- <math> F_5 = 4294967297 = 641 \cdot 6700417</math>.
Во времена Ферма считалось верным утверждение, что если <math>2^n \equiv 2~(\text{mod}~n)</math>, то <math>n</math> — простое, это утверждение оказалось неверным (был найден контрпример: <math>n=341</math>), по мнению Тадеуша Банахевича, именно это могло побудить Ферма выдвинуть свою гипотезу, так как утверждение <math>2^{F_n} \equiv 2~(\text{mod}~F_n)</math> верно при всех <math>n</math>[1].
Простые числа Ферма
На 2023 год известны 5 простых чисел Ферма — при <math>n \in \{0,1,2,3,4\}\colon</math>[2]
- <math>F_0=2^{2^0}+1=2^1+1 = 3;</math>
- <math>F_1=2^{2^1}+1=2^2+1 = 5;</math>
- <math>F_2=2^{2^2}+1=2^4+1 = 17;</math>
- <math>F_3=2^{2^3}+1=2^8+1 = 257;</math>
- <math>F_4=2^{2^4}+1=2^{16}+1 = 65537;</math>
Существование других простых чисел Ферма является открытой проблемой. Известно, что <math>F_n</math> являются составными при <math>5 \le n \le 32</math>, при том, что до 5 все числа Ферма простые.
Свойства
- Правильный <math>n</math>-угольник можно построить с помощью циркуля и линейки тогда и только тогда, когда <math>n=2^r\cdot p_1\cdot p_2\cdot\ldots\cdot p_k</math> (<math>r=0, 1, 2, ...</math>), где <math>p_1,\dots,p_k</math> — различные простые числа Ферма (теорема Гаусса — Ванцеля).
- Среди чисел вида <math>2^n+1</math> простыми могут быть только числа Ферма (то есть число n обязано быть степенью 2). Действительно, если у n есть нечётный делитель <math>d>1</math> и <math>n/d=m</math>, то
- <math>2^n+1=(2^m+1)(1-2^m+2^{2m}-\cdots+2^{n-m}),</math>
- и поэтому <math>2^n+1</math> не является простым.
- Простоту некоторых чисел Ферма можно эффективно установить с помощью теста Пепина. Однако числа Ферма сильно растут, и этот тест был удачно применён только для 8 чисел, составность которых ранее не была доказана. По мнению Майера, Пападопулоса и Крэндалла, чтобы выполнить тесты Пепина на последующих числах Ферма, понадобится несколько десятилетий[3].
- Десятичная запись чисел Ферма, больших 5, оканчивается на 17, 37, 57 или 97.
- Каждый делитель числа <math>F_n</math> при <math>n>2</math> имеет вид <math>k \cdot 2^{n+2} + 1</math> (Эйлер, Люка, 1878).
- Числа Ферма растут очень быстро: 9-е число больше гугола, а 334-е число больше гуголплекса.
Разложение на простые
Всего по состоянию на июнь 2023 года найдено 364 простых делителя чисел Ферма. Для 320 чисел Ферма доказано, что они составные, при этом для 2 из них (F20 и F24) до сих пор неизвестно ни одного делителя[4]. Несколько новых делителей чисел Ферма находят каждый год.
Ниже приведено разложение чисел Ферма на простые сомножители, при <math>n \in \{5,6,7,8,9\}\colon</math>
- <math>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>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>\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>\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>\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>a^{2^n} + b^{2^n}</math>. Числа Ферма являются их частным случаем для <math>a = 2</math> и <math>b = 1.</math>
Примечания
Литература
- Шаблон:Citation
- Шаблон:Citation
- Шаблон:Citation
- Шаблон:Citation — This book contains an extensive list of references.
- Шаблон:Citation
- Шаблон:Citation
- Шаблон:Citation
- Шаблон:Citation
- Шаблон:Citation
Ссылки
- Леонид Дурман. Гонки по вертикали. Числа Ферма от Эйлера до наших дней: 1, 2, 3 // Компьютерра, 2001, № 393—395.
- TOP-20 Наибольших делителей чисел ФермаШаблон:Ref-en
- Леонид Дурман, Luigi Morelli. Координирующий проект FERMATSEARCHШаблон:Ref-en Шаблон:Ref-it Шаблон:Ref-ru
- Wilfrid Keller. Prime Factors of Fermat NumbersШаблон:Ref-en
- ↑ Шаблон:Книга
- ↑ Шаблон:OEIS
- ↑ Richard E. Crandall, Ernst W. Mayer & Jason S. Papadopoulos (2003), The twenty-fourth Fermat number is compositeШаблон:Ref-en
- ↑ Fermat factoring status
