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 Fn 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 is osztója -nek; ebből azonban nem következik, hogy a Fibonacci-sorozat minden prím indexe Fibonacci-prímet adna.
Az Fp az első 10 prímszám közül 8-ra prímet eredményez, az F2 = 1 és F19 = 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 F81839, 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 F2904353. 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
Egy p≠5 prím akkor és csak akkor osztója Fp−1-nek, ha p kongruens ±1 (mod 5) és p akkor és csak akkor osztója Fp+1-nek, ha kongruens ±2 (mod 5). (A p=5 esetben F5=5, így 5 osztja F5-ö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(Fn, Fm) = FLNKO(n,m).[6]
Ha n ≥ 3, Fn akkor és csak akkor osztója Fm-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 Fp-nek nem lehet közös osztója a megelőző Fibonacci-számokkal.
- GCD(Fp, Fn) = FGCD(p,n) = F1 = 1
Ez azt jelenti, hogy Fp-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. „Fnk többszöröse Fk-nak bármely n és k pozitív egészekre.”[8]
- Kijelenthető, hogy Fnk legalább annyi különböző prímtényezővel fog rendelkezni, mint Fk.
- Az Fp az Fk 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 Fn különböző prímtényezőinek száma. (A022307 sorozat az OEIS-ben)
- Ha k | n, akkor πn >= πk+1. (kivétel: π6 = π3 = 1)
- Ha k=1 és n páratlan prímszám, akkor 1 | p és πp >= π1+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 Fn karakterisztikus prímosztóját keressük, az első lépés azon korábbi Fk 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 Fpq minden prímtényezője karakterisztikus, kivéve az Fp-ben vagy Fq-ban szereplőket.
- LNKO(Fpq, Fq) = FLNKO(pq,q) = Fq
- LNKO(Fpq, Fp) = FLNKO(pq,p) = Fp
- πpq>=πq+πp+1 (kivétel: πp2>=πp+1)
Például F247 π(19·13)>=(π13+π19)+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
![]() | 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 p2 osztója az Fq Fibonacci-számnak, ahol q éppen p mínusz a Legendre-szimbólum, aminek definíciója:
Egy p prímszámhoz tartozó legkisebb u > 0 index, melyre Fu 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 -nek, tehát -nek vagy -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 :
- pn | Fukpn-1
Továbbá, n=2 és k=1 esetén:
- p2 | Fpu
Minden olyan p prímre, ami nem Wall–Szun–Szun-prím, a(p2) = 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 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)
akkor és csak akkor Fibonacci-prím, ha a p prímszám szerepel ebben a sorozatban; továbbá akkor és csak akkor Lucas-prím, ha 2p szerepel a sorozatban (ahol a Lucas-sorozat); pedig akkor és csak akkor Lucas-prím, ha 2n szerepel a sorozatban.
Az 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 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
Jegyzetek
- ↑ 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
- 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