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 szerkesztés

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.^[1]

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.^[2] 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.^[3]^[4] 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.^[1] 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.^[5]

A Fibonacci-számok oszthatósága szerkesztés

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).^[6]

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

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.”^[8]

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
F_n	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.^[9]

Í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 szerkesztés

Bővebben: 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.^[10]

A megjelenés rendje, a(p) minden p prímszámra definiált.^[11] 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.^[12]

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(p²)	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 szerkesztés

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 szerkesztés

Lucas-számok

Jegyzetek szerkesztés

↑ ^a ^b PRP Top Records, Search for : F(n). Retrieved 2014-08-12.
↑ Sloane's A005478, A001605
↑ Number Theory Archives announcement by David Broadhurst and Bouk de Water
↑ Chris Caldwell, The Top Twenty: Fibonacci Number from the Prime Pages. Retrieved 2009-11-21.
↑ N. MacKinnon, Problem 10844, Amer. Math. Monthly 109, (2002), p. 78
↑ Paulo Ribenboim, My Numbers, My Friends, Springer-Verlag 2000
↑ Wells 1986, p.65
↑ The mathematical magic of Fibonacci numbers Factors of Fibonacci numbers
↑ Jarden - Recurring sequences, Volume 1, Fibonacci quarterly, by Brother U. Alfred
↑ Steven Vajda. Fibonacci and Lucas Numbers, and the Golden Section: Theory and Applications, Dover Books on Mathematics (1989)
↑ (A001602 sorozat az OEIS-ben)
↑ John Vinson (1963). „The Relation of the Period Modulo m to the Rank of Apparition of m in the Fibonacci Sequence”. Fibonacci Quarterly 1, 37-45. o.

További információk szerkesztés

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

[prptop-1] PRP Top Records, Search for : F(n). Retrieved 2014-08-12.

[2] Sloane's A005478, A001605

[3] Number Theory Archives announcement by David Broadhurst and Bouk de Water

[4] Chris Caldwell, The Top Twenty: Fibonacci Number from the Prime Pages. Retrieved 2009-11-21.

[5] N. MacKinnon, Problem 10844, Amer. Math. Monthly 109, (2002), p. 78

[6] Paulo Ribenboim, My Numbers, My Friends, Springer-Verlag 2000

[7] Wells 1986, p.65

[8] The mathematical magic of Fibonacci numbers Factors of Fibonacci numbers

[9] Jarden - Recurring sequences, Volume 1, Fibonacci quarterly, by Brother U. Alfred

[10] Steven Vajda. Fibonacci and Lucas Numbers, and the Golden Section: Theory and Applications, Dover Books on Mathematics (1989)

[11] (A001602 sorozat az OEIS-ben)

[12] John Vinson (1963). „The Relation of the Period Modulo m to the Rank of Apparition of m in the Fibonacci Sequence”. Fibonacci Quarterly 1, 37-45. o.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]