Fibonacci-prímek

A matematika, azon belül a számelmélet területén a Fibonacci-prímek olyan Fibonacci-számok, melyek egyben prímszámok is, így a számsorozatprímek közé tartoznak.

Az első néhány Fibonacci-prím:

2, 3, 5, 13, 89, 233, 1597, 28657, 514229, 433494437, 2971215073, ... (A005478 sorozat az OEIS-ben).

Ismert Fibonacci-prímek

Nem ismert, hogy végtelen sok Fibonacci-prímszám létezik-e. Az első 33 n érték, amire F_n Fibonacci-prím (A001605 sorozat az OEIS-ben):

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.

Ezeken a bizonyítottan prím Fibonacci-számokon kívül a következő sorszámokhoz tartoznak valószínű prímek:

n = 104911, 130021, 148091, 201107, 397379, 433781, 590041, 593689, 604711, 931517, 1049897, 1285607, 1636007, 1803059, 1968721, 2904353.

Az n = 4 eseten kívül minden Fibonacci-prím sorszáma is prím, mivel ha a osztója b-nek, akkor $F_{a}$ is osztója $F_{b}$-nek; ebből azonban nem következik, hogy a Fibonacci-sorozat minden prím indexe Fibonacci-prímet adna.

Az F_p az első 10 prímszám közül 8-ra prímet eredményez, az F₂ = 1 és F₁₉ = 4181 = 37 × 113 kivételével. A Fibonacci-prímek azonban az index növekedésével gyorsan ritkulni kezdenek: a 10 000 alatti 1229 darab prím közül mindössze 26 ad Fibonacci-prímet. A prím indexű Fibonacci-számok prímtényezőinek száma:

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, ... (A080345 sorozat az OEIS-ben)

2015 szeptemberében a legnagyobb ismert Fibonacci-prím (tehát nemcsak valószínű prím) az F₈₁₈₃₉, 17 103 jeggyel. Prímségét David Broadhurst és Bouk de Water bizonyították 2001-ben. A legnagyobb ismert Fibonacci-valószínű prím az F_2904353. Ez 606 974 számjeggyel írható le, és Henri Lifchitz találta meg 2014-ben. Nick MacKinnon megmutatta, hogy a Fibonacci-prímek közül kizárólag a következők ikerprímpár-tagok: 3, 5 és 13.

A Fibonacci-számok oszthatósága

Egy p≠5 prím akkor és csak akkor osztója F_p−1-nek, ha p kongruens ±1 (mod 5) és p akkor és csak akkor osztója F_p+1-nek, ha kongruens ±2 (mod 5). (A p=5 esetben F₅=5, így 5 osztja F₅-öt)

A p prím indexű Fibonacci-számoknak egyetlen közös osztójuk sincs a náluk kisebb Fibonacci-számokkal, a következő azonosság miatt:

LNKO(F_n, F_m) = F_LNKO(n,m).

Ha n ≥ 3, F_n akkor és csak akkor osztója F_m-nek, ha n osztója m-nek.

Ha feltesszük, hogy m a fenti azonosságban szereplő p prímszám és n kisebb p-nél, akkor nyilvánvaló, hogy F_p-nek nem lehet közös osztója a megelőző Fibonacci-számokkal.

GCD(F_p, F_n) = F_GCD(p,n) = F₁ = 1

Ez azt jelenti, hogy F_p-nek mindig karakterisztikus prímtényezői lesznek, vagy maga is prím lesz. Az egyes Fibonacci-számok különböző prímtényezőinek száma egyszerűen megfogalmazható.

• 1. „F_nk többszöröse F_k-nak bármely n és k pozitív egészekre.”

Kijelenthető, hogy F_nk legalább annyi különböző prímtényezővel fog rendelkezni, mint F_k.

Az F_p az F_k egyetlen prímtényezőjével sem fog rendelkezni, de a Carmichael-tétel alapján legalább egy karakterisztikus prímtényezővel igen.

• 2. A Carmichael-tétel minden Fibonacci-számra igaz, néhány speciális eset (1, 8 és 144) kivételével

„Ha megvizsgáljuk egy Fibonacci-szám prímtényezőit, legalább egy olyat fogunk találni, ami egyetlen kisebb Fibonacci-szám prímtényezői között sem szerepelt.”

Legyen π_n az F_n különböző prímtényezőinek száma. (A022307 sorozat az OEIS-ben)

Ha k | n, akkor π_n >= π_k+1. (kivétel: π₆ = π₃ = 1)

Ha k=1 és n páratlan prímszám, akkor 1 | p és π_p >= π₁+1, vagy egyszerűbben: π_p>=1.

n	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25
Fn	0	1	1	2	3	5	8	13	21	34	55	89	144	233	377	610	987	1597	2584	4181	6765	10946	17711	28657	46368	75025
πn	0	0	0	1	1	1	1	1	2	2	2	1	2	1	2	3	3	1	3	2	4	3	2	1	4	2

Ha az F_n karakterisztikus prímosztóját keressük, az első lépés azon korábbi F_k Fibonacci-számok prímosztóival való leosztás, melyekre k | n.

Így pontosan azok a tényezők maradnak meg, melyek még nem jelentek meg a sorozatban.

Ha p és q is prímszámok, akkor F_pq minden prímtényezője karakterisztikus, kivéve az F_p-ben vagy F_q-ban szereplőket.

LNKO(F_pq, F_q) = F_LNKO(pq,q) = F_q

LNKO(F_pq, F_p) = F_LNKO(pq,p) = F_p

π_pq>=π_q+π_p+1 (kivétel: π_p²>=π_p+1)

Például F₂₄₇ π_(19·13)>=(π₁₃+π₁₉)+1.

A prím indexű Fibonacci-számok különböző prímosztóinak száma (A080345 sorozat az OEIS-ben):

p	2	3	5	7	11	13	17	19	23	29	31	37	41	43	47	53	59	61	67	71	73	79	83	89	97
πp	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

Wall–Szun–Szun-prímek

Egy p ≠ 2, 5 prímet Fibonacci–Wieferich-prímnek vagy Wall–Szun–Szun-prímnek nevezünk, ha p² osztója az F_q Fibonacci-számnak, ahol q éppen p mínusz a $\left({\tfrac {p}{5}}\right)$ Legendre-szimbólum, aminek definíciója:

$\left({\frac {p}{5}}\right)={\begin{cases}1&{\text{ha }}p\equiv \pm 1{\pmod {5}}\\-1&{\text{ha }}p\equiv \pm 2{\pmod {5}}\end{cases}}$

Egy p prímszámhoz tartozó legkisebb u > 0 index, melyre F_u osztható p-vel a megjelenés rendje (rank of apparition) vagy p Fibonacci-belépési pontja (Fibonacci entry point), jelölése a(p). Ismert, hogy minden p ≠ 2, 5 számra a(p) osztója $p-\left({\tfrac {p}{5}}\right)$-nek, tehát $p-1$-nek vagy $p+1$-nek.

A megjelenés rendje, a(p) minden p prímszámra definiált. A megjelenés rendje osztója a π(p) Pisano-periódusnak és segítségével meghatározható az összes, a p prímszámmal osztható Fibonacci-szám.

Egy adott prímszám hatványainak oszthatóságával kapcsolatban, ha $p\geq 3,n\geq 2,k\geq 0$:

pⁿ | F_ukp^n-1

Továbbá, n=2 és k=1 esetén:

p² | F_pu

Minden olyan p prímre, ami nem Wall–Szun–Szun-prím, a(p²) = a(p) · p, ahogy az alábbi táblázat is mutatja:

p	2	3	5	7	11	13	17	19	23	29	31	37	41	43	47	53	59	61
a(p)	3	4	5	8	10	7	9	18	24	14	30	19	20	44	16	27	58	15
a(p2)	6	12	25	56	110	91	153	342	552	406	930	703	820	1892	752	1431	3422	915

Fibonacci-számok primitív része

A Fibonacci-számok primitív része:

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, ... (A178763 sorozat az OEIS-ben)

Az n természetes számok, melyekre az $F_{n}$ primitív részre prím adódik:

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, ... (A152012 sorozat az OEIS-ben)

$F_{p}$ akkor és csak akkor Fibonacci-prím, ha a p prímszám szerepel ebben a sorozatban; továbbá $L_{p}$ akkor és csak akkor Lucas-prím, ha 2p szerepel a sorozatban (ahol $L_{n}$ a Lucas-sorozat); $L_{2^{n-1}}$ pedig akkor és csak akkor Lucas-prím, ha 2ⁿ szerepel a sorozatban.

Az $F_{n}$ primitív prímtényezőinek száma:

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, 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, ... (A086597 sorozat az OEIS-ben)

Az $F_{n}$ legkisebb primitív prímtényezői:

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, ... (A001578 sorozat az OEIS-ben)

Kapcsolódó szócikkek

• Lucas-számok

További információk

• Weisstein, Eric W.: Fibonacci Prime (angol nyelven). Wolfram MathWorld
• R. Knott Fibonacci primes
• Caldwell, Chris. Fibonacci number, Fibonacci prime, and Record Fibonacci primes at the Prime Pages
• Factorization of the first 300 Fibonacci numbers
• Factorization of Fibonacci and Lucas numbers Archiválva 2016. augusztus 19-i dátummal a Wayback Machine-ben
• Small parallel Haskell program to find probable Fibonacci primes at haskell.org