Число Ферма

Разделы:

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

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

3, 5, 17, 257, 65537

Содержание

История

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

F5=4294967297=641⋅6700417{displaystyle F_{5}=4294967297=641cdot 6700417}

{displaystyle F_{5}=4294967297=641cdot 6700417}

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

Свойства

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

2n+1=(2m+1)(1−2m+22m−⋯+2n−m),{displaystyle 2^{n}+1=(2^{m}+1)(1-2^{m}+2^{2m}-cdots +2^{n-m}),}

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

и поэтому 2n+1{displaystyle 2^{n}+1}

2^{n}+1

не является простым.

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

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

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

F0=220+1=21+1=3{displaystyle F_{0}=2^{2^{0}}+1=2^{1}+1=3}

F_{0}=2^{{2^{0}}}+1=2^{1}+1=3

F1=221+1=22+1=5{displaystyle F_{1}=2^{2^{1}}+1=2^{2}+1=5}

F_{1}=2^{{2^{1}}}+1=2^{2}+1=5

F2=222+1=24+1=17{displaystyle F_{2}=2^{2^{2}}+1=2^{4}+1=17}

F_{2}=2^{{2^{2}}}+1=2^{4}+1=17

F3=223+1=28+1=257{displaystyle F_{3}=2^{2^{3}}+1=2^{8}+1=257}

F_{3}=2^{{2^{3}}}+1=2^{8}+1=257

F4=224+1=216+1=65537{displaystyle F_{4}=2^{2^{4}}+1=2^{16}+1=65537}

F_{4}=2^{{2^{4}}}+1=2^{{16}}+1=65537

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

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

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

F5=225+1=232+1=4294967297=(5⋅25+2+1)⋅(52347⋅25+2+1)=641⋅6700417{displaystyle F_{5}=2^{2^{5}}+1=2^{32}+1=4294967297=(5cdot 2^{5+2}+1)cdot (52347cdot 2^{5+2}+1)=641cdot 6700417}

F_{5}=2^{{2^{5}}}+1=2^{{32}}+1=4294967297=(5cdot 2^{{5+2}}+1)cdot (52347cdot 2^{{5+2}}+1)=641cdot 6700417

F6=226+1=264+1=18446744073709551617=(1071⋅26+2+1)⋅(262814145745⋅26+2+1)=274177⋅67280421310721{displaystyle F_{6}=2^{2^{6}}+1=2^{64}+1=18446744073709551617=(1071cdot 2^{6+2}+1)cdot (262814145745cdot 2^{6+2}+1)=274177cdot 67280421310721}

F_{6}=2^{{2^{6}}}+1=2^{{64}}+1=18446744073709551617=(1071cdot 2^{{6+2}}+1)cdot (262814145745cdot 2^{{6+2}}+1)=274177cdot 67280421310721

F7=227+1=2128+1=340282366920938463463374607431768211457==(116503103764643⋅27+2+1)⋅(11141971095088142685⋅27+2+1)==59649589127497217⋅5704689200685129054721{displaystyle {begin{array}{lll}F_{7}=2^{2^{7}}+1=2^{128}+1&=&340282366920938463463374607431768211457=\&=&(116,503,103,764,643cdot 2^{7+2}+1)cdot (11,141,971,095,088,142,685cdot 2^{7+2}+1)=\&=&59,649,589,127,497,217cdot 5,704,689,200,685,129,054,721end{array}}}

{begin{array}{lll}F_{7}=2^{{2^{7}}}+1=2^{{128}}+1&=&340282366920938463463374607431768211457=\&=&(116,503,103,764,643cdot 2^{{7+2}}+1)cdot (11,141,971,095,088,142,685cdot 2^{{7+2}}+1)=\&=&59,649,589,127,497,217cdot 5,704,689,200,685,129,054,721end{array}}

F8=228+1=2256+1=115792089237316195423570985008687907853269984665640564039457584007913129639937==(3853149761⋅157⋅28+3+1)⋅(1057372046781162536274034354686893329625329⋅31618624099079⋅13⋅7⋅5⋅3⋅28+3+1)==1238926361552897⋅93461639715357977769163558199606896584051237541638188580280321{displaystyle {begin{array}{lll}F_{8}=2^{2^{8}}+1=2^{256}+1&=&115792089237316195423570985008687907853269984665640564039457584007913129639937=\&=&(3853149761cdot 157cdot 2^{8+3}+1)cdot \&&(1057372046781162536274034354686893329625329cdot 31618624099079cdot 13cdot 7cdot 5cdot 3cdot 2^{8+3}+1)=\&=&1238926361552897cdot 93461639715357977769163558199606896584051237541638188580280321end{array}}}

{begin{array}{lll}F_{8}=2^{{2^{8}}}+1=2^{{256}}+1&=&115792089237316195423570985008687907853269984665640564039457584007913129639937=\&=&(3853149761cdot 157cdot 2^{{8+3}}+1)cdot \&&(1057372046781162536274034354686893329625329cdot 31618624099079cdot 13cdot 7cdot 5cdot 3cdot 2^{{8+3}}+1)=\&=&1238926361552897cdot 93461639715357977769163558199606896584051237541638188580280321end{array}}

F9=229+1=2512+1=13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084097==(37⋅29+7+1)⋅(43226490359557706629⋅1143290228161321⋅82488781⋅47⋅19⋅29+2+1)⋅(16975143302271505426897585653131126520182328037821729720833840187223⋅17338437577121⋅40644377⋅26813⋅1129⋅29+2+1)==2424833⋅7455602825647884208337395736200454918783366342657⋅741640062627530801524787141901937474059940781097519023905821316144415759504705008092818711693940737{displaystyle {begin{array}{lll}F_{9}=2^{2^{9}}+1=2^{512}+1&=&13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084097=\&=&(37cdot 2^{9+7}+1)cdot \&&(43226490359557706629cdot 1143290228161321cdot 82488781cdot 47cdot 19cdot 2^{9+2}+1)cdot \&&(16975143302271505426897585653131126520182328037821729720833840187223cdot 17338437577121cdot 40644377cdot 26813cdot 1129cdot 2^{9+2}+1)=\&=&2424833cdot 7455602825647884208337395736200454918783366342657cdot 741640062627530801524787141901937474059940781097519023905821316144415759504705008092818711693940737end{array}}}

{begin{array}{lll}F_{9}=2^{{2^{9}}}+1=2^{{512}}+1&=&13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084097=\&=&(37cdot 2^{{9+7}}+1)cdot \&&(43226490359557706629cdot 1143290228161321cdot 82488781cdot 47cdot 19cdot 2^{{9+2}}+1)cdot \&&(16975143302271505426897585653131126520182328037821729720833840187223cdot 17338437577121cdot 40644377cdot 26813cdot 1129cdot 2^{{9+2}}+1)=\&=&2424833cdot 7455602825647884208337395736200454918783366342657cdot 741640062627530801524787141901937474059940781097519023905821316144415759504705008092818711693940737end{array}}

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

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

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

Примечания

↑ последовательность A000215 в OEIS
↑ В. Серпинский. 250 задач по теории чисел. — Просвещение, 1968.
↑ последовательность A019434 в OEIS

Ссылки

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