गणित में, लुकास अनुक्रम U n ( P , Q ) {\displaystyle U_{n}(P,Q)} V n ( P , Q ) {\displaystyle V_{n}(P,Q)} पुनरावृत्ति संबंध को प्रदर्शित करते हैं
x n = P ⋅ x n − 1 − Q ⋅ x n − 2 {\displaystyle x_{n}=P\cdot x_{n-1}-Q\cdot x_{n-2}} जहाँ P {\displaystyle P} Q {\displaystyle Q} पूर्णांक होता हैं। इस पुनरावृत्ति संबंध को सरल करने वाले किसी भी अनुक्रम को लुकास अनुक्रमों U n ( P , Q ) {\displaystyle U_{n}(P,Q)} V n ( P , Q ) {\displaystyle V_{n}(P,Q)} रैखिक संयोजन के रूप में प्रदर्शित किया जा सकता है।
अधिक सामान्यतः, लुकास अनुक्रम U n ( P , Q ) {\displaystyle U_{n}(P,Q)} V n ( P , Q ) {\displaystyle V_{n}(P,Q)} बहुपद के अनुक्रम का प्रतिनिधित्व P {\displaystyle P} Q {\displaystyle Q}
लुकास अनुक्रमों के प्रसिद्ध उदाहरणों में फाइबोनैचि संख्या एं, मेरसेन संख्याएं, पेल संख्याएं, लुकास संख्याएं, जैकबस्टल संख्याएं और फर्मेट संख्याओं का श्रेष्ट समुच्चय सम्मिलित होता हैं (नीचे देखें)। इस प्रकार लुकास अनुक्रमों का नाम फ्रांस के गणितज्ञ एडवर्ड लुकास के नाम पर रखा गया था।
पुनरावृत्ति संबंध दो पूर्णांक पैरामीटर P {\displaystyle P} Q {\displaystyle Q} U n ( P , Q ) {\displaystyle U_{n}(P,Q)} V n ( P , Q ) {\displaystyle V_{n}(P,Q)}
U 0 ( P , Q ) = 0 , U 1 ( P , Q ) = 1 , U n ( P , Q ) = P ⋅ U n − 1 ( P , Q ) − Q ⋅ U n − 2 ( P , Q ) for n > 1 , {\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{aligned}}} और
V 0 ( P , Q ) = 2 , V 1 ( P , Q ) = P , V n ( P , Q ) = P ⋅ V n − 1 ( P , Q ) − Q ⋅ V n − 2 ( P , Q ) for n > 1. {\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{ for }}n>1.\end{aligned}}} n > 0 {\displaystyle n>0}
U n ( P , Q ) = P ⋅ U n − 1 ( P , Q ) + V n − 1 ( P , Q ) 2 , V n ( P , Q ) = ( P 2 − 4 Q ) ⋅ U n − 1 ( P , Q ) + P ⋅ V n − 1 ( P , Q ) 2 . {\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{aligned}}} उपरोक्त संबंधों का आव्युह रूप में इस प्रकार वर्णित किया जा सकता है:
[ U n ( P , Q ) U n + 1 ( P , Q ) ] = [ 0 1 − Q P ] ⋅ [ U n − 1 ( P , Q ) U n ( P , Q ) ] , {\displaystyle {\begin{bmatrix}U_{n}(P,Q)\\U_{n+1}(P,Q)\end{bmatrix}}={\begin{bmatrix}0&1\\-Q&P\end{bmatrix}}\cdot {\begin{bmatrix}U_{n-1}(P,Q)\\U_{n}(P,Q)\end{bmatrix}},}
[ V n ( P , Q ) V n + 1 ( P , Q ) ] = [ 0 1 − Q P ] ⋅ [ V n − 1 ( P , Q ) V n ( P , Q ) ] , {\displaystyle {\begin{bmatrix}V_{n}(P,Q)\\V_{n+1}(P,Q)\end{bmatrix}}={\begin{bmatrix}0&1\\-Q&P\end{bmatrix}}\cdot {\begin{bmatrix}V_{n-1}(P,Q)\\V_{n}(P,Q)\end{bmatrix}},}
[ U n ( P , Q ) V n ( P , Q ) ] = [ P / 2 1 / 2 ( P 2 − 4 Q ) / 2 P / 2 ] ⋅ [ U n − 1 ( P , Q ) V n − 1 ( P , Q ) ] . {\displaystyle {\begin{bmatrix}U_{n}(P,Q)\\V_{n}(P,Q)\end{bmatrix}}={\begin{bmatrix}P/2&1/2\\(P^{2}-4Q)/2&P/2\end{bmatrix}}\cdot {\begin{bmatrix}U_{n-1}(P,Q)\\V_{n-1}(P,Q)\end{bmatrix}}.}
उदाहरण लुकास अनुक्रमों की प्रारंभिक स्थितियां U n ( P , Q ) {\displaystyle U_{n}(P,Q)} V n ( P , Q ) {\displaystyle V_{n}(P,Q)}
n U n ( P , Q ) V n ( P , Q ) 0 0 2 1 1 P 2 P P 2 − 2 Q 3 P 2 − Q P 3 − 3 P Q 4 P 3 − 2 P Q P 4 − 4 P 2 Q + 2 Q 2 5 P 4 − 3 P 2 Q + Q 2 P 5 − 5 P 3 Q + 5 P Q 2 6 P 5 − 4 P 3 Q + 3 P Q 2 P 6 − 6 P 4 Q + 9 P 2 Q 2 − 2 Q 3 {\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{array}}}
स्पष्ट अभिव्यक्ति लुकास अनुक्रमों के लिए पुनरावृत्ति संबंध का विशिष्ट समीकरण U n ( P , Q ) {\displaystyle U_{n}(P,Q)} V n ( P , Q ) {\displaystyle V_{n}(P,Q)}
x 2 − P x + Q = 0 {\displaystyle x^{2}-Px+Q=0\,} इसमें D = P 2 − 4 Q {\displaystyle D=P^{2}-4Q}
a = P + D 2 and b = P − D 2 . {\displaystyle a={\frac {P+{\sqrt {D}}}{2}}\quad {\text{and}}\quad b={\frac {P-{\sqrt {D}}}{2}}.\,} इस प्रकार:
a + b = P , {\displaystyle a+b=P\,,} a b = 1 4 ( P 2 − D ) = Q , {\displaystyle ab={\frac {1}{4}}(P^{2}-D)=Q\,,} a − b = D . {\displaystyle a-b={\sqrt {D}}\,.} ध्यान दें कि क्रम a n {\displaystyle a^{n}} b n {\displaystyle b^{n}}
विशिष्ट मूल जब D ≠ 0 {\displaystyle D\neq 0} a और b भिन्न-भिन्न होता हैं और कोई भी इसे शीघ्रता से सत्यापित कर सकता है
a n = V n + U n D 2 {\displaystyle a^{n}={\frac {V_{n}+U_{n}{\sqrt {D}}}{2}}} b n = V n − U n D 2 . {\displaystyle b^{n}={\frac {V_{n}-U_{n}{\sqrt {D}}}{2}}.} इससे यह पता चलता है कि लुकास अनुक्रमों की स्थितियों को a और b के संदर्भ में निम्नानुसार व्यक्त किया जा सकता है
U n = a n − b n a − b = a n − b n D {\displaystyle U_{n}={\frac {a^{n}-b^{n}}{a-b}}={\frac {a^{n}-b^{n}}{\sqrt {D}}}} V n = a n + b n {\displaystyle V_{n}=a^{n}+b^{n}\,} पुनरावर्तित मूल स्थिति D = 0 {\displaystyle D=0} P = 2 S औ र Q = S 2 {\displaystyle P=2S{\text{ औ र }}Q=S^{2}} a = b = S {\displaystyle a=b=S}
U n ( P , Q ) = U n ( 2 S , S 2 ) = n S n − 1 {\displaystyle U_{n}(P,Q)=U_{n}(2S,S^{2})=nS^{n-1}\,} V n ( P , Q ) = V n ( 2 S , S 2 ) = 2 S n . {\displaystyle V_{n}(P,Q)=V_{n}(2S,S^{2})=2S^{n}.\,} गुण कार्य उत्पन्न करना सामान्य जनरेटिंग फलन निम्न प्रकार होता हैं
∑ n ≥ 0 U n ( P , Q ) z n = z 1 − P z + Q z 2 ; {\displaystyle \sum _{n\geq 0}U_{n}(P,Q)z^{n}={\frac {z}{1-Pz+Qz^{2}}};} ∑ n ≥ 0 V n ( P , Q ) z n = 2 − P z 1 − P z + Q z 2 . {\displaystyle \sum _{n\geq 0}V_{n}(P,Q)z^{n}={\frac {2-Pz}{1-Pz+Qz^{2}}}.} पेल समीकरण कब Q = ± 1 {\displaystyle Q=\pm 1} U n ( P , Q ) {\displaystyle U_{n}(P,Q)} V n ( P , Q ) {\displaystyle V_{n}(P,Q)} पेल समीकरण को सरल करें:
V n ( P , 1 ) 2 − D ⋅ U n ( P , 1 ) 2 = 4 , {\displaystyle V_{n}(P,1)^{2}-D\cdot U_{n}(P,1)^{2}=4,} V 2 n ( P , − 1 ) 2 − D ⋅ U 2 n ( P , − 1 ) 2 = 4 , {\displaystyle V_{2n}(P,-1)^{2}-D\cdot U_{2n}(P,-1)^{2}=4,} V 2 n + 1 ( P , − 1 ) 2 − D ⋅ U 2 n + 1 ( P , − 1 ) 2 = − 4. {\displaystyle V_{2n+1}(P,-1)^{2}-D\cdot U_{2n+1}(P,-1)^{2}=-4.} विभिन्न मापदंडों के साथ अनुक्रमों के मध्य संबंध किसी भी संख्या c के लिए, अनुक्रम U n ( P ′ , Q ′ ) {\displaystyle U_{n}(P',Q')} V n ( P ′ , Q ′ ) {\displaystyle V_{n}(P',Q')} P ′ = P + 2 c {\displaystyle P'=P+2c} Q ′ = c P + Q + c 2 {\displaystyle Q'=cP+Q+c^{2}} के समान विभेदक U n ( P , Q ) {\displaystyle U_{n}(P,Q)} V n ( P , Q ) {\displaystyle V_{n}(P,Q)} P ′ 2 − 4 Q ′ = ( P + 2 c ) 2 − 4 ( c P + Q + c 2 ) = P 2 − 4 Q = D . {\displaystyle P'^{2}-4Q'=(P+2c)^{2}-4(cP+Q+c^{2})=P^{2}-4Q=D.} किसी भी संख्या c के लिए, हमारे पास भी निम्न समीकरण होता है U n ( c P , c 2 Q ) = c n − 1 ⋅ U n ( P , Q ) , {\displaystyle U_{n}(cP,c^{2}Q)=c^{n-1}\cdot U_{n}(P,Q),} V n ( c P , c 2 Q ) = c n ⋅ V n ( P , Q ) . {\displaystyle V_{n}(cP,c^{2}Q)=c^{n}\cdot V_{n}(P,Q).} अन्य संबंध लुकास अनुक्रमों की स्थिति उन संबंधों को सरल करती हैं जो फाइबोनैचि संख्याओं के मध्य F n = U n ( 1 , − 1 ) {\displaystyle F_{n}=U_{n}(1,-1)} L n = V n ( 1 , − 1 ) {\displaystyle L_{n}=V_{n}(1,-1)}
General case ( P , Q ) = ( 1 , − 1 ) ( P 2 − 4 Q ) U n = V n + 1 − Q V n − 1 = 2 V n + 1 − P V n 5 F n = L n + 1 + L n − 1 = 2 L n + 1 − L n V n = U n + 1 − Q U n − 1 = 2 U n + 1 − P U n L n = F n + 1 + F n − 1 = 2 F n + 1 − F n U 2 n = U n V n F 2 n = F n L n V 2 n = V n 2 − 2 Q n L 2 n = L n 2 − 2 ( − 1 ) n U m + n = U n U m + 1 − Q U m U n − विभाज्यता गुण परिणामों में सम्मिलित U k m ( P , Q ) {\displaystyle U_{km}(P,Q)} U m ( P , Q ) {\displaystyle U_{m}(P,Q)} ( U m ( P , Q ) ) m ≥ 1 {\displaystyle (U_{m}(P,Q))_{m\geq 1}} विभाज्यता क्रम होता है। इसका तात्पर्य, विशेष रूप से, जब U n ( P , Q ) {\displaystyle U_{n}(P,Q)} अभाज्य संख्या हो सकती है जब n अभाज्य हो। इस प्रकार अन्य परिणाम वर्ग द्वारा घातांक का अनुरूप होता है जो शीघ्रता से गणना की अनुमति देता है जों U n ( P , Q ) {\displaystyle U_{n}(P,Q)} gcd ( P , Q ) = 1 {\displaystyle \gcd(P,Q)=1} ( U m ( P , Q ) ) m ≥ 1 {\displaystyle (U_{m}(P,Q))_{m\geq 1}}
अन्य विभाज्यता गुण इस प्रकार हैं:[1]
अगर n ∣ m {\displaystyle n\mid m} V m {\displaystyle V_{m}} V n {\displaystyle V_{n}}
मान लीजिए N, 2Q के सापेक्ष अभाज्य पूर्णांक है। यदि सबसे छोटा धनात्मक पूर्णांक r जिसके लिए N विभाजित होता है U r {\displaystyle U_{r}} U n {\displaystyle U_{n}}
यदि P और Q समता (गणित) हैं, तो U n , V n {\displaystyle U_{n},V_{n}} U 1 {\displaystyle U_{1}}
यदि P सम है और Q विषम है, तो समता (गणित) की U n {\displaystyle U_{n}} V n {\displaystyle V_{n}}
यदि P विषम है और Q सम है, तो U n , V n {\displaystyle U_{n},V_{n}} n = 1 , 2 , … {\displaystyle n=1,2,\ldots }
यदि P और Q विषम हैं, तो U n , V n {\displaystyle U_{n},V_{n}}
यदि p विषम अभाज्य है, तो U p ≡ ( D p ) , V p ≡ P ( mod p ) {\displaystyle U_{p}\equiv \left({\tfrac {D}{p}}\right),V_{p}\equiv P{\pmod {p}}}
यदि p विषम अभाज्य है और P और Q को विभाजित करता है, तो p प्रत्येक n > 1 {\displaystyle n>1} U n {\displaystyle U_{n}}
यदि p विषम अभाज्य है और P को विभाजित करता है लेकिन Q को नहीं, तो p U n {\displaystyle U_{n}}
यदि p विषम अभाज्य है और P को नहीं जबकि Q को विभाजित करता है, तो p कभी भी n = 1 , 2 , … {\displaystyle n=1,2,\ldots } U n {\displaystyle U_{n}}
यदि p विषम अभाज्य है और PQ को नहीं बल्कि D को विभाजित करता है, तो p विभाजित होता है U n {\displaystyle U_{n}}
यदि p विषम अभाज्य है और PQD को विभाजित नहीं करता है, तो p U l {\displaystyle U_{l}} l = p − ( D p ) {\displaystyle l=p-\left({\tfrac {D}{p}}\right)} अंतिम तथ्य फ़र्मेट के छोटे प्रमेय का सामान्यीकरण करता है। इन तथ्यों का उपयोग लुकास-लेहमर अभाज्यलिटी परीक्षण में किया जाता है। अंतिम तथ्य का व्युत्क्रम (तर्क) मान्य नहीं होता है, जैसे फ़र्मेट के छोटे प्रमेय का व्युत्क्रम मान्य नहीं होता है। D और U l {\displaystyle U_{l}} l = n − ( D n ) {\displaystyle l=n-\left({\tfrac {D}{n}}\right)} लुकास स्यूडोअभाज्य कहा जाता है।
लुकास अनुक्रम में किसी पद का अभाज्य कारक जो अनुक्रम में किसी भी पहले के पद को विभाजित नहीं करता है उसे प्राथमिक कहा जाता है। कारमाइकल के प्रमेय में कहा गया है कि लुकास अनुक्रम में सभी लेकिन सीमित रूप से कई शब्दों में प्राथमिक अभाज्य कारक होता है।[2] D धनात्मक होता है और n 1, 2 या 6 नहीं होता है, तो U n {\displaystyle U_{n}} D नकारात्मक स्थितियों में, बिलु, हनरोट, वाउटियर और मिग्नोटे का अत्यंत परिणाम होता है[3] U n {\displaystyle U_{n}} U n {\displaystyle U_{n}}
विशिष्ट नाम P और Q के कुछ मानों के लिए लुकास अनुक्रमों के विशिष्ट नाम हैं:
Un (1, −1)Vn (1, −1)Un (2, −1)Vn (2, −1)Un (1, −2)Vn (1, −2)Un (3, 2)n − 1Vn (3, 2)n + 1, जिसमें फ़र्मेट संख्याएँ सम्मिलित होती हैं[2] Un (6, 1)वर्ग त्रिकोणीय संख्या ओं का वर्गमूल।Un (x , −1)फाइबोनैचि बहुपद Vn (x , −1)लुकास बहुपद Un (2x , 1)चेबीशेव बहुपद Vn (2x , 1)Un (x +1, x )Vn (x +1, x )xn + 1कुछ लुकास अनुक्रमों की पूर्णांक अनुक्रमों के ऑन-लाइन विश्वकोश में प्रविष्टियाँ निम्न प्रकार हैं:
अनुप्रयोग लुकास अनुक्रमों का उपयोग संभाव्य लुकास स्यूडोअभाज्य परीक्षणों में किया जाता है, जो सामान्यतः प्रयोग किए जाने वाले बैली-पीएसडब्ल्यू प्रारंभिक परीक्षण का भाग होता हैं।
लुकास अनुक्रमों का उपयोग कुछ प्रारंभिक प्रमाण विधियों में किया जाता है, जिनमें लुकास-लेहमर-रीज़ल परीक्षण, और N+1और संकर N−1/N+1 विधियां जैसे ब्रिलहार्ट-लेहमर-सेल्फ्रिज 1975 सम्मिलित होता हैं।[4]
एलयूसी लुकास अनुक्रमों पर आधारित सार्वजनिक-कुंजी क्रिप्टोप्रणाली है[5] एलगमाल (LUCELG), डिफी-हेलमैन (LUCDIF), और RSA (कलन विधि) (LUCRSA) के एनालॉग्स को प्रयुक्त करता है। एलयूसी में संदेश के कूटलेखन की गणना आरएसए या डिफी-हेलमैन जैसे मॉड्यूलर घातांक का उपयोग करने के अतिरिक्त, कुछ लुकास अनुक्रम के शब्द के रूप में की जाती है। यघपि, ब्लेइचेनबैकर एट अल द्वारा पेपर [6] यह भी देखें टिप्पणियाँ
संदर्भ Carmichael, R. D. (1913), "On the numerical factors of the arithmetic forms αn n Annals of Mathematics , 15 (1/4): 30–70, doi :10.2307/1967797 , JSTOR 1967797 Lehmer, D. H. (1930). "An extended theory of Lucas' functions". Annals of Mathematics . 31 (3): 419–448. Bibcode :1930AnMat..31..419L . doi :10.2307/1968235 . JSTOR 1968235 . Ward, Morgan (1954). "Prime divisors of second order recurring sequences". Duke Math. J . 21 (4): 607–614. doi :10.1215/S0012-7094-54-02163-8 . hdl :10338.dmlcz/137477 MR 0064073 . Somer, Lawrence (1980). "The divisibility properties of primary Lucas Recurrences with respect to primes" (PDF) . Fibonacci Quarterly . 18 : 316. Lagarias, J. C. (1985). "The set of primes dividing Lucas Numbers has density 2/3". Pac. J. Math . 118 (2): 449–461. doi :10.2140/pjm.1985.118.449 . MR 0789184 . Hans Riesel (1994). Prime Numbers and Computer Methods for Factorization . Progress in Mathematics. Vol. 126 (2nd ed.). Birkhäuser. pp. 107–121. ISBN 0-8176-3743-5 Ribenboim, Paulo; McDaniel, Wayne L. (1996). "The square terms in Lucas Sequences" . J. Number Theory . 58 (1): 104–123. doi :10.1006/jnth.1996.0068 Joye, M.; Quisquater, J.-J. (1996). "Efficient computation of full Lucas sequences" (PDF) . Electronics Letters . 32 (6): 537–538. Bibcode :1996ElL....32..537J . doi :10.1049/el:19960359 . Archived from the original (PDF) on 2015-02-02. Ribenboim, Paulo (1996). The New Book of Prime Number Records (eBook ed.). Springer-Verlag , New York. doi :10.1007/978-1-4612-0759-7 . ISBN 978-1-4612-0759-7 Ribenboim, Paulo (2000). My Numbers, My Friends: Popular Lectures on Number Theory . New York: Springer-Verlag . pp. 1–50. ISBN 0-387-98911-0 Luca, Florian (2000). "Perfect Fibonacci and Lucas numbers". Rend. Circ Matem. Palermo . 49 (2): 313–318. doi :10.1007/BF02904236 . S2CID 121789033 . Yabuta, M. (2001). "A simple proof of Carmichael's theorem on primitive divisors" (PDF) . Fibonacci Quarterly . 39 : 439–443. Benjamin, Arthur T. ; Quinn, Jennifer J. (2003). Proofs that Really Count: The Art of Combinatorial Proof Mathematical Association of America . p. 35 . ISBN 978-0-88385-333-7 Lucas sequence Encyclopedia of Mathematics .Weisstein, Eric W. "Lucas Sequence" . MathWorld Wei Dai . "Lucas Sequences in Cryptography" .