Demuestre que el número de pasos en el algoritmo euclidiano es menor que$\frac{2\log b}{\log 2}$

Question

¿Alguien podría decirme cómo probar esta afirmación? El número de pasos en el algoritmo euclidiano es menor que$\frac{2\log b}{\log 2}$, donde$b$ es el mayor de los dos números cuyo GCD se está encontrando.

Answer 1

¿Puede mostrar que cada vez que hace 2 pasos del algoritmo, ha reducido el número más grande que aparece al menos en un factor de 2?

Answer 2

Primera nota de que $\frac{\log b}{\log 2} = \log_2 b$, por lo que en realidad estamos tratando de demostrar que el número de pasos es de menos de $2\log_2 b$. De hecho, el número de pasos es en la mayoría de las $\log_2 a+\log_2 b$ donde $a$ es el número más pequeño, y es tan fácil de probar este resultado más fuerte. De ello se desprende del hecho de que en cada paso del algoritmo de Euclides, el producto de los dos números actuales gotas por un factor de más de $2$. Es decir, si $b=aq+r$ donde$0\le r<a$,$ar$, producto de la nueva pareja de números, está a menos de $\frac12 ab$. Para completar la prueba, es necesario hacer dos cosas:

1. Demostrar el hecho de que acabo de explicar.
2. Demostrar que implica que el algoritmo de Euclides se lleva en la mayoría de las $\log_2 a+\log_2 b$ pasos para encontrar $\gcd(a,b)$.

Ningún argumento es terriblemente difícil.