Calcular la fracción continua de raíz cuadrada

Question

Yo estaba teniendo dificultades para entender el algoritmo para calcular Continuó fracción de expansión de la raíz cuadrada.

Sé que el proceso es acerca de la extracción de la parte entera de la repetición y el mantenimiento de la cuadrática irracional $\frac{m_n + \sqrt{S}}{d_n}$. Pero no entiendo la ecuación:

$d_{n+1} = \frac{S - m_{n+1}^2}{d_n}$

Por qué $S - m_{n+1}^2$ es divisible por $d_n$?

En este caso, por ejemplo:

$$\ \dfrac {1-\sqrt{5}}2=-1+\dfrac {3-\sqrt{5}}2$$

$$\frac 1{\dfrac {3-\sqrt{5}}2}=\frac 2{3-\sqrt{5}}=\frac {2(3+\sqrt{5})}{(3-\sqrt{5})(3+\sqrt{5})}=\frac {2(3+\sqrt{5})}{9-5}=\frac {3+\sqrt{5}}{2}=2+\frac {\sqrt{5}-1}{2}$$

Si $S - m_{n+1}^2$ no es divisible por $d_n$, en el paso de $\frac {2(3+\sqrt{5})}{9-5}=\frac {3+\sqrt{5}}{2}$, puede resultar en algunos de los resultados como $\frac{3 + 3\sqrt{5}}{2}$ y romper el algoritmo. Así que ¿por qué no sucedió esto?

Answer 1

En el inicio, hemos (por $m=0$$d=1$) : $$\sqrt{S}=\frac{\sqrt{S}+m}d=a+\frac{\sqrt{S}+m-da}d$$ (con $a,\ m$ $d$ son enteros)

Supongamos que $\ d$ divide $(S-m^2)\ $ (esto es cierto para $d=1$ del curso).

La parte fraccionaria $\displaystyle \frac{\sqrt{S}+m-da}d$ se convierte en :

$$\frac{\sqrt{S}-da+m}d=\frac{S-(da-m)^2}{d\bigl(\sqrt{S}+da-m\bigr)}$$

El numerador $\ S-(da-m)^2=(S-m^2)+da(2m-da)$ será divisible por $d$ (a partir de nuestra hipótesis).
Si observamos $\ m':=da-m\ $, entonces el numerador dividido por $d$ hace $\ d':=\dfrac{S-(da-m)^2}d=\dfrac{S-m'^2}d$

y el siguiente mandato para examinar será :

$$\frac{\sqrt{S}+da-m}{\frac{S-(da-m)^2}d}=\frac{\sqrt{S}+m'}{d'}$$

Pero las condiciones son las mismas que en el inicio :

$\ d'$ divide $(S-m'^2)\ $ (la fracción de la anterior $d$ !) y podemos continuar con nuestra reescritura : $$\frac{\sqrt{S}+m'}{d'}=a'+\frac{\sqrt{S}+m'-d'a'}{d'}$$

Esta recurrencia muestra de que estas condiciones se mantenga en cada iteración.
(Para ser completa, vamos a agregar que en cada paso $\ a:=\left\lfloor\dfrac{\sqrt{S}+m}d\right\rfloor$)