I was having difficulty understanding the algorithm to calculate Continued fraction expansion of square root.
I know the process is about extracting the integer part in repeat and maintaining the quadratic irrational $\frac{m_n + \sqrt{S}}{d_n}$. But I don't understand the equation:
$d_{n+1} = \frac{S – m_{n+1}^2}{d_n}$
Why $S – m_{n+1}^2$ is dividable by $d_n$?
This case for example:
$$\ \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}$$
If $S – m_{n+1}^2$ is not dividable by $d_n$, in the step $\frac {2(3+\sqrt{5})}{9-5}=\frac {3+\sqrt{5}}{2}$, it may result in some result like $\frac{3 + 3\sqrt{5}}{2}$ and break the algorithm. So why won't this happened?
Best Answer
At the start we have (for $m=0$ and $d=1$) : $$\sqrt{S}=\frac{\sqrt{S}+m}d=a+\frac{\sqrt{S}+m-da}d$$ (with $a,\ m$ and $d$ are integers)
Suppose that $\ d$ divides $(S-m^2)\ $ (this is true for $d=1$ of course).
The fractional part $\displaystyle \frac{\sqrt{S}+m-da}d$ becomes :
$$\frac{\sqrt{S}-da+m}d=\frac{S-(da-m)^2}{d\bigl(\sqrt{S}+da-m\bigr)}$$
The numerator $\ S-(da-m)^2=(S-m^2)+da(2m-da)$ will be divisible by $d$ (from our hypothesis).
If we note $\ m':=da-m\ $ then the numerator divided by $d$ becomes $\ d':=\dfrac{S-(da-m)^2}d=\dfrac{S-m'^2}d$
and the next term to examine will be :
$$\frac{\sqrt{S}+da-m}{\frac{S-(da-m)^2}d}=\frac{\sqrt{S}+m'}{d'}$$
But the conditions are the same as at the start :
$\ d'$ divides $(S-m'^2)\ $ (the fraction is the previous $d$ !) and we may continue our rewriting : $$\frac{\sqrt{S}+m'}{d'}=a'+\frac{\sqrt{S}+m'-d'a'}{d'}$$
This recurrence shows that these conditions will hold at each iteration.
(To be complete let's add that at each step $\ a:=\left\lfloor\dfrac{\sqrt{S}+m}d\right\rfloor$)