Číslo Fermata - Fermat number
Pojmenoval podle | Pierre de Fermat |
---|---|
Ne. známých výrazů | 5 |
Domnělý Ne. podmínek | 5 |
Subsekvence z | Fermat čísla |
První termíny | 3, 5, 17, 257, 65537 |
Největší známý termín | 65537 |
OEIS index | A019434 |
v matematika, a Číslo Fermata, pojmenoval podle Pierre de Fermat, který je nejprve studoval, je a kladné celé číslo formuláře
kde n je nezáporné celé číslo. Prvních pár Fermatových čísel je:
Pokud 2k +1 je primární, a k > 0, lze ukázat, že k musí být síla dvou. (Li k = ab kde 1 ≤ A, b ≤ k a b je zvláštní, pak 2k + 1 = (2A)b + 1 ≡ (−1)b + 1 = 0 (mod 2A + 1). Vidět níže pro úplný důkaz.) Jinými slovy, každé prvočíslo formuláře 2k + 1 (jiné než 2 = 20 + 1) je Fermatovo číslo a tato prvočísla se nazývají Fermat připraví. Od roku 2019 jsou jediné známé Fermatovy prvočísla F0, F1, F2, F3, a F4 (sekvence A019434 v OEIS ).
Základní vlastnosti
Čísla Fermat splňují následující relace opakování:
pro n ≥ 1,
pro n ≥ 2. Každý z těchto vztahů lze prokázat matematická indukce. Z druhé rovnice můžeme odvodit Goldbachova věta (pojmenoval podle Christian Goldbach ): žádná dvě čísla Fermat sdílet společný celočíselný faktor větší než 1. Chcete-li to vidět, předpokládejme, že 0 ≤ i < j a Fi a Fj mají společný faktor A > 1. Potom A rozděluje obě
a Fj; proto A dělí jejich rozdíl, 2. Protože A > 1, toto síly A = 2. Toto je rozpor, protože každé číslo Fermata je jasně liché. Jako důsledek, získáváme další důkaz o nekonečnost prvočísel: pro každé Fn, vyberte hlavní faktor strn; pak sekvence {strn} je nekonečná posloupnost odlišných prvočísel.
Další vlastnosti
- Žádný Fermat prime nelze vyjádřit jako rozdíl dvou strth síly, kde str je zvláštní prime.
- S výjimkou F0 a F1, poslední číslice čísla Fermat je 7.
- The součet vzájemných všech Fermatových čísel (sekvence A051158 v OEIS ) je iracionální. (Solomon W. Golomb, 1963)
Primalita Fermatových čísel
Fermatova čísla a Fermatova prvočísla nejprve studoval Pierre de Fermat, který domnělý že všechna Fermatova čísla jsou prvočísla. Ve skutečnosti prvních pět Fermatových čísel F0, ..., F4 jsou snadno prokazatelné jako hlavní. Fermatova domněnka byla vyvrácena Leonhard Euler v roce 1732, když to ukázal
Euler dokázal, že každý faktor Fn musí mít formu k 2n+1 + 1 (později vylepšeno na k 2n+2 + 1 od Lucas ).
Tých 641 je faktorem F5 lze odvodit z rovnosti 641 = 27 × 5 + 1 a 641 = 24 + 54. Z první rovnosti vyplývá, že 27 × 5 ≡ −1 (mod 641), a proto (zvýšení na čtvrtou mocninu), že 228 × 54 ≡ 1 (mod 641). Na druhé straně z druhé rovnosti vyplývá, že 54 ≡ −24 (mod 641). Tyto shody naznačují, že 232 ≡ −1 (mod 641).
Fermat si byl pravděpodobně vědom formy faktorů, které později prokázal Euler, a tak se zdá být zvědavé, že se mu nepodařilo provést přímý výpočet a najít faktor.[1] Jedno běžné vysvětlení je, že Fermat udělal výpočetní chybu.
Neexistují žádné další známé Fermatovy prvočísla Fn s n > 4, ale o Fermatových číslech pro velké je známo jen málo n.[2] Ve skutečnosti je každý z následujících otevřených problémů:
- Je Fn kompozitní pro všechny n > 4?
- Existuje nekonečně mnoho Fermatových prvočísel? (Eisenstein 1844)[3]
- Existuje nekonečně mnoho složených čísel Fermata?
- Existuje číslo Fermat, které není bez čtverce ?
Od roku 2014[Aktualizace], je známo že Fn je složený pro 5 ≤ n ≤ 32, ačkoli z nich, úplné faktorizace Fn jsou známé pouze pro 0 ≤ n ≤ 11a nejsou známy žádné hlavní faktory pro n = 20 a n = 24.[4] Největší Fermatovo číslo, o kterém je známo, že je složené, je F18233954a jeho hlavní faktor 7 × 218233956 + 1, a megaprime, byl objeven v říjnu 2020.
Heuristické argumenty pro hustotu
Existuje několik pravděpodobnostních argumentů pro konečnost Fermatových prvočísel.
Podle věta o prvočísle „pravděpodobnost „to číslo n je prime je asi 1 / ln (n). Proto celkem očekávané číslo Fermatových prvočísel je nanejvýš
Tento argument není přísným důkazem. Argument za prvé předpokládá, že se Fermatova čísla chovají „náhodně“, přesto jsme již viděli, že faktory Fermatových čísel mají speciální vlastnosti.
Pokud (složitěji) považujeme podmiňovací způsob pravděpodobnost, že n je prime, vzhledem k tomu, že víme, že všechny jeho hlavní faktory překračují B, jako nanejvýš A ln (B) / ln (n), poté pomocí Eulerovy věty, jejíž nejméně prvočinitelem je Fn překračuje 2n+1místo toho bychom našli
Rovnocenné podmínky prvenství
Nechat být nčíslo Fermata. Pépinův test uvádí, že pro n > 0,
- je hlavní právě tehdy
Výraz lze hodnotit modulo podle opakované kvadratury. Díky tomu je test rychlý polynomiální čas algoritmus. Ale počet Fermatů roste tak rychle, že jen hrstka z nich může být testována v rozumném množství času a prostoru.
Existuje několik testů na čísla formuláře k 2m + 1, jako jsou faktory Fermatových čísel, k primalitě.
- Prothova věta (1878). Nechat = + s lichým < . Pokud existuje celé číslo takhle
- pak je hlavní. Naopak, pokud výše uvedená shoda neplatí, a navíc
- (Vidět Jacobi symbol )
- pak je složený.
Li N = Fn > 3, pak se výše uvedený Jacobiho symbol vždy rovná -1 pro A = 3, a tento speciální případ Prothovy věty je známý jako Pépinův test. Přestože Pépinův test a Prothova věta byly implementovány do počítačů k prokázání komplexnosti některých Fermatových čísel, žádný test neposkytuje konkrétní netriviální faktor. Ve skutečnosti nejsou známy žádné konkrétní hlavní faktory n = 20 a 24.
Faktorizace Fermatových čísel
Vzhledem k velikosti Fermatových čísel je těžké faktorizovat nebo dokonce zkontrolovat primitivitu. Pépinův test dává nezbytnou a dostatečnou podmínku pro primalitu Fermatových čísel a lze jej implementovat moderními počítači. The metoda eliptické křivky je rychlá metoda pro hledání malých prvočíselných dělitelů čísel. Projekt distribuovaných výpočtů Fermatsearch našel některé faktory Fermatových čísel. Proth.exe od Yves Gallot byl použit k vyhledání faktorů velkého počtu Fermatů. Édouard Lucas, zlepšující Eulerův výše zmíněný výsledek, dokázal v roce 1878, že každý faktor Fermatova čísla , s n alespoň 2, je ve formě (vidět Proth číslo ), kde k je kladné celé číslo. To samo o sobě usnadňuje prokázání primality známých Fermatových prvočísel.
Faktorizace prvních dvanácti Fermatových čísel jsou:
F0 = 21 + 1 = 3 je hlavní F1 = 22 + 1 = 5 je hlavní F2 = 24 + 1 = 17 je hlavní F3 = 28 + 1 = 257 je hlavní F4 = 216 + 1 = 65,537 je největší známý Fermat prime F5 = 232 + 1 = 4,294,967,297 = 641 × 6 700 417 (plně zohledněno 1732 [5]) F6 = 264 + 1 = 18 446 744 073 709 551 617 (20 číslic) = 274 177 × 67 280 421 310 1021 (14 číslic) (plně zohledněno 1855) F7 = 2128 + 1 = 340 282 366 920 938 463 463 374 607 431 768 211 457 (39 číslic) = 59 649 589 127 497 217 (17 číslic) × 5 704 689 200 685 129 1295421 (22 číslic) (plně zohledněno v roce 1970) F8 = 2256 + 1 = 115,792,089,237,316,195,423,570,985,008,687,907,853,269,984,665,640,564,039,457,584,007,913,129,
639937 (78 číslic)= 1 238 926 361 552 897 (16 číslic) ×
93 461 639 715 357 977 769 163 558 199 606 896 584 051 237 541 638 188 580 280 321 (62 číslic) (plně zohledněno v roce 1980)F9 = 2512 + 1 = 13,407,807,929,942,597,099,574,024,998,205,846,127,479,365,820,592,393,377,723,561,443,721,764,0
30,073,546,976,801,874,298,166,903,427,690,031,858,186,486,050,853,753,882,811,946,569,946,433,6
49 006 084 097 (155 číslic)= 2424 833 × 7 455 602 825 647 884 208 337 395 736 200 454 918 783 366 342 657 (49 číslic) ×
741,640,062,627,530,801,524,787,141,901,937,474,059,940,781,097,519,023,905,821,316,144,415,759,
504 705 008 092 818 711 693 940 737 (99 číslic) (plně zohledněno v roce 1990)F10 = 21024 + 1 = 179 769 313 486 231 590 772 930 ... 30 4835 356 329 624 224 137 217 (309 číslic) = 45 592 577 × 6 487 031 809 × 4 659 775 785 220 018 543 264 560 743 076 778 192 897 (40 číslic) ×
130,439,874,405,488,189,727,484 ... 806,217,820,753,127,014,424,577 (252 číslic) (plně zohledněno 1995)F11 = 22048 + 1 = 32 317 006 071 311 007 300 714,8 ... 193 555 853 611 059 596 230 657 (617 číslic) = 319 489 × 974 849 × 167 988 556 341 760 475 137 (21 číslic) × 3 560 841 906 445 833 920 513 (22 číslic) ×
173 462 447 179 147 555 430 258 ... 491 382 441 723 306 598 834 177 (564 číslic) (plně zohledněno v roce 1988)
Od roku 2018[Aktualizace], pouze F0 na F11 byly úplně započteno.[4] The distribuované výpočty projekt Fermat Search hledá nové faktory Fermatových čísel.[6] Soubor všech Fermatových faktorů je A050922 (nebo tříděno, A023394 ) v OEIS.
Je možné, že jediné prvočísla této formy jsou 3, 5, 17, 257 a 65 537. Opravdu, Boklan a John H. Conway zveřejnil v roce 2016 velmi přesnou analýzu naznačující, že pravděpodobnost existence dalšího Fermatova prvočísla je menší než jedna ku miliardě.[7]
Následující faktory Fermatových čísel byly známy před rokem 1950 (od 50. let digitální počítače pomohly najít další faktory):
Rok | Nálezce | Číslo Fermata | Faktor |
---|---|---|---|
1732 | Euler | ||
1732 | Euler | (plně zohledněno) | |
1855 | Clausen | ||
1855 | Clausen | (plně zohledněno) | |
1877 | Pervushin | ||
1878 | Pervushin | ||
1886 | Seelhoff | ||
1899 | Cunningham | ||
1899 | Cunningham | ||
1903 | Západní | ||
1903 | Západní | ||
1903 | Západní | ||
1903 | Západní | ||
1903 | Cullen | ||
1906 | Morehead | ||
1925 | Kraitchik |
Od ledna 2020[Aktualizace]Je známo 351 prvočísel Fermatových čísel a 307 Fermatových čísel je složených.[4] Každý rok se objevuje několik nových Fermatových faktorů.[8]
Čísla Pseudoprimes a Fermat
Jako složená čísla formuláře 2str - 1, každé složené číslo Fermat je a silný pseudoprime do základny 2. Je to proto, že všechny silné pseudopriminy do základny 2 také jsou Fermat pseudoprimes - tj.
pro všechna čísla Fermat.
V roce 1904 Cipolla ukázal, že produkt alespoň dvou odlišných primárních nebo složených Fermatových čísel bude Fermat pseudoprime na základnu 2, pokud a jen pokud .[9]
Další věty o Fermatových číslech
Lemma. — Li n je kladné celé číslo,
Teorém — Li je tedy liché prvočíslo je síla 2.
Li je kladné celé číslo, ale není mocninou 2, musí mít lichý primární faktor a můžeme psát kde .
Podle předchozího lemmatu pro kladné celé číslo ,
kde znamená „rovnoměrně rozdělit“. Střídání , a a používat to je zvláštní,
a tudíž
Protože , z toho vyplývá, že není prime. Proto by kontrapozice musí být síla 2.
Teorém — Fermat prime nemůže být Wieferich prime.
Ukážeme, jestli je Fermat prime (a tudíž výše, m je mocnina 2), pak shoda nedrží.
Od té doby můžeme psát . Pokud daná kongruence platí, pak , a proto
Proto , a proto . Tohle vede k , což je od té doby nemožné .
Teorém (Édouard Lucas ) — Jakýkoli hlavní dělitel str z je ve formě kdykoli n > 1.
Nechat Gstr označit skupina nenulových celých čísel modulo str pod násobením, který má pořádek str-1. Všimněte si, že 2 (přísně vzato, jeho obraz modulo str) má multiplikativní pořadí rovné v Gstr (od té doby je čtverec což je -1 modulo Fn), takže tím, že Lagrangeova věta, str - 1 je dělitelné a str má formu pro celé číslo k, tak jako Euler věděl. Édouard Lucas šel dále. Od té doby n > 1, hlavní str výše je shodné s 1 modulo 8. Proto (jak bylo známo Carl Friedrich Gauss ), 2 je a kvadratický zbytek modulo str, to znamená, že existuje celé číslo A takhle Pak obrázek A má pořádek ve skupině Gstr a (opět pomocí Lagrangeovy věty), str - 1 je dělitelné a str má formu pro celé číslo s.
Ve skutečnosti lze přímo vidět, že 2 je kvadratický zbytek modulo str, od té doby
Protože lichá síla 2 je kvadratický zbytek modulo str, tak je 2 sám.
Vztah ke konstruovatelným polygonům

Carl Friedrich Gauss vyvinul teorii Gaussovské období v jeho Disquisitiones Arithmeticae a formuloval a dostatečný stav pro konstruovatelnost pravidelných mnohoúhelníků. Gauss uvedl, že tato podmínka byla také nutné, ale nikdy nezveřejnil důkaz. Pierre Wantzel poskytl úplný důkaz nutnosti v roce 1837. Výsledek je znám jako Gauss – Wantzelova věta:
- An n-stranný pravidelný mnohoúhelník lze sestrojit pomocí kompas a pravítko kdyby a jen kdyby n je produktem síly 2 a různých Fermatových prvočísel: jinými slovy, pokud a jen pokud n je ve formě n = 2kstr1str2…strs, kde k je nezáporné celé číslo a stri jsou odlišné Fermatovy prvočísla.
Kladné celé číslo n je výše uvedené formy právě tehdy, když je totient φ (n) je síla 2.
Aplikace čísel Fermat
Generování pseudonáhodných čísel
Fermatova prvočísla jsou zvláště užitečná při generování pseudonáhodných sekvencí čísel v rozsahu 1… N, kde N je mocnina 2. Nejběžnější používanou metodou je převzetí jakékoli počáteční hodnoty mezi 1 a P - 1, kde P je Fermat prime. Nyní to vynásobte číslem A, který je větší než odmocnina z P a je primitivní kořen modulo P (tj. není to kvadratický zbytek ). Pak vezměte výsledek modulo P. Výsledkem je nová hodnota pro RNG.
- (vidět lineární shodný generátor, RANDU )
To je užitečné v informatice, protože většina datových struktur má členy s 2X možné hodnoty. Například bajt má 256 (28) možné hodnoty (0–255). Proto k vyplnění bajtu nebo bajtů náhodnými hodnotami lze použít generátor náhodných čísel, který vytváří hodnoty 1–256, přičemž bajt má výstupní hodnotu −1. Z tohoto důvodu jsou obzvláště zajímavé Fermatovy prvočísla v šifrování dat. Tato metoda vytváří pouze pseudonáhodné hodnoty jako po P - 1 opakování, sekvence se opakuje. Špatně zvolený multiplikátor může mít za následek opakování sekvence dříve než P − 1.
Další zajímavá fakta
Fermatovo číslo nemůže být dokonalým číslem nebo součástí dvojice přátelská čísla. (Luca 2000 )
Série převrácených čísel všech hlavních dělitelů Fermatových čísel je konvergentní. (Křížek, Luca & Somer 2002 )
Li nn +1 je prvočíslo, existuje celé číslo m takhle n = 22m. Rovnicenn + 1 = F(2m+m)v takovém případě platí.[10][11]
Nechť největší primární faktor Fermatova čísla Fn být P(Fn). Pak,
Zobecněná čísla Fermat
Čísla formuláře s A, b žádný coprime celá čísla, A > b > 0, jsou volány zobecněná čísla Fermat. Zvláštní prime str je zobecněné číslo Fermat, právě když str je shodný s 1 (mod 4). (Zde uvažujeme pouze případ n > 0, takže 3 = není protikladem.)
Příklad a pravděpodobný prime tohoto formuláře je 12465536 + 5765536 (našel Valeryi Kuryshev).[12]
Analogicky s běžnými Fermatovými čísly je běžné psát zobecněná Fermatova čísla formuláře tak jako Fn(A). V této notaci by například bylo číslo 100 000 001 zapsáno jako F3(10). V následujícím se omezíme na prvočísla této formy, se taková prvočísla nazývají „Fermatova základna A". Tato prvočísla samozřejmě existují, pouze pokud A je dokonce.
Pokud požadujeme n > 0, tedy Landauův čtvrtý problém ptá se, jestli existuje nekonečně mnoho zobecněných Fermatových prvočísel Fn(A).
Zobecněné Fermatovy prvočísla
Kvůli jednoduchosti prokázání jejich primality se zobecněné Fermatovy prvočísla staly v posledních letech tématem výzkumu v oblasti teorie čísel. Mnoho z největších známých prvočísel dnes jsou zobecněné Fermatovy prvočísla.
Zobecněná čísla Fermat mohou být prvočísla pouze pro sudé A, protože jestli A je liché, pak bude každé zobecněné Fermatovo číslo dělitelné 2. Nejmenší prvočíslo s je nebo 3032 + 1. Kromě toho můžeme definovat „napůl zobecněná čísla Fermat“ pro lichou základnu, poloviční zobecněné číslo Fermat na základnu A (pro liché A) je a lze také očekávat, že pro každou lichou základnu bude pouze konečně mnoho polovičně zobecněných Fermatových prvočísel.
(V seznamu jsou zobecněná čísla Fermat () na sudý A jsou , pro zvláštní A, oni jsou . Li A je dokonalá síla s lichým exponentem (sekvence A070265 v OEIS ), pak lze všechna zobecněná Fermatova čísla algebraicky započítat, takže nemohou být prvočísla)
(Pro nejmenší číslo takhle je hlavní, viz OEIS: A253242)
čísla takhle je hlavní | čísla takhle je hlavní | čísla takhle je hlavní | čísla takhle je hlavní | ||||
---|---|---|---|---|---|---|---|
2 | 0, 1, 2, 3, 4, ... | 18 | 0, ... | 34 | 2, ... | 50 | ... |
3 | 0, 1, 2, 4, 5, 6, ... | 19 | 1, ... | 35 | 1, 2, 6, ... | 51 | 1, 3, 6, ... |
4 | 0, 1, 2, 3, ... | 20 | 1, 2, ... | 36 | 0, 1, ... | 52 | 0, ... |
5 | 0, 1, 2, ... | 21 | 0, 2, 5, ... | 37 | 0, ... | 53 | 3, ... |
6 | 0, 1, 2, ... | 22 | 0, ... | 38 | ... | 54 | 1, 2, 5, ... |
7 | 2, ... | 23 | 2, ... | 39 | 1, 2, ... | 55 | ... |
8 | (žádný) | 24 | 1, 2, ... | 40 | 0, 1, ... | 56 | 1, 2, ... |
9 | 0, 1, 3, 4, 5, ... | 25 | 0, 1, ... | 41 | 4, ... | 57 | 0, 2, ... |
10 | 0, 1, ... | 26 | 1, ... | 42 | 0, ... | 58 | 0, ... |
11 | 1, 2, ... | 27 | (žádný) | 43 | 3, ... | 59 | 1, ... |
12 | 0, ... | 28 | 0, 2, ... | 44 | 4, ... | 60 | 0, ... |
13 | 0, 2, 3, ... | 29 | 1, 2, 4, ... | 45 | 0, 1, ... | 61 | 0, 1, 2, ... |
14 | 1, ... | 30 | 0, 5, ... | 46 | 0, 2, 9, ... | 62 | ... |
15 | 1, ... | 31 | ... | 47 | 3, ... | 63 | ... |
16 | 0, 1, 2, ... | 32 | (žádný) | 48 | 2, ... | 64 | (žádný) |
17 | 2, ... | 33 | 0, 3, ... | 49 | 1, ... | 65 | 1, 2, 5, ... |
b | známá zobecněná (poloviční) Fermatova primární báze b |
2 | 3, 5, 17, 257, 65537 |
3 | 2, 5, 41, 21523361, 926510094425921, 1716841910146256242328924544641 |
4 | 5, 17, 257, 65537 |
5 | 3, 13, 313 |
6 | 7, 37, 1297 |
7 | 1201 |
8 | (nemožné) |
9 | 5, 41, 21523361, 926510094425921, 1716841910146256242328924544641 |
10 | 11, 101 |
11 | 61, 7321 |
12 | 13 |
13 | 7, 14281, 407865361 |
14 | 197 |
15 | 113 |
16 | 17, 257, 65537 |
17 | 41761 |
18 | 19 |
19 | 181 |
20 | 401, 160001 |
21 | 11, 97241, 1023263388750334684164671319051311082339521 |
22 | 23 |
23 | 139921 |
24 | 577, 331777 |
25 | 13, 313 |
26 | 677 |
27 | (nemožné) |
28 | 29, 614657 |
29 | 421, 353641, 125123236840173674393761 |
30 | 31, 185302018885184100000000000000000000000000000001 |
31 | |
32 | (nemožné) |
33 | 17, 703204309121 |
34 | 1336337 |
35 | 613, 750313, 330616742651687834074918381127337110499579842147487712949050636668246738736343104392290115356445313 |
36 | 37, 1297 |
37 | 19 |
38 | |
39 | 761, 1156721 |
40 | 41, 1601 |
41 | 31879515457326527173216321 |
42 | 43 |
43 | 5844100138801 |
44 | 197352587024076973231046657 |
45 | 23, 1013 |
46 | 47, 4477457, 46512+1 (852 číslic: 214787904487 ... 289480994817) |
47 | 11905643330881 |
48 | 5308417 |
49 | 1201 |
50 |
(Vidět [13][14] Další informace (i základny do 1000) viz také [15] pro liché podklady)
(Pro nejmenší prime formy (pro liché ), viz také OEIS: A111635)
čísla takhle je hlavní | ||
---|---|---|
2 | 1 | 0, 1, 2, 3, 4, ... |
3 | 1 | 0, 1, 2, 4, 5, 6, ... |
3 | 2 | 0, 1, 2, ... |
4 | 1 | 0, 1, 2, 3, ... |
4 | 3 | 0, 2, 4, ... |
5 | 1 | 0, 1, 2, ... |
5 | 2 | 0, 1, 2, ... |
5 | 3 | 1, 2, 3, ... |
5 | 4 | 1, 2, ... |
6 | 1 | 0, 1, 2, ... |
6 | 5 | 0, 1, 3, 4, ... |
7 | 1 | 2, ... |
7 | 2 | 1, 2, ... |
7 | 3 | 0, 1, 8, ... |
7 | 4 | 0, 2, ... |
7 | 5 | 1, 4, ... |
7 | 6 | 0, 2, 4, ... |
8 | 1 | (žádný) |
8 | 3 | 0, 1, 2, ... |
8 | 5 | 0, 1, 2, ... |
8 | 7 | 1, 4, ... |
9 | 1 | 0, 1, 3, 4, 5, ... |
9 | 2 | 0, 2, ... |
9 | 4 | 0, 1, ... |
9 | 5 | 0, 1, 2, ... |
9 | 7 | 2, ... |
9 | 8 | 0, 2, 5, ... |
10 | 1 | 0, 1, ... |
10 | 3 | 0, 1, 3, ... |
10 | 7 | 0, 1, 2, ... |
10 | 9 | 0, 1, 2, ... |
11 | 1 | 1, 2, ... |
11 | 2 | 0, 2, ... |
11 | 3 | 0, 3, ... |
11 | 4 | 1, 2, ... |
11 | 5 | 1, ... |
11 | 6 | 0, 1, 2, ... |
11 | 7 | 2, 4, 5, ... |
11 | 8 | 0, 6, ... |
11 | 9 | 1, 2, ... |
11 | 10 | 5, ... |
12 | 1 | 0, ... |
12 | 5 | 0, 4, ... |
12 | 7 | 0, 1, 3, ... |
12 | 11 | 0, ... |
13 | 1 | 0, 2, 3, ... |
13 | 2 | 1, 3, 9, ... |
13 | 3 | 1, 2, ... |
13 | 4 | 0, 2, ... |
13 | 5 | 1, 2, 4, ... |
13 | 6 | 0, 6, ... |
13 | 7 | 1, ... |
13 | 8 | 1, 3, 4, ... |
13 | 9 | 0, 3, ... |
13 | 10 | 0, 1, 2, 4, ... |
13 | 11 | 2, ... |
13 | 12 | 1, 2, 5, ... |
14 | 1 | 1, ... |
14 | 3 | 0, 3, ... |
14 | 5 | 0, 2, 4, 8, ... |
14 | 9 | 0, 1, 8, ... |
14 | 11 | 1, ... |
14 | 13 | 2, ... |
15 | 1 | 1, ... |
15 | 2 | 0, 1, ... |
15 | 4 | 0, 1, ... |
15 | 7 | 0, 1, 2, ... |
15 | 8 | 0, 2, 3, ... |
15 | 11 | 0, 1, 2, ... |
15 | 13 | 1, 4, ... |
15 | 14 | 0, 1, 2, 4, ... |
16 | 1 | 0, 1, 2, ... |
16 | 3 | 0, 2, 8, ... |
16 | 5 | 1, 2, ... |
16 | 7 | 0, 6, ... |
16 | 9 | 1, 3, ... |
16 | 11 | 2, 4, ... |
16 | 13 | 0, 3, ... |
16 | 15 | 0, ... |
(Pro nejmenší sudou základnu A takhle je hlavní, viz OEIS: A056993)
základny A takhle je hlavní (zvažte pouze sudé A) | OEIS sekvence | |
---|---|---|
0 | 2, 4, 6, 10, 12, 16, 18, 22, 28, 30, 36, 40, 42, 46, 52, 58, 60, 66, 70, 72, 78, 82, 88, 96, 100, 102, 106, 108, 112, 126, 130, 136, 138, 148, 150, ... | A006093 |
1 | 2, 4, 6, 10, 14, 16, 20, 24, 26, 36, 40, 54, 56, 66, 74, 84, 90, 94, 110, 116, 120, 124, 126, 130, 134, 146, 150, 156, 160, 170, 176, 180, 184, ... | A005574 |
2 | 2, 4, 6, 16, 20, 24, 28, 34, 46, 48, 54, 56, 74, 80, 82, 88, 90, 106, 118, 132, 140, 142, 154, 160, 164, 174, 180, 194, 198, 204, 210, 220, 228, ... | A000068 |
3 | 2, 4, 118, 132, 140, 152, 208, 240, 242, 288, 290, 306, 378, 392, 426, 434, 442, 508, 510, 540, 542, 562, 596, 610, 664, 680, 682, 732, 782, ... | A006314 |
4 | 2, 44, 74, 76, 94, 156, 158, 176, 188, 198, 248, 288, 306, 318, 330, 348, 370, 382, 396, 452, 456, 470, 474, 476, 478, 560, 568, 598, 642, ... | A006313 |
5 | 30, 54, 96, 112, 114, 132, 156, 332, 342, 360, 376, 428, 430, 432, 448, 562, 588, 726, 738, 804, 850, 884, 1068, 1142, 1198, 1306, 1540, 1568, ... | A006315 |
6 | 102, 162, 274, 300, 412, 562, 592, 728, 1084, 1094, 1108, 1120, 1200, 1558, 1566, 1630, 1804, 1876, 2094, 2162, 2164, 2238, 2336, 2388, ... | A006316 |
7 | 120, 190, 234, 506, 532, 548, 960, 1738, 1786, 2884, 3000, 3420, 3476, 3658, 4258, 5788, 6080, 6562, 6750, 7692, 8296, 9108, 9356, 9582, ... | A056994 |
8 | 278, 614, 892, 898, 1348, 1494, 1574, 1938, 2116, 2122, 2278, 2762, 3434, 4094, 4204, 4728, 5712, 5744, 6066, 6508, 6930, 7022, 7332, ... | A056995 |
9 | 46, 1036, 1318, 1342, 2472, 2926, 3154, 3878, 4386, 4464, 4474, 4482, 4616, 4688, 5374, 5698, 5716, 5770, 6268, 6386, 6682, 7388, 7992, ... | A057465 |
10 | 824, 1476, 1632, 2462, 2484, 2520, 3064, 3402, 3820, 4026, 6640, 7026, 7158, 9070, 12202, 12548, 12994, 13042, 15358, 17646, 17670, ... | A057002 |
11 | 150, 2558, 4650, 4772, 11272, 13236, 15048, 23302, 26946, 29504, 31614, 33308, 35054, 36702, 37062, 39020, 39056, 43738, 44174, 45654, ... | A088361 |
12 | 1534, 7316, 17582, 18224, 28234, 34954, 41336, 48824, 51558, 51914, 57394, 61686, 62060, 89762, 96632, 98242, 100540, 101578, 109696, ... | A088362 |
13 | 30406, 71852, 85654, 111850, 126308, 134492, 144642, 147942, 150152, 165894, 176206, 180924, 201170, 212724, 222764, 225174, 241600, ... | A226528 |
14 | 67234, 101830, 114024, 133858, 162192, 165306, 210714, 216968, 229310, 232798, 422666, 426690, 449732, 462470, 468144, 498904, 506664, ... | A226529 |
15 | 70906, 167176, 204462, 249830, 321164, 330716, 332554, 429370, 499310, 524552, 553602, 743788, 825324, 831648, 855124, 999236, 1041870, ... | A226530 |
16 | 48594, 108368, 141146, 189590, 255694, 291726, 292550, 357868, 440846, 544118, 549868, 671600, 843832, 857678, 1024390, 1057476, 1087540, ... | A251597 |
17 | 62722, 130816, 228188, 386892, 572186, 689186, 909548, 1063730, 1176694, 1361244, 1372930, 1560730, 1660830, 1717162, 1722230, 1766192, ... | A253854 |
18 | 24518, 40734, 145310, 361658, 525094, 676754, 773620, 1415198, 1488256, 1615588, 1828858, 2042774, 2514168, 2611294, 2676404, 3060772, ... | A244150 |
19 | 75898, 341112, 356926, 475856, 1880370, 2061748, 2312092, ... | A243959 |
20 | 919444, 1059094, ... | A321323 |
Nejmenší základna b takhle b2n + 1 je prime are
- 2, 2, 2, 2, 2, 30, 102, 120, 278, 46, 824, 150, 1534, 30406, 67234, 70906, 48594, 62722, 24518, 75898, 919444, ... (sekvence A056993 v OEIS )
Nejmenší k takové, že (2n)k + 1 je prime are
- 1, 1, 1, 0, 1, 1, 2, 1, 1, 2, 1, 2, 2, 1, 1, 0, 4, 1, ... (Další termín není znám) (sekvence A079706 v OEIS ) (viz také OEIS: A228101 a OEIS: A084712)
K predikci počtu bází, pro které lze použít propracovanější teorii bude hlavní pro pevné . Lze zhruba předpokládat, že počet zobecněných Fermatových prvočísel klesne na polovinu se zvyšuje o 1.
Největší známé generalizované Fermatovy prvočísla
Následuje seznam 5 největších známých zobecněných Fermatových prvočísel.[16] Všichni jsou megaprimes. Celá top-5 je objevena účastníky v PrimeGrid projekt.
Hodnost | Prime rank[17] | prvočíslo | Zobecněná Fermatova notace | Počet číslic | Nalezené datum | ref. |
---|---|---|---|---|---|---|
1 | 14 | 10590941048576 + 1 | F20(1059094) | 6,317,602 | Listopadu 2018 | [18] |
2 | 15 | 9194441048576 + 1 | F20(919444) | 6,253,210 | Září 2017 | [19] |
3 | 31 | 3214654524288 + 1 | F19(3214654) | 3,411,613 | Prosince 2019 | [20] |
4 | 32 | 2985036524288 + 1 | F19(2985036) | 3,394,739 | Září 2019 | [21] |
5 | 33 | 2877652524288 + 1 | F19(2877652) | 3,386,397 | Června 2019 | [22] |
Na Prime Stránky jeden může najít aktuální top 100 zobecněných Fermatových prvočísel.
Viz také
- Konstruktivní polygon: které pravidelné polygony jsou částečně konstruovatelné, závisí na Fermatových prvočíslech.
- Dvojitá exponenciální funkce
- Lucasova věta
- Mersenne prime
- Pierpont prime
- Test primality
- Prothova věta
- Pseudoprime
- Sierpińského číslo
- Sylvestrova sekvence
Poznámky
- ^ Křížek, Luca & Somer 2001, str. 38, poznámka 4.15
- ^ Chris Caldwell, „Prime Links ++: speciální formuláře“ Archivováno 2013-12-24 na Wayback Machine na Prime Stránky.
- ^ Ribenboim 1996, str. 88.
- ^ A b C Keller, Wilfrid (7. února 2012), „Prime Factors of Fermat Numbers“, ProthSearch.com, vyvoláno 25. ledna 2020
- ^ Sandifer, ed. „Jak to Euler udělal“ (PDF). MAA online. Mathematical Association of America. Citováno 2020-06-13.
- ^ ":: F E R M A T S E A R C H. O R G :: Domovská stránka". www.fermatsearch.org. Citováno 7. dubna 2018.
- ^ Boklan, Kent D .; Conway, John H. (2016). „Očekávejte maximálně miliardtinu nového Fermat Prime!“. arXiv:1605.01371 [math.NT ].
- ^ ":: F E R M A T S E A R C H. O R G :: Novinky". www.fermatsearch.org. Citováno 7. dubna 2018.
- ^ Křížek, Michal; Luca, Florian; Somer, Lawrence (14. března 2013). 17 přednášek o číslech Fermat: od teorie čísel po geometrii. Springer Science & Business Media. ISBN 9780387218502. Citováno 7. dubna 2018 - prostřednictvím Knih Google.
- ^ Jeppe Stig Nielsen, „S (n) = n ^ n + 1“.
- ^ Weisstein, Eric W. "Sierpiński číslo prvního druhu". MathWorld.
- ^ Nejlepší záznamy PRP, hledejte x ^ (2 ^ 16) + y ^ (2 ^ 16), Henri & Renaud Lifchitz.
- ^ „Zobecněné Fermatovy prvočísla“. jeppesn.dk. Citováno 7. dubna 2018.
- ^ „Zobecněné Fermatovy prvočísla pro základny do 1030“. noprimeleftbehind.net. Citováno 7. dubna 2018.
- ^ „Zobecněné Fermatovy prvočísla v lichých základnách“. fermatquotient.com. Citováno 7. dubna 2018.
- ^ Caldwell, Chris K. „Top Twenty: Generalized Fermat“. Prvotní stránky. Citováno 11. července 2019.
- ^ Caldwell, Chris K. "Výstup hledání databáze". Prvotní stránky. Citováno 11. července 2019.
- ^ 10590941048576 + 1
- ^ 9194441048576 + 1
- ^ 3214654524288 + 1
- ^ 2985036524288 + 1
- ^ 2877652524288 + 1
Reference
- Golomb, S. W. (1. ledna 1963), „O součtu převrácených čísel Fermata a souvisejících iracionalit“, Kanadský žurnál matematiky, 15: 475–478, doi:10.4153 / CJM-1963-051-0
- Grytczuk, A .; Luca, F. & Wójtowicz, M. (2001), „Další poznámka o největších hlavních faktorech Fermatových čísel“, Jihovýchodní Asie Bulletin matematiky, 25 (1): 111–115, doi:10.1007 / s10012-001-0111-4, S2CID 122332537
- Guy, Richard K. (2004), Nevyřešené problémy v teorii čísel, Problémové knihy z matematiky, 1 (3. vyd.), New York: Springer Verlag, str. A3, A12, B21, ISBN 978-0-387-20860-2
- Křížek, Michal; Luca, Florian & Somer, Lawrence (2001), 17 přednášek o číslech Fermat: od teorie čísel po geometrii, CMS knihy z matematiky, 10, New York: Springer, ISBN 978-0-387-95332-8 - Tato kniha obsahuje rozsáhlý seznam odkazů.
- Křížek, Michal; Luca, Florian & Somer, Lawrence (2002), „O konvergenci řady převrácených čísel prvočísel souvisejících s Fermatovými čísly“ (PDF), Žurnál teorie čísel, 97 (1): 95–112, doi:10.1006 / jnth.2002.2782
- Luca, Florian (2000), „Asociální číslo Fermata“, Americký matematický měsíčník, 107 (2): 171–173, doi:10.2307/2589441, JSTOR 2589441
- Ribenboim, Paulo (1996), Nová kniha rekordů prvočísel (3. vyd.), New York: Springer, ISBN 978-0-387-94457-9
- Robinson, Raphael M. (1954), „Mersenne and Fermat Numbers“, Proceedings of the American Mathematical Society, 5 (5): 842–846, doi:10.2307/2031878, JSTOR 2031878
- Yabuta, M. (2001), „Jednoduchý důkaz Carmichaelovy věty o primitivních dělitelích“ (PDF), Fibonacci čtvrtletně, 39: 439–443
externí odkazy
- Fermat prime na Encyklopedie Britannica
- Chris Caldwell, Hlavní glosář: Fermatovo číslo na Prime Stránky.
- Luigi Morelli, Historie Fermat čísel
- John Cosgrave, Sjednocení čísel Mersenne a Fermat
- Wilfrid Keller, Hlavní faktory počtu fermatů
- Weisstein, Eric W. „Fermat Number“. MathWorld.
- Weisstein, Eric W. „Fermat Prime“. MathWorld.
- Weisstein, Eric W. „Fermat Pseudoprime“. MathWorld.
- Weisstein, Eric W. "Zobecněné číslo Fermat". MathWorld.
- Yves Gallot, Zobecněné Fermat Prime Search
- Mark S.Manasse, Dokončete faktorizaci devátého Fermatova čísla (původní oznámení)
- Peyton Hayslette, Největší známé zobecněné oznámení Fermat Prime