Ciertas secuencias de números enteros recursivos constantes
En matemáticas , las sucesiones de Lucas y son ciertas sucesiones de números enteros recursivos constantes que satisfacen la relación de recurrencia.
donde y son números enteros fijos . Cualquier secuencia que satisfaga esta relación de recurrencia puede representarse como una combinación lineal de las secuencias de Lucas y
De manera más general, las secuencias de Lucas y representan secuencias de polinomios en y con coeficientes enteros .
Entre los ejemplos famosos de secuencias de Lucas se incluyen los números de Fibonacci , los números de Mersenne , los números de Pell , los números de Lucas , los números de Jacobsthal y un superconjunto de números de Fermat (véase más abajo). Las secuencias de Lucas reciben su nombre del matemático francés Édouard Lucas .
Relaciones de recurrencia
Dados dos parámetros enteros y , las secuencias de Lucas del primer tipo y del segundo tipo se definen mediante las relaciones de recurrencia :
y
No es difícil demostrar que para ,
Las relaciones anteriores se pueden expresar en forma matricial de la siguiente manera:
Ejemplos
Los términos iniciales de las sucesiones de Lucas y se dan en la tabla:
Expresiones explícitas
La ecuación característica de la relación de recurrencia para las secuencias de Lucas y es:
Tiene el discriminante y las raíces :
De este modo:
Tenga en cuenta que la secuencia y la secuencia también satisfacen la relación de recurrencia. Sin embargo, es posible que no sean secuencias enteras.
Raíces distintas
Cuando a y b son distintos y uno verifica rápidamente que
De ello se deduce que los términos de las sucesiones de Lucas se pueden expresar en términos de a y b de la siguiente manera
Raíz repetida
El caso ocurre exactamente cuando para algún entero S tal que . En este caso uno encuentra fácilmente que
Propiedades
Funciones generadoras
Las funciones generadoras ordinarias son
Ecuaciones de Pell
Cuando las secuencias de Lucas y satisfacen ciertas ecuaciones de Pell :
Relaciones entre secuencias con diferentes parámetros
- Para cualquier número c , las sucesiones y con
- tienen el mismo discriminante que y :
- Para cualquier número c , también tenemos
Otras relaciones
Los términos de las sucesiones de Lucas satisfacen relaciones que son generalizaciones de las existentes entre los números de Fibonacci y los números de Lucas . Por ejemplo:
Propiedades de divisibilidad
Entre las consecuencias está que es un múltiplo de , es decir, la sucesión
es una sucesión de divisibilidad . Esto implica, en particular, que puede ser primo solo cuando n es primo. Otra consecuencia es un análogo de la exponenciación por cuadrado que permite el cálculo rápido de para valores grandes de n . Además, si , entonces es una sucesión de divisibilidad fuerte .
Otras propiedades de divisibilidad son las siguientes: [1]
- Si es impar , entonces divide .
- Sea N un entero primo relativo a 2 Q . Si existe el entero positivo más pequeño r para el cual N es divisor , entonces el conjunto de n para el cual N es divisor es 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 de es la misma que n y siempre es par.
- Si P es impar y Q es par, entonces siempre son impares para .
- Si P y Q son impares, entonces son pares si y sólo si n es un múltiplo de 3.
- Si p es un número 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 divide si y sólo si n es par.
- Si p es un primo impar y no divide a P sino a Q , entonces p nunca divide a Q.
- Si p es un primo impar y no divide a PQ sino a D , entonces p divide si y sólo si p divide a n .
- Si p es un primo impar y no divide a PQD , entonces p divide a , donde .
El último hecho generaliza el pequeño teorema de Fermat . Estos hechos se utilizan en la prueba de primalidad de Lucas-Lehmer . El inverso del último hecho no se cumple, como tampoco se cumple el inverso del pequeño teorema de Fermat. Existe un compuesto n primo relativo con D y que divide a , donde . Tal compuesto se llama pseudoprimo de Lucas .
Un factor primo de un término en una secuencia de Lucas que no divide a 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, excepto un número finito, tienen un factor primo primitivo. [2] De hecho, Carmichael (1913) demostró que si D es positivo y n no es 1, 2 o 6, entonces tiene 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 que todos los casos no tienen ningún 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 de Pell–Lucas (números de 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 ) : Reuniones en 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 :
Aplicaciones
- Las secuencias de Lucas se utilizan en pruebas pseudoprimas probabilísticas de Lucas , que son 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 la exponenciación modular no están presentes o no son tan sustanciales como se afirma.
Software
Sagemath implementa y como y , respectivamente. [7]lucas_number1()
lucas_number2()
Véase también
Notas
- ^ Para tales relaciones y propiedades de divisibilidad, véase (Carmichael 1913), (Lehmer 1930) o (Ribenboim 1996, 2.IV).
- ^ ab Yabuta, M (2001). "Una prueba simple del teorema de Carmichael sobre divisores primitivos" (PDF) . Fibonacci Quarterly . 39 (5): 439–443. doi :10.1080/00150517.2001.12428701 . Consultado el 4 de octubre de 2018 .
- ^ Bilu, Yuri; Hanrot, Guillaume; Voutier, Paul M.; Mignotte, Maurice (2001). "Existencia de divisores primitivos de los números de Lucas y Lehmer" (PDF) . J. Reine Angew. Matemáticas . 2001 (539): 75–122. doi :10.1515/crll.2001.080. MR 1863855. S2CID 122969549.
- ^ John Brillhart ; Derrick Henry Lehmer ; John Selfridge (abril de 1975). "Nuevos criterios de primalidad y factorizaciones de 2m ± 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 Simposio Internacional sobre Seguridad Informática de la IFIP : 103–117. CiteSeerX 10.1.1.32.1835 .
- ^ D. Bleichenbacher; W. Bosma; AK Lenstra (1995). "Algunas observaciones sobre criptosistemas basados en Lucas" (PDF) . Avances en criptología — CRYPT0' 95. Apuntes de clase en informática. Vol. 963. págs. 386–396. doi : 10.1007/3-540-44750-4_31 . ISBN. 978-3-540-60221-7.
- ^ "Funciones combinatorias - Combinatoria". doc.sagemath.org . Consultado el 13 de julio de 2023 .
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 extendida de las funciones de Lucas". Anales de Matemáticas . 31 (3): 419–448. Bibcode :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 . MR 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 (4): 316–334. doi :10.1080/00150517.1980.12430140.
- Lagarias, JC (1985). "El conjunto de primos que dividen números de Lucas tiene densidad 2/3". Pac. J. Math . 118 (2): 449–461. CiteSeerX 10.1.1.174.660 . doi :10.2140/pjm.1985.118.449. MR 0789184.
- Hans Riesel (1994). Números primos y métodos informáticos para la factorización . Progreso en matemáticas. Vol. 126 (2.ª ed.). Birkhäuser. pp. 107–121. ISBN. 0-8176-3743-5.
- Ribenboim, Paulo; McDaniel, Wayne L. (1996). "Los términos cuadrados en secuencias de Lucas". J. Number Theory . 58 (1): 104–123. doi : 10.1006/jnth.1996.0068 .
- Joye, M.; Quisquater, J.-J. (1996). "Cálculo eficiente de secuencias Lucas completas" (PDF) . Electronics Letters . 32 (6): 537–538. Bibcode :1996ElL....32..537J. doi :10.1049/el:19960359. Archivado desde el original (PDF) el 2 de febrero de 2015.
- Ribenboim, Paulo (1996). El nuevo libro de registros de números primos (edición en formato electrónico). 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 . pp. 1–50. ISBN. 0-387-98911-0.
- Luca, Florian (2000). "Números perfectos de Fibonacci y Lucas". Rend. 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 (5): 439–443. doi :10.1080/00150517.2001.12428701.
- Benjamin, Arthur T. ; Quinn, Jennifer J. (2003). Pruebas que realmente cuentan: el arte de la prueba combinatoria . Dolciani Mathematical Expositions. Vol. 27. Asociación Matemática de América . p. 35. ISBN 978-0-88385-333-7.
- Sucesión de Lucas en Enciclopedia de Matemáticas .
- Weisstein, Eric W. "Secuencia de Lucas". MundoMatemático .
- Wei Dai . "Secuencias de Lucas en criptografía".