En matemáticas , las secuencias de Lucas y son ciertas secuencias enteras constantes-recursivas que satisfacen la relación de recurrencia
dónde y son enteros fijos. Cualquier secuencia que satisfaga esta relación de recurrencia se puede representar como una combinación lineal de las secuencias de Lucas. y .
De manera más general, las secuencias de Lucas y representar secuencias de polinomios en y con coeficientes enteros.
Ejemplos famosos de secuencias de Lucas incluyen los números de Fibonacci , números de Mersenne , números de Pell , números de Lucas , números Jacobsthal , y un superconjunto de números de Fermat . Las secuencias de Lucas llevan el nombre del matemático francés Édouard Lucas .
Relaciones de recurrencia
Dados dos parámetros enteros P y Q , las secuencias de Lucas del primer tipo U n ( P , Q ) y del segundo tipo V n ( P , Q ) están definidas por las relaciones de recurrencia :
y
No es difícil demostrar que para ,
Ejemplos de
Los términos iniciales de las secuencias de Lucas U n ( P , Q ) y V n ( P , Q ) se dan en la tabla:
Expresiones explícitas
La ecuación característica de la relación de recurrencia para secuencias de Lucas y es:
Tiene el discriminante y las raíces:
Por lo tanto:
Tenga en cuenta que la secuencia y la secuencia también satisfacen la relación de recurrencia. Sin embargo, es posible que estas no sean secuencias enteras.
Raíces distintas
Cuándo , Un y b son verifica distintos y uno rápidamente que
- .
De ello se desprende que los términos de secuencias de Lucas se pueden expresar en términos de una y b de la siguiente
Raíz repetida
El caso ocurre exactamente cuando para algún entero S de modo que. En este caso uno encuentra fácilmente que
- .
Propiedades
Funciones generadoras
Las funciones generadoras ordinarias son
Secuencias con el mismo discriminante
Si las secuencias de Lucas y tener discriminante , luego las secuencias basadas en y dónde
tienen el mismo discriminante: .
Ecuaciones de Pell
Cuándo , las secuencias de Lucas y satisfacen ciertas ecuaciones de Pell :
Otras relaciones
Los términos de las secuencias de Lucas satisfacen relaciones que son generalizaciones de aquellas entre números de Fibonacci y números de Lucas . Por ejemplo:
Entre las consecuencias está que es un múltiplo de , es decir, la secuencia es una secuencia de divisibilidad . Esto implica, en particular, quesolo puede ser primo cuando n es primo. Otra consecuencia es un análogo de exponenciación por cuadratura que permite el cálculo rápido depara valores grandes de n . Además, si, luego es una secuencia de divisibilidad fuerte.
Otras propiedades de divisibilidad son las siguientes: [1]
- Si n / m es impar, entonces divide .
- Deje que N sea un número entero primo con 2 Q . Si el menor entero positivo r por el que N se divideexiste, entonces el conjunto de n para el que N se dividees exactamente el conjunto de múltiplos de r .
- Si P y Q son pares, entonces son siempre pares excepto .
- Si P es par y Q es impar, entonces la paridad dees el mismo que n y es siempre parejo.
- Si P es impar y Q es par, entonces siempre son extraños para .
- Si P y Q son impares, entoncesson incluso si y solo si n es un múltiplo de 3.
- Si p es un primo impar, entonces(ver símbolo de Legendre ).
- Si p es un primo impar y divide a P y Q , entonces p divide para cada .
- Si p es un primo impar y divide a P pero no a Q , entonces p dividesi y solo si n es par.
- Si p es un primo impar y no divide a P sino a Q , entonces p nunca divide por .
- Si p es un primo impar y no divide a PQ sino a D , entonces p dividesi y solo si p divide a n .
- Si p es un primo impar y no divide PQD , entonces p divide, dónde .
El último hecho generaliza el pequeño teorema de Fermat . Estos hechos se utilizan en la prueba de primalidad de Lucas-Lehmer . Lo contrario del último hecho no se cumple, como tampoco lo es el inverso del pequeño teorema de Fermat. Existe un compuesto n relativamente primo a D y que divide, dónde . Tal compuesto se llama pseudoprime de Lucas .
Un factor primo de un término en una secuencia de Lucas que no divide ningún término anterior en la secuencia se llama primitivo . El teorema de Carmichael establece que todos los términos de una secuencia de Lucas, salvo un número finito, tienen un factor primo primitivo . [2] De hecho, Carmichael (1913) mostró que si D es positivo yn no es 1, 2 o 6, entoncestiene un factor primo primitivo. En el caso de que D sea negativo, un resultado profundo de Bilu, Hanrot, Voutier y Mignotte [3] muestra que si n > 30, entonces tiene un factor primo primitivo y determina todos los casos no tiene factor primo primitivo.
Nombres específicos
Las secuencias de Lucas para algunos valores de P y Q tienen nombres específicos:
- U n (1, −1) : números de Fibonacci
- V n (1, −1) : números de Lucas
- U n (2, −1) : números de Pell
- V n (2, −1) : números Pell – Lucas (números Pell complementarios)
- U n (1, −2) : números de Jacobsthal
- V n (1, −2) : números de Jacobsthal – Lucas
- U n (3, 2) : números de Mersenne 2 n - 1
- V n (3, 2) : Números de la forma 2 n + 1, que incluyen los números de Fermat [2]
- U n (6, 1) : Las raíces cuadradas de los números triangulares cuadrados .
- U n ( x , −1) : polinomios de Fibonacci
- V n ( x , −1) : polinomios de Lucas
- U n (2 x , 1) : polinomios de Chebyshev de segundo tipo
- V n (2 x , 1) : polinomios de Chebyshev de primer tipo multiplicados por 2
- U n ( x +1, x ) : Repunifica la base x
- V n ( x +1, x ) : x n + 1
Algunas secuencias de Lucas tienen entradas en la Enciclopedia en línea de secuencias de números enteros :
−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
Aplicaciones
- Las secuencias de Lucas se utilizan en las pruebas probabilísticas de pseudoprime de Lucas , que forman parte de la prueba de primalidad de Baillie-PSW de uso común .
- Las secuencias de Lucas se utilizan en algunos métodos de prueba de primalidad, incluida la prueba de Lucas-Lehmer-Riesel , y los métodos N + 1 e híbridos N-1 / N + 1 como los de Brillhart-Lehmer-Selfridge 1975 [4]
- LUC es un criptosistema de clave pública basado en secuencias de Lucas [5] que implementa los análogos de ElGamal (LUCELG), Diffie-Hellman (LUCDIF) y RSA (LUCRSA). El cifrado del mensaje en LUC se calcula como un término de cierta secuencia de Lucas, en lugar de utilizar la exponenciación modular como en RSA o Diffie-Hellman. Sin embargo, un artículo de Bleichenbacher et al. [6] muestra que muchas de las supuestas ventajas de seguridad de LUC sobre los criptosistemas basados en exponenciación modular no están presentes o no son tan sustanciales como se afirma.
Ver también
- Lucas pseudoprime
- Pseudoprime de Frobenius
- Pseudoprime de Somer-Lucas
Notas
- ↑ Para tales relaciones y propiedades de divisibilidad, ver ( Carmichael 1913 ), ( Lehmer 1930 ) o ( Ribenboim 1996 , 2.IV).
- ↑ a b Yabuta, M (2001). "Una prueba simple del teorema de Carmichael sobre divisores primitivos" (PDF) . Fibonacci Quarterly . 39 : 439–443 . Consultado el 4 de octubre de 2018 .
- ^ Bilu, Yuri; Hanrot, Guillaume; Voutier, Paul M .; Mignotte, Maurice (2001). "Existencia de divisores primitivos de números de Lucas y Lehmer" (PDF) . J. Reine Angew. Matemáticas . 2001 (539): 75–122. doi : 10.1515 / crll.2001.080 . Señor 1863855 .
- ^ John Brillhart ; Derrick Henry Lehmer ; John Selfridge (abril de 1975). "Nuevos Criterios de Primaria y Factorizaciones de 2 m ± 1" . Matemáticas de la Computación . 29 (130): 620–647. doi : 10.1090 / S0025-5718-1975-0384673-1 . JSTOR 2005583 .
- ^ PJ Smith; MJJ Lennon (1993). "LUC: Un nuevo sistema de clave pública". Actas del Noveno IFIP Int. Symp. Sobre seguridad informática : 103-117. CiteSeerX 10.1.1.32.1835 .
- ^ D. Bleichenbacher; W. Bosma; AK Lenstra (1995). "Algunas observaciones sobre los criptosistemas basados en Lucas" (PDF) . Apuntes de conferencias en informática . 963 : 386–396. doi : 10.1007 / 3-540-44750-4_31 . ISBN 978-3-540-60221-7.
Referencias
- Carmichael, RD (1913), "Sobre los factores numéricos de las formas aritméticas α n ± β n ", Annals of Mathematics , 15 (1/4): 30–70, doi : 10.2307 / 1967797 , JSTOR 1967797
- Lehmer, DH (1930). "Una teoría ampliada de las funciones de Lucas". Annals of Mathematics . 31 (3): 419–448. Código Bibliográfico : 1930AnMat..31..419L . doi : 10.2307 / 1968235 . JSTOR 1968235 .
- Ward, Morgan (1954). "Divisores primos de secuencias recurrentes de segundo orden". Duke Math. J . 21 (4): 607–614. doi : 10.1215 / S0012-7094-54-02163-8 . hdl : 10338.dmlcz / 137477 . Señor 0064073 .
- Somer, Lawrence (1980). "Las propiedades de divisibilidad de las recurrencias de Lucas primarias con respecto a los números primos" (PDF) . Fibonacci Quarterly . 18 : 316.
- Lagarias, JC (1985). "El conjunto de números primos que dividen los números de Lucas tiene una densidad de 2/3". Pac. J. Math . 118 (2): 449–461. doi : 10.2140 / pjm.1985.118.449 . Señor 0789184 .
- Hans Riesel (1994). Números primos y métodos informáticos de factorización . Progreso en Matemáticas. 126 (2ª ed.). Birkhäuser. págs. 107-121. ISBN 0-8176-3743-5.
- Ribenboim, Paulo; McDaniel, Wayne L. (1996). "Los términos cuadrados en las secuencias de Lucas". J. Teoría de números . 58 (1): 104-123. doi : 10.1006 / jnth.1996.0068 .
- Joye, M .; Quisquater, J.-J. (1996). "Cálculo eficiente de secuencias completas de Lucas" (PDF) . Cartas de electrónica . 32 (6): 537–538. doi : 10.1049 / el: 19960359 . Archivado desde el original (PDF) el 02/02/2015.
- Ribenboim, Paulo (1996). El nuevo libro de registros de números primos (eBook ed.). Springer-Verlag , Nueva York. doi : 10.1007 / 978-1-4612-0759-7 . ISBN 978-1-4612-0759-7.
- Ribenboim, Paulo (2000). Mis números, mis amigos: conferencias populares sobre teoría de números . Nueva York: Springer-Verlag . págs. 1-50. ISBN 0-387-98911-0.
- Luca, Florian (2000). "Números perfectos de Fibonacci y Lucas". Desgarrar. Circ Matem. Palermo . 49 (2): 313–318. doi : 10.1007 / BF02904236 . S2CID 121789033 .
- Yabuta, M. (2001). "Una prueba simple del teorema de Carmichael sobre divisores primitivos" (PDF) . Fibonacci Quarterly . 39 : 439–443.
- Benjamin, Arthur T .; Quinn, Jennifer J. (2003). Pruebas que realmente cuentan: el arte de la prueba combinatoria . Exposiciones Matemáticas Dolciani. 27 . Asociación Matemática de América . pag. 35 . ISBN 978-0-88385-333-7.
- Secuencia de Lucas en Encyclopedia of Mathematics .
- Weisstein, Eric W. "Secuencia de Lucas" . MathWorld .
- Wei Dai . "Secuencias de Lucas en criptografía" .