1.7: Teorema de Lame
- Page ID
- 115041
En esta sección, damos una estimación del número de pasos necesarios para encontrar el mayor divisor común de dos enteros usando el algoritmo euclidiano. Para ello, tenemos que introducir los números de Fibonacci con el fin de probar un lema que dé una estimación sobre el crecimiento de los números de Fibonacci en la secuencia de Fibonacci. El lema que probemos será utilizado en la prueba del teorema de Lame.
La secuencia de Fibonacci se define recursivamente por\(f_1=1\),\(f_2=1\), y\[f_{n}=f_{n-1}+f_{n-2} \mbox{for} \ \ n\geq 3.\] Los términos en la secuencia se denominan números de Fibonacci.
En el siguiente lema, damos un límite inferior sobre el crecimiento de los números de Fibonacci. Mostraremos que los números de Fibonacci crecen más rápido que una serie geométrica con relación común\(\alpha=(1+\sqrt{5})/2\).
[lem2] Porque\(n\geq 3\), tenemos\(f_n>\alpha^{n-2}\) donde\(\alpha=(1+\sqrt{5})/2\).
Utilizamos el segundo principio de inducción matemática para probar nuestro resultado. Es fácil ver que esto es cierto para\(n=3\) y\(n=4\). Supongamos que\(\alpha^{k-2}<f_k\) para todos los enteros\(k\) donde\(k\leq n\). Ahora como\(\alpha\) es una solución del polinomio\(x^2-x-1=0\), tenemos\(\alpha^2=\alpha+1\). De ahí\[\alpha^{n-1}=\alpha^2.\alpha^{n-3}=(\alpha+1).\alpha^{n-3}=\alpha^{n-2}+\alpha^{n-3}.\] por la hipótesis inductiva, tenemos\[\alpha^{n-2}<f_n, \ \ \ \alpha^{n-3}<f_{n-1}.\] Después de sumar las dos desigualdades, obtenemos\[\alpha^{n-1}<f_{n}+f_{n-1}=f_{n+1}.\]
Presentamos ahora el teorema de Lame.
usando el algoritmo euclidiano para encontrar el mayor divisor común de dos enteros positivos tiene número de divisiones menor o igual cinco veces el número de dígitos decimales en el mínimo de los dos enteros.
Dejar\(a\) y\(b\) ser dos enteros positivos donde\(a>b\). Aplicando el algoritmo euclidiano para encontrar el mayor divisor común de dos enteros con\(a=r_0\) y\(b=r_1\), obtenemos\[\begin{aligned} r_0&=&r_1q_1+r_2 \ \ \ \ \ 0\leq r_2<r_1, \\ r_1&=&r_2q_2+r_3 \ \ \ \ \ 0\leq r_3<r_2, \\ &.& \\ &.& \\ &.& \\ r_{n-2}&=&r_{n-1}q_{n-1}+r_{n} \ \ \ \ \ 0\leq r_{n}<r_{n-1}, \\ r_{n-1}&=&r_{n}q_{n}.\end{aligned}\] Observe que cada uno de los cocientes\(q_1,q_2,...,q_{n-1}\) son todos mayores que 1 y\(q_n\geq 2\) y esto es porque\(r_n<r_{n-1}\). Así tenemos\[\begin{aligned} r_n&\geq& 1=f_2,\\ r_{n-1}&\geq& 2r_n\geq 2f_2=f_3,\\ r_{n-2}&\geq& r_{n-1}+r_n\geq f_3+f_2=f_4,\\ r_{n-3}&\geq& r_{n-2}+r_{n-1}\geq f_4+f_3=f_5,\\ &.&\\ &.&\\ &.&\\ r_2&\geq& r_3+r_4\geq f_{n-1}+f_{n-2}=f_n,\\ b&=& r_1\geq r_2+r_3\geq f_n+f_{n-1}=f_{n+1}.\end{aligned}\] Así notamos eso\(b\geq f_{n+1}\). Por Lemma [lem2], tenemos\(f_{n+1}>\alpha^{n-1}\) para\(n>2\). Como resultado, tenemos\(b>\alpha^{n-1}\). Ahora\[\log_{10}\alpha>\frac{1}{5},\] fíjense ya que vemos que\[log_{10}b>(n-1)/5.\] Así tenemos\[n-1<5log_{10}b.\] Ahora vamos\(b\) tiene dígitos\(k\) decimales. Como resultado, tenemos\(b<10^k\) y así\(log_{10}b<k\). De ahí que concluyamos eso\(n-1<5k\). Dado que\(k\) es un entero, concluimos que\(n\leq 5k\).
Ejercicios
- Encuentra un límite superior para el número de pasos en el algoritmo euclidiano que se utiliza para encontrar el divisor más común de 38472 y 957748838.
- Encuentra un límite superior para el número de pasos en el algoritmo euclidiano que se utiliza para encontrar el divisor más común de 15 y 75. Verifica tu resultado usando el algoritmo euclidiano para encontrar el divisor más común de los dos enteros.