Число Ферма
Числа Ферма — числа вида F n = 2 2 n + 1 {displaystyle F_{n}=2^{2^{n}}+1} , где n ⩾ 0 {displaystyle ngeqslant 0} (последовательность A000215 в OEIS).
При n = 0 , 1 , 2 , 3 , 4 {displaystyle n=0,,1,,2,,3,,4 } числа Ферма простые и равны 3 , 5 , 17 , 257 , 65537 {displaystyle 3,,5,,17,,257,,65537} . Пока других простых чисел Ферма не обнаружено, и неизвестно, существуют ли они при n>4, или же все прочие числа Ферма — составные.
История
Изучение чисел такого вида начал Ферма, который выдвинул гипотезу, что все они простые. Однако эта гипотеза была опровергнута Эйлером в 1732 году, нашедшим разложение числа F 5 {displaystyle F_{5}} на простые сомножители:
F 5 = 4294967297 = 641 ⋅ 6700417 {displaystyle F_{5}=4294967297=641cdot 6700417} .Во времена Ферма считалось верным утверждение, что если 2 n ≡ 2 ( mod n ) {displaystyle 2^{n}equiv 2{pmod {n}}} , то n {displaystyle n} — простое. Это утверждение оказалось неверным (контрпример: n = 341 {displaystyle n=341} ), однако, по мнению Тадеуша Банахевича, именно оно могло побудить Ферма выдвинуть свою гипотезу, так как утверждение 2 F n ≡ 2 ( mod F n ) {displaystyle 2^{F_{n}}equiv 2{pmod {F_{n}}}} верно при всех n {displaystyle n} .
Простые числа Ферма
На 2020 год известны только 5 простых чисел Ферма, при n = 0 , 1 , 2 , 3 , 4 : {displaystyle n=0,,1,,2,,3,,4:}
F 0 = 2 2 0 + 1 = 2 1 + 1 = 3 {displaystyle F_{0}=2^{2^{0}}+1=2^{1}+1=3} , F 1 = 2 2 1 + 1 = 2 2 + 1 = 5 {displaystyle F_{1}=2^{2^{1}}+1=2^{2}+1=5} , F 2 = 2 2 2 + 1 = 2 4 + 1 = 17 {displaystyle F_{2}=2^{2^{2}}+1=2^{4}+1=17} , F 3 = 2 2 3 + 1 = 2 8 + 1 = 257 {displaystyle F_{3}=2^{2^{3}}+1=2^{8}+1=257} , F 4 = 2 2 4 + 1 = 2 16 + 1 = 65537 {displaystyle F_{4}=2^{2^{4}}+1=2^{16}+1=65537} .Существование других простых чисел Ферма является открытой проблемой. Известно, что F n {displaystyle F_{n}} являются составными при 5 ≤ n ≤ 32 {displaystyle 5leq nleq 32} .
Свойства
- Правильный n {displaystyle n} -угольник можно построить с помощью циркуля и линейки тогда и только тогда, когда n = 2 r ⋅ p 1 ⋅ p 2 ⋅ … ⋅ p k {displaystyle n=2^{r}cdot p_{1}cdot p_{2}cdot ldots cdot p_{k}} ( r = 0 , 1 , 2 , . . . {displaystyle r=0,1,2,...} ), где p 1 , … , p k {displaystyle p_{1},dots ,p_{k}} — различные простые числа Ферма (теорема Гаусса — Ванцеля).
- Среди чисел вида 2 n + 1 {displaystyle 2^{n}+1} простыми могут быть только числа Ферма (то есть n обязано быть степенью 2). Действительно, если у n есть нечётный делитель d > 1 {displaystyle d>1} и n / d = m {displaystyle n/d=m} , то
- Простоту чисел Ферма можно эффективно установить с помощью теста Пепина.
- Десятичная запись чисел Ферма, больших 5, оканчивается на 17, 37, 57 или 97.
- Каждый делитель числа F n {displaystyle F_{n}} при n > 2 {displaystyle n>2} имеет вид: k ⋅ 2 n + 2 + 1 {displaystyle kcdot 2^{n+2}+1} (Эйлер, Люка, 1878).
- Числа Ферма растут очень быстро: 9-е число больше гугола и 334-е число больше гуголплекса.
Разложение на простые
Всего по состоянию на октябрь 2020 года найдено 354 простых делителя чисел Ферма. Для 310 чисел Ферма доказано, что они составные, при этом для 2 из них (F20 и F24) до сих пор неизвестно ни одного делителя! . Несколько новых делителей чисел Ферма находят каждый год.
Ниже приведено разложение чисел Ферма на простые сомножители, при n = 5 , 6 , 7 , 8 , 9 : {displaystyle n=5,,6,,7,,8,,9:}
F 5 = 2 2 5 + 1 = 2 32 + 1 = 4294967297 = ( 5 ⋅ 2 5 + 2 + 1 ) ⋅ ( 52347 ⋅ 2 5 + 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 6 = 2 2 6 + 1 = 2 64 + 1 = 18446744073709551617 = ( 1071 ⋅ 2 6 + 2 + 1 ) ⋅ ( 262814145745 ⋅ 2 6 + 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 7 = 2 2 7 + 1 = 2 128 + 1 = 340282366920938463463374607431768211457 = = ( 116 503 103 764 643 ⋅ 2 7 + 2 + 1 ) ⋅ ( 11 141 971 095 088 142 685 ⋅ 2 7 + 2 + 1 ) = = 59 649 589 127 497 217 ⋅ 5 704 689 200 685 129 054 721 ; {displaystyle {egin{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,721;end{array}}} F 8 = 2 2 8 + 1 = 2 256 + 1 = 115792089237316195423570985008687907853269984665640564039457584007913129639937 = = ( 3853149761 ⋅ 157 ⋅ 2 8 + 3 + 1 ) ⋅ ( 1057372046781162536274034354686893329625329 ⋅ 31618624099079 ⋅ 13 ⋅ 7 ⋅ 5 ⋅ 3 ⋅ 2 8 + 3 + 1 ) = = 1238926361552897 ⋅ 93461639715357977769163558199606896584051237541638188580280321 ; {displaystyle {egin{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 93461639715357977769163558199606896584051237541638188580280321;end{array}}} F 9 = 2 2 9 + 1 = 2 512 + 1 = 13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084097 = = ( 37 ⋅ 2 9 + 7 + 1 ) ⋅ ( 43226490359557706629 ⋅ 1143290228161321 ⋅ 82488781 ⋅ 47 ⋅ 19 ⋅ 2 9 + 2 + 1 ) × × ( 16975143302271505426897585653131126520182328037821729720833840187223 ⋅ 17338437577121 ⋅ 40644377 ⋅ 26813 ⋅ 1129 ⋅ 2 9 + 2 + 1 ) = = 2424833 ⋅ 7455602825647884208337395736200454918783366342657 ⋅ 741640062627530801524787141901937474059940781097519023905821316144415759504705008092818711693940737. {displaystyle {egin{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) imes && imes (16975143302271505426897585653131126520182328037821729720833840187223cdot 17338437577121cdot 40644377cdot 26813cdot 1129cdot 2^{9+2}+1)=&=&2424833cdot 7455602825647884208337395736200454918783366342657cdot 741640062627530801524787141901937474059940781097519023905821316144415759504705008092818711693940737.end{array}}}Обобщённые числа Ферма
Обобщённое число Ферма — число вида a 2 n + b 2 n {displaystyle a^{2^{n}}+b^{2^{n}}} . Числа Ферма являются обобщёнными числами Ферма для a = 2 {displaystyle a=2} и b = 1 {displaystyle b=1} .