Fibonacci prime - Fibonacci prime - Wikipedia

A Fibonacci prime je Fibonacciho číslo to je primární, typ celočíselná posloupnost prime.

První Fibonacciho prvočísla jsou (sekvence A005478 v OEIS ):

2, 3, 5, 13, 89, 233, 1597, 28657, 514229, 433494437, 2971215073, ....

Známé Fibonacciho prvočísla

Nevyřešený problém v matematice: Existuje nekonečné množství Fibonacciho prvočísel? (více nevyřešených úloh z matematiky)

Není známo, zda existují nekonečně mnoho Fibonacciho prvočísel. S indexováním začínajícím na F₁ = F₂ = 1, prvních 34 je F_n pro n hodnoty (sekvence A001605 v OEIS ):

n = 3, 4, 5, 7, 11, 13, 17, 23, 29, 43, 47, 83, 131, 137, 359, 431, 433, 449, 509, 569, 571, 2971, 4723, 5387, 9311, 9677, 14431, 25561, 30757, 35999, 37511, 50833, 81839, 104911.

Kromě těchto osvědčených Fibonacciho prvočísel se našly také pravděpodobné prvočísla pro

n = 130021, 148091, 201107, 397379, 433781, 590041, 593689, 604711, 931517, 1049897, 1285607, 1636007, 1803059, 1968721, 2904353, 3244369, 3340367.^[2]

Až na případ n = 4, všechna Fibonacciho prvočísla mají index prvočísel, protože pokud A rozděluje b, pak ${ displaystyle F_ {a}}$ také rozděluje ${ displaystyle F_ {b}}$, ale ne každé prvočíslo je indexem Fibonacciho prvočísla.

F_p je prvočíslo pro 8 z prvních 10 prvočísel p; výjimky jsou F₂ = 1 a F₁₉ = 4181 = 37 × 113. Zdá se však, že Fibonacciho prvočísla se s růstem indexu stávají vzácnějšími. F_p je hlavní pouze pro 26 z 1229 prvočísel p pod 10 000.^[3] Počet prvočíselných faktorů v číslech Fibonacci s indexem prvočísel je:

0, 1, 1, 1, 1, 1, 1, 2, 1, 1, 2, 3, 2, 1, 1, 2, 2, 2, 3, 2, 2, 2, 1, 2, 4, 2, 3, 2, 2, 2, 2, 1, 1, 3, 4, 2, 4, 4, 2, 2, 3, 3, 2, 2, 4, 2, 4, 4, 2, 5, 3, 4, 3, 2, 3, 3, 4, 2, 2, 3, 4, 2, 4, 4, 4, 3, 2, 3, 5, 4, 2, 1, ... (sekvence A080345 v OEIS )

Od března 2017^{[Aktualizace]}, největší známý jistý Fibonacci prime F₁₀₄₉₁₁, s 21925 číslicemi. Ukázalo se, že v roce 2015 to byli Mathew Steine ​​a Bouk de Water.^[4] Největší známý pravděpodobný Fibonacciho prime je F_3340367. Nalezl ji Henri Lifchitz v roce 2018.^[2]Nick MacKinnon dokázal, že jediná čísla Fibonacci, která jsou také členy množiny dvojčata připraví jsou 3, 5 a 13.^[5]

Dělitelnost Fibonacciho čísel

Prime ${ displaystyle p}$ rozděluje ${ displaystyle F_ {p-1}}$ kdyby a jen kdyby p je shodný na ± 1 modulo 5 a p rozděluje ${ displaystyle F_ {p + 1}}$ právě když je shodný s ± 2 modulo 5. (Pro p = 5, F₅ = 5, takže 5 dělí F₅)

Fibonacciho čísla, která mají primární index p nesdílejte žádné společné dělitele větší než 1 s předchozími čísly Fibonacci, kvůli identitě:^[6]

${ displaystyle gcd (F_ {n}, F_ {m}) = F _ { gcd (n, m)},}$

což znamená nekonečnost prvočísel od té doby ${ displaystyle F_ {p}}$ je dělitelný alespoň jedním prvočíslem pro všechny ${ displaystyle p> 2}$.

Pro n ≥ 3, F_n rozděluje F_m iff n rozděluje m.^[7]

Pokud to předpokládáme m je prvočíslo p, a n je méně než p, pak je jasné, že F_p, nemůže sdílet žádné běžné dělitele s předchozími čísly Fibonacci.

${ displaystyle gcd (F_ {p}, F_ {n}) = F _ { gcd (p, n)} = F_ {1} = 1.}$

Tohle znamená tamto F_p vždy bude mít charakteristické faktory nebo bude samotným hlavním charakteristickým faktorem. Počet odlišných hlavních faktorů každého Fibonacciho čísla lze shrnout jednoduše.

• F_nk je násobkem F_k pro všechny hodnoty n a k od 1 nahoru.^[8] Dá se to bezpečně říci F_nk bude mít "alespoň" stejný počet odlišných hlavních faktorů jako F_k. Všechno F_p nebude mít žádné faktory F_k, ale „alespoň“ jedna nová charakteristika připravená z Carmichaelova věta.

• Carmichaelova věta platí pro všechna čísla Fibonacci kromě 4 zvláštních případů: ${ displaystyle F_ {1} = F_ {2} = 1, F_ {6} = 8}$ a ${ displaystyle F_ {12} = 144.}$ Podíváme-li se na hlavní faktory Fibonacciho čísla, bude existovat alespoň jeden z nich, který se nikdy předtím neobjevil jako faktor jakéhokoli dřívějšího Fibonacciho čísla. Nechat π_n být počet odlišných hlavních faktorů F_n. (sekvence A022307 v OEIS )

Li k | n pak ${ displaystyle pi _ {n} geqslant pi _ {k} +1}$ až na ${ displaystyle pi _ {6} = pi _ {3} = 1.}$

Li k = 1 a n je liché prvočíslo, pak 1 | p a ${ displaystyle pi _ {p} geqslant pi _ {1} + 1 = 1.}$

První krok při hledání charakteristického kvocientu libovolného F_n je rozdělit hlavní faktory všech dřívějších Fibonacciho čísel F_k pro který k | n.^[9]

Přesné zbývající podíly jsou hlavními faktory, které se dosud neobjevily.

Li p a q jsou obě prvočísla, pak všechny faktory F_pq jsou charakteristické, kromě těch z F_p a F_q.

${ displaystyle { begin {aligned} gcd (F_ {pq}, F_ {q}) & = F _ { gcd (pq, q)} = F_ {q} gcd (F_ {pq}, F_ {p}) & = F _ { gcd (pq, p)} = F_ {p} end {zarovnáno}}}$

Proto:

${ displaystyle pi _ {pq} geqslant { begin {cases} pi _ {p} + pi _ {q} + 1 & p neq q pi _ {p} + 1 & p = q end { případy}}}$

Počet zřetelných prvočísel Fibonacciho čísel s prvočíslem je přímo relevantní pro funkci počítání. (sekvence A080345 v OEIS )

Hodnostní zjevení

Za nejlepší p, nejmenší index u > 0 takových F_u je dělitelné p se nazývá hodnost zjevení (někdy nazývané Fibonacciho vstupní bod) z p a označil A(p). Hodnost zjevení A(p) je definován pro každé prvočíslo p.^[10] Hodnost zjevení rozděluje Pisanské období π (p) a umožňuje určit všechna Fibonacciho čísla dělitelná p.^[11]

Pro dělitelnost Fibonacciho čísel mocninami prvočísla, ${ displaystyle p geqslant 3, n geqslant 2}$ a ${ displaystyle k geqslant 0}$

${ displaystyle p ^ {n} mid F_ {a (p) kp ^ {n-1}}.}$

Zejména

${ displaystyle p ^ {2} mid F_ {a (p) p}.}$

Zeď-slunce-slunce připraví

Prime p ≠ 2, 5 se nazývá Fibonacci – Wieferich prime nebo a Zeď-Slunce-Slunce -li ${ displaystyle p ^ {2} mid F_ {q},}$ kde

${ displaystyle q = p- left ({ frac {p} {5}} right)}$

ve kterém ${ displaystyle left ({ tfrac {p} {5}} right)}$ je Legendární symbol definováno jako:

${ displaystyle left ({ frac {p} {5}} right) = { begin {cases} 1 & p equiv pm 1 { bmod {5}} - 1 & p equiv pm 2 { bmod {5}} end {cases}}}$

Je známo, že pro p ≠ 2, 5, A(p) je dělitelem:^[12]

${ displaystyle p- left ({ frac {p} {5}} right) = { begin {cases} p-1 & p equiv pm 1 { bmod {5}} p + 1 & p equiv pm 2 { bmod {5}} end {případy}}}$

Pro každého p to není vrchol Wall-Sun-Sun, ${ displaystyle a (p ^ {2}) = pa (p)}$ jak je znázorněno v následující tabulce:

Existence prvočísel Wall-Sun-Sun je domněnka.

Fibonacciho primitivní část

The primitivní část z Fibonacciho čísel jsou

1, 1, 2, 3, 5, 4, 13, 7, 17, 11, 89, 6, 233, 29, 61, 47, 1597, 19, 4181, 41, 421, 199, 28657, 46, 15005, 521, 5777, 281, 514229, 31, 1346269, 2207, 19801, 3571, 141961, 321, 24157817, 9349, 135721, 2161, 165580141, 211, 433494437, 13201, 109441, ... (sekvence A061446 v OEIS )

Produkt primitivních prvočísel Fibonacciho čísel je

1, 1, 2, 3, 5, 1, 13, 7, 17, 11, 89, 1, 233, 29, 61, 47, 1597, 19, 4181, 41, 421, 199, 28657, 23, 3001, 521, 5777, 281, 514229, 31, 1346269, 2207, 19801, 3571, 141961, 107, 24157817, 9349, 135721, 2161, 165580141, 211, 433494437, 13201, 109441, 64079, 2971215073, 1103, 598364773, 15251 ... (sekvence A178763 v OEIS )

První případ více než jednoho primitivního prvočísla je 4181 = 37 × 113 pro ${ displaystyle F_ {19}}$.

Primitivní část má v některých případech neprimitivní primární faktor. Poměr mezi dvěma výše uvedenými sekvencemi je

1, 1, 1, 1, 1, 4, 1, 1, 1, 1, 1, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 7, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 13, 1, 1, .... (sekvence A178764 v OEIS )

Přirozená čísla n pro který ${ displaystyle F_ {n}}$ má právě jeden primitivní primární faktor

3, 4, 5, 7, 8, 9, 10, 11, 13, 14, 15, 16, 17, 18, 20, 21, 22, 23, 24, 25, 26, 28, 29, 30, 32, 33, 34, 35, 36, 38, 39, 40, 42, 43, 45, 47, 48, 51, 52, 54, 56, 60, 62, 63, 65, 66, 72, 74, 75, 76, 82, 83, 93, 94, 98, 105, 106, 108, 111, 112, 119, 121, 122, 123, 124, 125, 131, 132, 135, 136, 137, 140, 142, 144, 145, ... (sekvence A152012 v OEIS )

Kdyby jen hlavní p je tedy v tomto pořadí ${ displaystyle F_ {p}}$ je Fibonacciho prime, a právě když 2p je tedy v tomto pořadí ${ displaystyle L_ {p}}$ je Lucas připravuje (kde ${ displaystyle L_ {n}}$ je Lucasova sekvence ), a pokud a pouze pokud 2ⁿ je tedy v tomto pořadí ${ displaystyle L_ {2 ^ {n-1}}}$ je Lucas prime.

Počet primitivních prvočíselných faktorů ${ displaystyle F_ {n}}$ jsou

0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 1, 1, 1, 3, 1, 1, 1, 2, 1, 1, 2, 1, 2, 1, 1, 2, 2, 1, 1, 2, 1, 2, 1, 2, 2, 2, 1, 2, 1, 1, 2, 1, 1, 3, 2, 3, 2, 2, 1, 2, 1, 1, 1, 2, 2, 2, 2, 3, 1, 1, 2, 2, 2, 2, 3, 2, 2, 2, 2, 1, 1, 3, 2, 4, 1, 2, 2, 2, 2, 3, 2, 1, 1, 2, 1, 2, 2, 1, 1, 2, 2, 2, 2, 2, 3, 1, 2, 1, 1, 1, 1, 1, 2, 2, 2, ... (sekvence A086597 v OEIS )

Nejméně primitivní primární faktor ${ displaystyle F_ {n}}$ jsou

1, 1, 2, 3, 5, 1, 13, 7, 17, 11, 89, 1, 233, 29, 61, 47, 1597, 19, 37, 41, 421, 199, 28657, 23, 3001, 521, 53, 281, 514229, 31, 557, 2207, 19801, 3571, 141961, 107, 73, 9349, 135721, 2161, 2789, 211, 433494437, 43, 109441, 139, 2971215073, 1103, 97, 101, ... (sekvence A001578 v OEIS )

Viz také

• Lucasovo číslo

Reference

externí odkazy

• Weisstein, Eric W. „Fibonacci Prime“. MathWorld.
• R. Knott Fibonacciho prvočísla
• Caldwell, Chris. Fibonacciho číslo, Fibonacci prime, a Zaznamenejte Fibonacciho prvočísla na Prime Stránky
• Faktorizace prvních 300 Fibonacciho čísel
• Faktorizace Fibonacciho a Lucasových čísel
• Malý paralelní program Haskell k nalezení pravděpodobných Fibonacciho prvočísel na haskell.org