Lucasova sekvence - Lucas sequence

v matematika, Lucasovy sekvence ${ displaystyle U_ {n} (P, Q)}$ a ${ displaystyle V_ {n} (P, Q)}$ jsou si jistí konstantní rekurzivní celočíselné sekvence které uspokojí relace opakování

${ displaystyle x_ {n} = P cdot x_ {n-1} -Q cdot x_ {n-2}}$

kde ${ displaystyle P}$ a ${ displaystyle Q}$ jsou pevná celá čísla. Jakoukoli sekvenci splňující tento vztah opakování lze reprezentovat jako a lineární kombinace Lucasových sekvencí ${ displaystyle U_ {n} (P, Q)}$ a ${ displaystyle V_ {n} (P, Q)}$.

Obecněji řečeno, Lucasovy sekvence ${ displaystyle U_ {n} (P, Q)}$ a ${ displaystyle V_ {n} (P, Q)}$ představují sekvence polynomy v ${ displaystyle P}$ a ${ displaystyle Q}$ s celočíselnými koeficienty.

Slavné příklady Lucasových sekvencí zahrnují Fibonacciho čísla, Mersennova čísla, Pell čísla, Lucasova čísla, Jacobsthal čísla a nadmnožinu Fermat čísla. Lucasovy sekvence jsou pojmenovány po francouzština matematik Édouard Lucas.

Vztahy opakování

Vzhledem k tomu, dva celočíselné parametry P a Q, Lucasovy sekvence prvního druhu U_n(P,Q) a druhého druhu PROTI_n(P,Q) jsou definovány relace opakování:

${ displaystyle { begin {aligned} U_ {0} (P, Q) & = 0, U_ {1} (P, Q) & = 1, U_ {n} (P, Q) & = P cdot U_ {n-1} (P, Q) -Q cdot U_ {n-2} (P, Q) { mbox {for}} n> 1, end {zarovnáno}}}$

a

${ displaystyle { begin {aligned} V_ {0} (P, Q) & = 2, V_ {1} (P, Q) & = P, V_ {n} (P, Q) & = P cdot V_ {n-1} (P, Q) -Q cdot V_ {n-2} (P, Q) { mbox {pro}} n> 1. end {zarovnáno}}}$

Není těžké to ukázat ${ displaystyle n> 0}$,

${ displaystyle { begin {aligned} U_ {n} (P, Q) & = { frac {P cdot U_ {n-1} (P, Q) + V_ {n-1} (P, Q) } {2}}, V_ {n} (P, Q) & = { frac {(P ^ {2} -4Q) cdot U_ {n-1} (P, Q) + P cdot V_ {n-1} (P, Q)} {2}}. end {zarovnáno}}}$

Příklady

Počáteční podmínky Lucasových sekvencí U_n(P,Q) a PROTI_n(P,Q) jsou uvedeny v tabulce:

${ displaystyle { begin {array} {r | l | l} n & U_ {n} (P, Q) & V_ {n} (P, Q) hline 0 & 0 & 2 1 & 1 & P 2 & P & {P} ^ { 2} -2Q 3 & {P} ^ {2} -Q & {P} ^ {3} -3PQ 4 & {P} ^ {3} -2PQ & {P} ^ {4} -4 {P} ^ {2} Q + 2 {Q} ^ {2} 5 & {P} ^ {4} -3 {P} ^ {2} Q + {Q} ^ {2} & {P} ^ {5} -5 {P} ^ {3} Q + 5P {Q} ^ {2} 6 & {P} ^ {5} -4 {P} ^ {3} Q + 3P {Q} ^ {2} & {P} ^ {6} -6 {P} ^ {4} Q + 9 {P} ^ {2} {Q} ^ {2} -2 {Q} ^ {3} end {pole}}}$

Výslovné výrazy

Charakteristická rovnice relace rekurence pro Lucasovy sekvence ${ displaystyle U_ {n} (P, Q)}$ a ${ displaystyle V_ {n} (P, Q)}$ je:

${ displaystyle x ^ {2} -Px + Q = 0 ,}$

Má to diskriminující ${ displaystyle D = P ^ {2} -4Q}$ a kořeny:

${ displaystyle a = { frac {P + { sqrt {D}}} {2}} quad { text {a}} quad b = { frac {P - { sqrt {D}}} { 2}}. ,}$

Tím pádem:

${ displaystyle a + b = P ,,}$

${ displaystyle ab = { frac {1} {4}} (P ^ {2} -D) = Q ,,}$

${ displaystyle a-b = { sqrt {D}} ,.}$

Všimněte si, že sekvence ${ displaystyle a ^ {n}}$ a sekvence ${ displaystyle b ^ {n}}$ také uspokojit relaci opakování. Nemusí to však být celočíselné sekvence.

Výrazné kořeny

Když ${ displaystyle D neq 0}$, A a b jsou odlišné a jeden si to rychle ověří

${ displaystyle a ^ {n} = { frac {V_ {n} + U_ {n} { sqrt {D}}} {2}}}$

${ displaystyle b ^ {n} = { frac {V_ {n} -U_ {n} { sqrt {D}}} {2}}}$.

Z toho vyplývá, že termíny Lucasových sekvencí lze vyjádřit pomocí A a b jak následuje

${ displaystyle U_ {n} = { frac {a ^ {n} -b ^ {n}} {ab}} = { frac {a ^ {n} -b ^ {n}} { sqrt {D }}}}$

${ displaystyle V_ {n} = a ^ {n} + b ^ {n} ,}$

Opakovaný kořen

Pouzdro ${ displaystyle D = 0}$ nastane přesně kdy ${ displaystyle P = 2S { text {and}} Q = S ^ {2}}$ pro celé číslo S aby ${ displaystyle a = b = S}$. V tomto případě to člověk snadno zjistí

${ displaystyle U_ {n} (P, Q) = U_ {n} (2S, S ^ {2}) = nS ^ {n-1} ,}$

${ displaystyle V_ {n} (P, Q) = V_ {n} (2S, S ^ {2}) = 2S ^ {n} ,}$.

Vlastnosti

Generování funkcí

Obyčejný generující funkce jsou

${ displaystyle sum _ {n geq 0} U_ {n} (P, Q) z ^ {n} = { frac {z} {1-Pz + Qz ^ {2}}};}$

${ displaystyle sum _ {n geq 0} V_ {n} (P, Q) z ^ {n} = { frac {2-Pz} {1-Pz + Qz ^ {2}}}.}$

Sekvence se stejnou diskriminací

Pokud sekvence Lucas ${ displaystyle U_ {n} (P, Q)}$ a ${ displaystyle V_ {n} (P, Q)}$ nediskriminační ${ displaystyle D = P ^ {2} -4Q}$, pak sekvence založené na ${ displaystyle P_ {2}}$ a ${ displaystyle Q_ {2}}$ kde

${ displaystyle P_ {2} = P + 2}$

${ displaystyle Q_ {2} = P + Q + 1}$

mít stejný diskriminátor: ${ displaystyle P_ {2} ^ {2} -4Q_ {2} = (P + 2) ^ {2} -4 (P + Q + 1) = P ^ {2} -4Q = D}$.

Pellovy rovnice

Když ${ displaystyle Q = pm 1}$, Lucasovy sekvence ${ displaystyle U_ {n} (P, Q)}$ a ${ displaystyle V_ {n} (P, Q)}$ uspokojit jisté Pellovy rovnice:

${ displaystyle V_ {n} (P, 1) ^ {2} -D cdot U_ {n} (P, 1) ^ {2} = 4,}$

${ displaystyle V_ {2n} (P, -1) ^ {2} -D cdot U_ {2n} (P, -1) ^ {2} = 4,}$

${ displaystyle V_ {2n + 1} (P, -1) ^ {2} -D cdot U_ {2n + 1} (P, -1) ^ {2} = - 4.}$

Další vztahy

Termíny Lucasových sekvencí uspokojují vztahy, které jsou zevšeobecněním těch mezi nimi Fibonacciho čísla ${ displaystyle F_ {n} = U_ {n} (1, -1)}$ a Lucasova čísla ${ displaystyle L_ {n} = V_ {n} (1, -1)}$. Například:

${ displaystyle { begin {pole} {r | l} { text {obecný případ}} & (P, Q) = (1, -1) hline (P ^ {2} -4Q) U_ { n} = {V_ {n + 1} -QV_ {n-1}} = 2V_ {n + 1} -PV_ {n} & 5F_ {n} = {L_ {n + 1} + L_ {n-1}} = 2L_ {n + 1} -L_ {n} V_ {n} = U_ {n + 1} -QU_ {n-1} = 2U_ {n + 1} -PU_ {n} & L_ {n} = F_ {n + 1} + F_ {n-1} = 2F_ {n + 1} -F_ {n} U_ {2n} = U_ {n} V_ {n} & F_ {2n} = F_ {n} L_ { n} V_ {2n} = V_ {n} ^ {2} -2Q ^ {n} & L_ {2n} = L_ {n} ^ {2} -2 (-1) ^ {n} U_ { m + n} = U_ {n} U_ {m + 1} -QU_ {m} U_ {n-1} = { frac {U_ {m} V_ {n} + U_ {n} V_ {m}} { 2}} & F_ {m + n} = F_ {n} F_ {m + 1} + F_ {m} F_ {n-1} = { frac {F_ {m} L_ {n} + F_ {n} L_ {m}} {2}} V_ {m + n} = V_ {m} V_ {n} -Q ^ {n} V_ {mn} = DU_ {m} U_ {n} + Q ^ {n} V_ {mn} & L_ {m + n} = L_ {m} L_ {n} - (- 1) ^ {n} L_ {mn} = 5F_ {m} F_ {n} + (- 1) ^ {n} L_ {mn} V_ {n} ^ {2} -DU_ {n} ^ {2} = 4Q ^ {n} & L_ {n} ^ {2} -5F_ {n} ^ {2} = 4 (- 1) ^ {n} U_ {n} ^ {2} -U_ {n-1} U_ {n + 1} = Q ^ {n-1} & F_ {n} ^ {2} -F_ {n- 1} F_ {n + 1} = (- 1) ^ {n-1} DU_ {n} = V_ {n + 1} -QV_ {n-1} & F_ {n} = { frac {L_ { n + 1} + L_ {n-1}} {5}} V_ {m + n} = { frac {V_ {m} V_ {n} + DU_ {m} U_ {n}} {2} } & L_ {m + n} = { frac {L_ {m} L_ {n} + 5F_ {m} F_ {n}} {2}} U_ {m + n} = U_ {m} V_ {n } -Q ^ {n} U_ {mn} & F_ {n + m} = F_ {m} L_ {n} - (- 1) ^ {n} F_ {mn} 2 ^ {n-1} U_ { n} = {n zvolit 1} P ^ {n-1} + {n zvolit 3} P ^ {n-3} D + cdots & 2 ^ {n-1} F_ {n} = {n select 1} +5 {n choose 3} + cdots 2 ^ {n-1} V_ {n} = P ^ {n} + {n select 2} P ^ {n-2} D + {n choose 4} P ^ {n-4} D ^ {2} + cdots & 2 ^ {n-1} L_ {n} = 1 + 5 {n vyberte 2} + 5 ^ {2} {n zvolte 4} + cdots end {pole}}}$

Mezi následky to patří ${ displaystyle U_ {km} (P, Q)}$ je násobkem ${ displaystyle U_ {m} (P, Q)}$sekvence ${ displaystyle (U_ {m} (P, Q)) _ {m geq 1}}$je posloupnost dělitelnosti. Z toho zejména vyplývá, že ${ displaystyle U_ {n} (P, Q)}$ může být hlavní, pouze když n je hlavní. Dalším důsledkem je analogie umocňování druhou mocninou , který umožňuje rychlý výpočet ${ displaystyle U_ {n} (P, Q)}$ pro velké hodnoty n. Navíc pokud ${ displaystyle gcd (P, Q) = 1}$, pak ${ displaystyle (U_ {m} (P, Q)) _ {m geq 1}}$ je silná posloupnost dělitelnosti.

Další vlastnosti dělitelnosti jsou následující:^[1]

• Li n / m je tedy zvláštní ${ displaystyle V_ {m}}$ rozděluje ${ displaystyle V_ {n}}$.
• Nechat N být celé číslo relativně prime k 2Q. Pokud je nejmenší kladné celé číslo r pro který N rozděluje ${ displaystyle U_ {r}}$ existuje, pak sada n pro který N rozděluje ${ displaystyle U_ {n}}$ je přesně množina násobků r.
• Li P a Q jsou tedy vyrovnané ${ displaystyle U_ {n}, V_ {n}}$ jsou vždy dokonce s výjimkou ${ displaystyle U_ {1}}$.
• Li P je sudé a Q je liché, pak parita ${ displaystyle U_ {n}}$ je stejné jako n a ${ displaystyle V_ {n}}$ je vždy rovnoměrné.
• Li P je liché a Q je tedy vyrovnaný ${ displaystyle U_ {n}, V_ {n}}$ jsou vždy zvláštní pro ${ displaystyle n = 1,2, ldots}$.
• Li P a Q jsou tedy zvláštní ${ displaystyle U_ {n}, V_ {n}}$ jsou i když a jen tehdy n je násobkem 3.
• Li p je tedy liché prvočíslo ${ displaystyle U_ {p} equiv left ({ frac {D} {p}} right), V_ {p} equiv P { pmod {p}}}$ (vidět Legendární symbol ).
• Li p je liché prvočíslo a dělí se P a Q, pak p rozděluje ${ displaystyle U_ {n}}$ pro každého ${ displaystyle n> 1}$.
• Li p je liché prvočíslo a dělí se P ale ne Q, pak p rozděluje ${ displaystyle U_ {n}}$ kdyby a jen kdyby n je sudý.
• Li p je liché prvočíslo a nerozděluje P ale Q, pak p nikdy nedělí ${ displaystyle U_ {n}}$ pro ${ displaystyle n = 1,2, ldots}$.
• Li p je liché prvočíslo a nerozděluje PQ ale D, pak p rozděluje ${ displaystyle U_ {n}}$ kdyby a jen kdyby p rozděluje n.
• Li p je liché prvočíslo a nedělí se PQD, pak p rozděluje ${ displaystyle U_ {l}}$, kde ${ displaystyle l = p- left ({ frac {D} {p}} right)}$.

Poslední skutečnost se zobecňuje Fermatova malá věta. Tato fakta jsou používána v Lucas – Lehmerův test primality Konverzace posledního faktu neplatí, protože konverzace Fermatovy malé věty neplatí. Existuje kompozit n relativně prime to D a dělení ${ displaystyle U_ {l}}$, kde ${ displaystyle l = n- vlevo ({ frac {D} {n}} vpravo)}$. Takový kompozit se nazývá Lucas pseudoprime.

A hlavní faktor se nazývá termín v Lucasově posloupnosti, který nerozděluje žádný dřívější výraz v posloupnosti primitivní.Carmichaelova věta uvádí, že až na konečně mnoho termínů v Lucasově sekvenci má primitiv hlavní faktor.^[2] Carmichael (1913) skutečně ukázal, že pokud D je pozitivní a n není tedy 1, 2 nebo 6 ${ displaystyle U_ {n}}$ má primitivní primární faktor. V případě D je negativní, hluboký výsledek Bilu, Hanrota, Voutiera a Mignotte^[3] ukazuje, že pokud n > 30, tedy ${ displaystyle U_ {n}}$ má primitivní primární faktor a určuje všechny případy ${ displaystyle U_ {n}}$ nemá primitivní primární faktor.

Konkrétní jména

Lucasovy sekvence pro některé hodnoty P a Q mít konkrétní jména:

U_n(1,−1) : Fibonacciho čísla

PROTI_n(1,−1) : Lucasova čísla

U_n(2,−1) : Pell čísla

PROTI_n(2,−1) : Čísla Pell-Lucase (doprovodná čísla Pell)

U_n(1,−2) : Jacobsthal čísla

PROTI_n(1,−2) : Jacobsthal-Lucas čísla

U_n(3, 2) : Mersennova čísla 2ⁿ − 1

PROTI_n(3, 2) : Čísla formuláře 2ⁿ + 1, které zahrnují Fermat čísla (Yabuta 2001 ) chyba harv: více cílů (2 ×): CITEREFYabuta2001 (Pomoc).

U_n(6, 1) : Druhé odmocniny čtvercová trojúhelníková čísla.

U_n(X,−1) : Fibonacciho polynomy

PROTI_n(X,−1) : Lucasovy polynomy

U_n(2X, 1) : Čebyševovy polynomy druhého druhu

PROTI_n(2X, 1) : Čebyševovy polynomy prvního druhu vynásobené 2

U_n(X+1, X) : Repunits základna X

PROTI_n(X+1, X) : Xⁿ + 1

Některé Lucasovy sekvence mají záznamy v On-line encyklopedie celočíselných sekvencí:

${ displaystyle P ,}$	${ displaystyle Q ,}$	${ displaystyle U_ {n} (P, Q) ,}$	${ displaystyle V_ {n} (P, Q) ,}$
−1	3	OEIS: A214733
1	−1	OEIS: A000045	OEIS: A000032
1	1	OEIS: A128834	OEIS: A087204
1	2	OEIS: A107920	OEIS: A002249
2	−1	OEIS: A000129	OEIS: A002203
2	1	OEIS: A001477
2	2	OEIS: A009545	OEIS: A007395
2	3	OEIS: A088137
2	4	OEIS: A088138
2	5	OEIS: A045873
3	−5	OEIS: A015523	OEIS: A072263
3	−4	OEIS: A015521	OEIS: A201455
3	−3	OEIS: A030195	OEIS: A172012
3	−2	OEIS: A007482	OEIS: A206776
3	−1	OEIS: A006190	OEIS: A006497
3	1	OEIS: A001906	OEIS: A005248
3	2	OEIS: A000225	OEIS: A000051
3	5	OEIS: A190959
4	−3	OEIS: A015530	OEIS: A080042
4	−2	OEIS: A090017
4	−1	OEIS: A001076	OEIS: A014448
4	1	OEIS: A001353	OEIS: A003500
4	2	OEIS: A007070	OEIS: A056236
4	3	OEIS: A003462	OEIS: A034472
4	4	OEIS: A001787
5	−3	OEIS: A015536
5	−2	OEIS: A015535
5	−1	OEIS: A052918	OEIS: A087130
5	1	OEIS: A004254	OEIS: A003501
5	4	OEIS: A002450	OEIS: A052539
6	1	OEIS: A001109	OEIS: A003499

Aplikace

• Lucasovy sekvence se používají pravděpodobnostně Lucas pseudoprime testy, které jsou součástí běžně používaných Baityho-PSW test primality.
• Lucasovy sekvence se používají v některých metodách ověřování primality, včetně Test Lucas-Lehmer-Riesel a metody N + 1 a hybridní N-1 / N + 1, jako jsou metody v Brillhart-Lehmer-Selfridge 1975^[4]
• LUC je a kryptosystém veřejného klíče na základě Lucasových sekvencí^[5] který implementuje analogy ElGamal (LUCELG), Diffie-Hellman (LUCDIF) a RSA (LUCRSA). Šifrování zprávy v LUC se počítá jako výraz určité Lucasovy posloupnosti, namísto použití modulární umocňování jako v RSA nebo Diffie-Hellman. Avšak článek Bleichenbachera a kol.^[6] ukazuje, že mnoho z předpokládaných bezpečnostních výhod LUC oproti kryptosystémům založeným na modulární umocňování buď není přítomno, nebo není tak podstatné, jak se tvrdí.

Viz také

• Lucas pseudoprime
• Frobenius pseudoprime
• Somer – Lucas pseudoprime

Poznámky

Reference

• Carmichael, R. D. (1913), „O numerických faktorech aritmetických forem αⁿ± βⁿ", Annals of Mathematics, 15 (1/4): 30–70, doi:10.2307/1967797, JSTOR  1967797CS1 maint: ref = harv (odkaz)
• Lehmer, D. H. (1930). "Rozšířená teorie Lucasových funkcí". Annals of Mathematics. 31 (3): 419–448. Bibcode:1930AnMat..31..419L. doi:10.2307/1968235. JSTOR  1968235.CS1 maint: ref = harv (odkaz)
• Ward, Morgan (1954). "Prime dělitele opakujících se sekvencí druhého řádu". Vévoda Math. J. 21 (4): 607–614. doi:10.1215 / S0012-7094-54-02163-8. hdl:10338.dmlcz / 137477. PAN  0064073.CS1 maint: ref = harv (odkaz)
• Somer, Lawrence (1980). „Vlastnosti dělitelnosti primárních Lucasových opakování s ohledem na prvočísla“ (PDF). Fibonacci čtvrtletně. 18: 316.CS1 maint: ref = harv (odkaz)
• Lagarias, J. C. (1985). "Sada prvočísel dělících Lucasova čísla má hustotu 2/3". Pac. J. Math. 118 (2): 449–461. doi:10.2140 / pjm.1985.118.449. PAN  0789184.CS1 maint: ref = harv (odkaz)
• Hans Riesel (1994). Prvočísla a počítačové metody pro faktorizaci. Pokrok v matematice. 126 (2. vyd.). Birkhäuser. 107–121. ISBN  0-8176-3743-5.CS1 maint: ref = harv (odkaz)
• Ribenboim, Paulo; McDaniel, Wayne L. (1996). "Čtvercové výrazy v Lucasových sekvencích". J. Teorie čísel. 58 (1): 104–123. doi:10.1006 / jnth.1996.0068.CS1 maint: ref = harv (odkaz)
• Joye, M .; Quisquater, J.-J. (1996). "Efektivní výpočet plných Lucasových sekvencí" (PDF). Elektronické dopisy. 32 (6): 537–538. doi:10.1049 / el: 19960359. Archivovány od originál (PDF) dne 02.02.2015.CS1 maint: ref = harv (odkaz)
• Ribenboim, Paulo (1996). Nová kniha rekordů prvočísel (eBook ed.). Springer-Verlag, New York. doi:10.1007/978-1-4612-0759-7. ISBN  978-1-4612-0759-7.CS1 maint: ref = harv (odkaz)
• Ribenboim, Paulo (2000). Moje čísla, moji přátelé: Populární přednášky o teorii čísel. New York: Springer-Verlag. s. 1–50. ISBN  0-387-98911-0.CS1 maint: ref = harv (odkaz)
• Luca, Florian (2000). "Perfektní čísla Fibonacciho a Lucase". Vykreslit. Circ Matem. Palermo. 49 (2): 313–318. doi:10.1007 / BF02904236. S2CID  121789033.CS1 maint: ref = harv (odkaz)
• Yabuta, M. (2001). „Jednoduchý důkaz Carmichaelovy věty o primitivních dělitelích“ (PDF). Fibonacci čtvrtletně. 39: 439–443.CS1 maint: ref = harv (odkaz)
• Benjamin, Arthur T.; Quinn, Jennifer J. (2003). Důkazy, které se skutečně počítají: Umění kombinatorického důkazu. Dolcianiho matematické expozice. 27. Mathematical Association of America. str.35. ISBN  978-0-88385-333-7.CS1 maint: ref = harv (odkaz)
• Lucasova sekvence na Encyclopedia of Mathematics.
• Weisstein, Eric W. „Lucas Sequence“. MathWorld.
• Wei Dai. „Lucasovy sekvence v kryptografii“.