La prueba de que fracciones continuas finitas para los racionales?

Question

¿Cómo hace uno para demostrar que la continuación de la fracción representaciones de los números racionales son finitos?

Para cada $x\in\mathbb{R}$, la (simple) la continuación de la fracción representación de $x$ es: $$ x = [a_0; a_1, a_2, ...] = a_0 + \frac{1}{a_1 + \frac{1}{a_2 + \frac{1}{...}}} $$ donde$a_0\in\mathbb{Z}$$a_k\in\mathbb{N}$$k\geq 1$, que son en sí obtiene de la siguiente manera: $$ \begin{align} r_0 &= x \\ \forall k \geq 0,\quad a_k &= \lfloor r_k \rfloor \\ \forall k \geq 0,\quad r_{k+1} &= \begin{cases} 1 / (r_k-a_k) & \text{if } r_k > a_k \\ 0 & \text{otherwise} \end{casos} \end{align} $$ y si no existe $n$ que $r_n > r_{n+1} = 0$, entonces la corrección de $a_n\mapsto a_n-1$.

Es evidente que si la secuencia de $a_k$ converge a 0, $x$ es racional. Pero el recíproco no parece trivial en absoluto; ¿por qué esta recursividad necesariamente terminar si $x = p/q$? Contraposición no parece evidente para mí aquí. Hay otra forma de pensar acerca de esto?

Answer 1

es el Algoritmo de Euclides, que es de todos. Muchas personas usan "sustitución" para terminar el Algoritmo Extendido y encontrar el Bezout combinación, prefiero escribir esto como una continuación de la fracción.

$$ \gcd( 12345, 1601 ) = ??? $$

$$ \frac{ 12345 }{ 1601 } = 7 + \frac{ 1138 }{ 1601 } $$ $$ \frac{ 1601 }{ 1138 } = 1 + \frac{ 463 }{ 1138 } $$ $$ \frac{ 1138 }{ 463 } = 2 + \frac{ 212 }{ 463 } $$ $$ \frac{ 463 }{ 212 } = 2 + \frac{ 39 }{ 212 } $$ $$ \frac{ 212 }{ 39 } = 5 + \frac{ 17 }{ 39 } $$ $$ \frac{ 39 }{ 17 } = 2 + \frac{ 5 }{ 17 } $$ $$ \frac{ 17 }{ 5 } = 3 + \frac{ 2 }{ 5 } $$ $$ \frac{ 5 }{ 2 } = 2 + \frac{ 1 }{ 2 } $$ $$ \frac{ 2 }{ 1 } = 2 + \frac{ 0 }{ 1 } $$ Simple continuación de la fracción de tableau:
$$ \begin{array}{cccccccccccccccccccc} & & 7 & & 1 & & 2 & & 2 & & 5 & & 2 & & 3 & & 2 & & 2 & \\ \frac{ 0 }{ 1 } & \frac{ 1 }{ 0 } & & \frac{ 7 }{ 1 } & & \frac{ 8 }{ 1 } & & \frac{ 23 }{ 3 } & & \frac{ 54 }{ 7 } & & \frac{ 293 }{ 38 } & & \frac{ 640 }{ 83 } & & \frac{ 2213 }{ 287 } & & \frac{ 5066 }{ 657 } & & \frac{ 12345 }{ 1601 } \end{array} $$ $$ $$ $$ 12345 \cdot 657 - 1601 \cdot 5066 = -1 $$

Answer 2

La única forma de que esto de la recursión para terminar, es para la secuencia de $a_k$ a converger a $0$, y esto sólo sucede cuando uno de los $r_k$ se convierte en un entero.

Si esto no es claro para usted, considere la posibilidad de que $\forall x\in\mathbb{R},\ x-\lfloor x\rfloor\in[0,1)$; por lo tanto, la única manera de que el $a_k$ converge a cero es si en algún punto de $r_k = \lfloor r_k\rfloor$, es decir, $r_k$ es un número entero. Es fácil ver que una vez que esto sucede, todas las $r_k$ $a_k$ son cero. (Tenga en cuenta también que el $a_0$ puede ser cero sin que ello implique la convergencia, que no es el caso para las subsiguientes $a_k$.)

La principal cosa que cambia si $x$ es racional, es que el $r_k$ son todos racionales (resta con números enteros y recíproca de un no-cero inversa de elementales operaciones en $\mathbb{Q}$).

Para todos $k>0$, $r_k$ es integral o racional mayor que 1.

Prueba:

Si alguna de las $r_{k\geq 0}$ es integral, a continuación, todos los sucesores son cero.

Si $r_0$ es un racional menor que 1, entonces $0 < r_0 - \lfloor r_0 \rfloor < 1$ y, por tanto,$r_1 > 1$. Del mismo modo, si $r_k = p/q$ $p > q > 0$ algunos $k > 0$, entonces: $$ \existe n\in\mathbb{N},\quad 0 < n < \frac{p}{q} < n+1 \quad\implica\quad a_k = n \quad\text{y}\quad r_{k+1} = \frac{q}{p-cn} $$ con $p - nq < q$ (debido a $n$ es tal que $p < (n+1)q$).

---

Por cierto, esto también muestra que la secuencia de los denominadores de $r_k$ $k > 0$ es estrictamente decreciente, mientras que la secuencia se compone de racionales. Desde estos denominadores están delimitadas por debajo de cero, y que el anterior inducción se aplica para los valores mayores que uno, se le necesariamente encontrar un plazo $r_K = p/q$ que $q|p$ (entero caso) o $p \equiv 1 \mod q$ (en cuyo caso $r_{K+1}$ es un número entero).