¿Por qué el algoritmo de Euclides terminar siempre?

Question

¿Por qué el algoritmo de Euclides terminar siempre? Podemos hacer esto efectivo por la delimitación de la número de pasos que da en términos de la original enteros?

Answer 1

Siempre termina porque a cada paso que uno de los dos argumentos a $\gcd({}\mathbin\cdot{},{}\mathbin\cdot{})$ hace más pequeño, y en el paso siguiente, el otro se hace más pequeño. Usted no puede seguir recibiendo más pequeños enteros positivos para siempre; que es el "bien de pedido" de los números naturales. Mientras ninguno de los dos argumentos es $0$ usted puede tomar un paso más, pero no puede continuar para siempre, así que tienes que llegar a un punto en donde uno de ellos es $0$, y luego se detiene.

Como para agigantados, muy crudo y fácilmente establecido límite superior en el número de pasos es la suma de los dos argumentos. Uno de los argumentos es reducido por lo menos $1$ a cada paso, y no se puede reducir a $n$ repetidamente por $1$ más de $n$ veces sin someterlo a $0$.

El peor de los casos es $\gcd(m,n)$ cuando la relación de $m$ $n$es el cociente de dos números de Fibonacci consecutivos. Por ahora les dejo la prueba de que, como un ejercicio.

Answer 2

Este es un caso de "descenso infinito".

Una iteración del algoritmo que transforma un par de $(a,b)$ $a>b\ge0$ en otro par $(a',b')$$a'>b'\ge0$, y también se $a'<a$ ( $a'\le a$ ). Así que inevitablemente transformar un problema en otro problema del mismo tipo con menor argumentos, y se llega a la $0$ después de un número finito de pasos.

Para una discusión sobre el número de pasos, ver https://en.wikipedia.org/wiki/Euclidean_algorithm#Number_of_steps.

Answer 3

Sí, hay un límite. Se utiliza en matemáticas computacionales. Si $a$ $b$ son enteros ($a\ge b\ge1$) y la distancia euclídea alg. se requiere $n+1$ operaciones, a continuación, usted tiene $n+1 \lt 5\log_{10}b$. Además, el algoritmo debe terminar en un número finito de pasos, porque en cada paso que tiene un resto que es estrictamente menor que la de su predecesor. Así que, si no terminan, a continuación, el conjunto de todos los restos que no tienen el mínimo elemento, pero este es un absurdum.(Estamos en $\mathbb N$).

Answer 4

Si usted toma dos pasos en el algoritmo de Euclides, se han reducido a la mitad el tamaño del mayor número.

$$\begin{align} a,b &\to b, c \;(\equiv a \bmod b)\\[3ex] b\le a/2 &\implies c<b \le a/2 \\ b>a/2 &\implies c=a-b < a/2\\[3ex] b,c &\to c,d\;(<c) \quad\square \end{align}$$

Así, el proceso termina en la mayoría de los $2\log_2 a$ pasos.

Answer 5

Considere el siguiente invariante del algoritmo: tome $|a|+|b|$. Suponga $a>b$. El algoritmo se puede definir como sigue: reemplace $(a,b)$ $(a-b,b)$ si $a-b>b$ $(b,a-b)$ si $a-b\leq b$. Cuando uno de los elementos es cero, volver el otro elemento. En este procedimiento $|a|+|b|$ siempre se hace más pequeño, pero tiene un mínimo de $1$. Así se termina