WikiSort.ru - Не сортированное

Число Ферма́ — число вида ${\displaystyle F_{n}=2^{2^{n}}+1}$ , где ${\displaystyle n\geqslant 0}$ .

Числа Ферма для ${\displaystyle n=0,1,2,3,4}$ образуют последовательность^[1]:

3, 5, 17, 257, 65537

История

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

${\displaystyle F_{5}=4294967297=641\cdot 6700417}$ .

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

Свойства

• Правильный ${\displaystyle n}$ -угольник можно построить с помощью циркуля и линейки тогда и только тогда, когда ${\displaystyle n=2^{r}\cdot p_{1}\cdot p_{2}\cdots p_{k}}$ (${\displaystyle r=0,1,2,...}$ ) где ${\displaystyle p_{1}...p_{k}}$  — различные простые числа Ферма (теорема Гаусса — Ванцеля).
• Среди чисел вида ${\displaystyle 2^{n}+1}$ простыми могут быть только числа Ферма (то есть n обязано быть степенью 2). Действительно, если у n есть нечётный делитель ${\displaystyle d>1}$ и ${\displaystyle n/d=m}$ , то по теореме Безу:

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

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

• Простоту чисел Ферма можно эффективно установить с помощью теста Пепина.
• На январь 2016 года известно лишь 5 простых чисел Ферма: 3, 5, 17, 257, 65537^[3]. Существование других простых чисел Ферма является открытой проблемой.
• Известно, что ${\displaystyle F_{n}}$ являются составными при ${\displaystyle 5\leq n\leq 32.}$
• Десятичная запись чисел Ферма, больших 5, оканчивается на 17, 37, 57 или 97.
• Каждый делитель числа ${\displaystyle F_{n}}$ при ${\displaystyle n>2}$ имеет вид: ${\displaystyle k\cdot 2^{n+2}+1}$ (Эйлер, Люка, 1878).
• Числа Ферма растут очень быстро: 9-е число больше гугола и 334-е число больше гуголплекса.

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

На 20.01.2019 известны только 5 простых чисел Ферма, при ${\displaystyle n=0,1,2,3,4:}$

${\displaystyle F_{0}=2^{2^{0}}+1=2^{1}+1=3}$ ,

${\displaystyle F_{1}=2^{2^{1}}+1=2^{2}+1=5}$ ,

${\displaystyle F_{2}=2^{2^{2}}+1=2^{4}+1=17}$ ,

${\displaystyle F_{3}=2^{2^{3}}+1=2^{8}+1=257}$ ,

${\displaystyle F_{4}=2^{2^{4}}+1=2^{16}+1=65537}$ .

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

Всего по состоянию на март 2017 года известно 336 разложений на простые числа чисел Ферма, и 292 числа Ферма для которых доказано, что они составные, но их разложение на простые числа неизвестно. Несколько новых разложений на простые числа чисел Ферма находят каждый год.

Ниже приведено разложение чисел Ферма на простые сомножители, при ${\displaystyle n=5,6,7,8,9:}$

${\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}$

${\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}$

${\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}}}$

${\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}}}$

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

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

В другом языковом разделе есть более полная статья Fermat number#Generalized Fermat numbers (англ.). Вы можете помочь проекту, расширив текущую статью с помощью перевода. При этом, для соблюдения правил атрибуции, следует установить шаблон {{переведённая статья}} на страницу обсуждения, либо указать ссылку на статью-источник в комментарии к правке.

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

Примечания

Ссылки

• Леонид Дурман. Гонки по вертикали. Числа Ферма от Эйлера до наших дней. Начало, продолжение, окончание // Компьютерра, 2001, № 393—395.
• Делители чисел Ферма (англ.)
• Wilfrid Keller. Prime Factors of Fermat Numbers (англ.)