La clave aquí es que para la paridad de razones, siempre vamos a llegar a un 'menor' fracción en un corto, número finito de etapas. En lugar de fracciones, haré referencia a una iteración en un par de números de $f:\langle a,b\rangle \mapsto \mathop{Red}(\langle a+b,b+1\rangle)$ donde $\mathop{Red}()$ denota la reducción de $\mathop{Red}(\langle a,b\rangle) = \langle\frac{a}{\gcd(a,b)},\frac{b}{\gcd(a,b)}\rangle $. Vamos a empezar por inducción sobre el valor de $b$, para mostrar que necesitamos para considerar sólo un pequeño número de valores de $b$ cuando se busca ciclos. Tenga en cuenta que $a$ e $b$ no puede ser ambos inclusive, por lo que hay tres casos: $a=2m+1, b=2n$, $a=2m, b=2n+1$, e $a=2m+1, b=2n+1$. El tercer caso, de inmediato se pone a $\langle a',b'\rangle$ $=\mathop{Red}(\langle 2m+2n+2,2n+2\rangle)$ $=\mathop{Red}(\langle m+n+1,n+1\rangle)$; esto podría reducir aún más, pero esto es suficiente para nuestros propósitos. tenga en cuenta que $b'=n+1\lt b=2n+1$, por lo que el valor de $b$ siempre se reduce en este caso, a menos $b=1$.
En el caso de $a=2m+1, b=2n$, el mapa va $\langle 2m+1, 2n\rangle$ $\mapsto \mathop{Red}(\langle 2m+2n+1, 2n+1\rangle)$ $\mapsto\mathop{Red}(\langle 2m+4n+2, 2n+2\rangle)$ $=\mathop{Red}(\langle m+2n+1, n+1\rangle)$. Aquí tenemos a $b'=n+1\lt b=2n$ mientras $b\gt 2$.
Finalmente, en el caso de $a=2m, b=2n+1$, el mapa va $\langle 2m, 2n+1\rangle \mapsto\mathop{Red}(\langle 2m+2n+1, 2n+2\rangle)$ $\mapsto\mathop{Red}(\langle 2m+4n+3, 2n+3\rangle)$ $\mapsto\mathop{Red}(\langle 2m+6n+6, 2n+4\rangle) = \mathop{Red}(\langle m+3n+3, n+2\rangle)$. Aquí, $b'=n+2\lt b=2n+1$ mientras $b\gt 3$.
Juntos, estos significa que podemos estudiar los efectos de la iteración específicamente en los casos de $\langle a,b\rangle: b\in \{1,2,3\}$; de cualquier grande $b$ eventualmente reducir a un $b$ en este rango. Más específicamente, tenemos los casos de $\langle a, 1\rangle$, $\langle 2m+1, 2\rangle$, e $\langle 2m, 3\rangle$ a estudio. Voy a usar una forma diferente de inducción en estos casos, con base en el valor de $a+b$.
Vamos a empezar con el caso de $\langle a,1\rangle$. Si $a$ es impar, entonces tenemos $\langle 2m+1, 1\rangle \mapsto \langle m+1, 1\rangle$; aquí $a'+b'=m+2$ siempre será menor que $a+b=2m+2$. Si $a$ es par, entonces tenemos el caso de $\langle 2m, 1\rangle$; por la lógica anterior, se asigna a $\mathop{Red}(\langle m+3, 3\rangle)$. Obtenemos un valor menor para la suma siempre como $a+b=2m+1\gt a'+b'=m+6$, o en otras palabras como largo como $m\gt 5$ (es decir, $a\gt 10$).
A continuación, tenemos el caso de $\langle 2m+1, 2\rangle$; por la lógica anterior, se asigna a $\mathop{Red}(\langle m+3, 2\rangle)$. Desde $a'+b'=m+5\lt a+b=2m+3$ mientras $m\gt 2$, podemos ver que cualquier par $\langle a,2\rangle$ con $a$ un número impar mayor que $5$ va a dar una nueva pareja con la suma menor.
Por último, tenemos el caso de $\langle 2m, 3\rangle$; una vez más, el uso de la lógica anterior, podemos ver que este se asignará a $\mathop{Red}(\langle m+6, 3\rangle)$. Aquí tenemos a $a+b=2m+3\gt a'+b'=m+9$ mientras $m\gt 6$, o en otras palabras $a\gt 12$.
Poniendo todo esto junto, podemos ver que los casos de la forma $\langle a,b\rangle$ con $b\leq 3$ siempre ceder a otro caso de forma similar con menor $a$ mientras $a\gt 12$; esto deja sólo un número finito de valores para comprobar, que los rendimientos de los lazos que ya se han encontrado.
