The problem in Project Euler #64 asks us to generate continued fractions for square roots of integers.
The basic way to do it is:
A fraction
$\frac{\sqrt{n} + b}{d}$ can be expanded to:
$$
1 + \frac{1}{\frac{d}{\sqrt{n}+b}}
$$
$$
1 + \frac{1}{\frac{\sqrt{n}-b}{(\frac{n - b^2}{d})}}
$$
The next step involves factorizing $\frac{\sqrt{n}-b}{(\frac{n-b^2}{d})}$ to $$ a + \frac{\sqrt{n}+b'}{d'} $$ where $$ d' = (\frac{n-b^2}{d}) \\ a = \left \lfloor{\frac{\sqrt{n}-b}{(\frac{n-b^2}{d})}}\right \rfloor \\ b' = -b - ad' $$
Overall: $$ 1 + \frac{1}{\frac{d}{\sqrt{n}+b}} = 1 + \frac{1}{a + \frac{\sqrt{n}+b'}{d'}} $$
After this you repeat the steps on $\frac{\sqrt{n}+b'}{d'}$ to get the next fraction.
However in the expression $d' = \frac{n-b^2}{d}$, it is observed that $n-b^2$ is always evenly divisible by $d$ (remainder is $0$).
This greatly simplifies the problem. I'm however, stuck at why this property will always hold. I'm hoping you could help me with the proof.
Thank you for your help.
Ok I came up with the solution. I'm answering it here in case anybody wants help.
It can be proved using induction
Assume $n-b^2$ is divisible by $d$.
That is $ \frac{n-b^2}{d}$ is an integer
From $d' = \frac{n-b^2}{d}$ we can say that $ \frac{n-b^2}{d'} = d$ is also an integer
Now we have to prove that in the next step $\frac{n-b'^2}{d'}$ is also an integer
Substituting $$ b' = -b-ad'$$
in $$\frac{n-b'^2}{d'}$$ We get $$ \frac{n-b'^2}{d'} = \frac{n - b^2 - (ad')^2 - 2abd'}{d'} \\ = \frac{n-b^2}{d'} - \frac{(ad')^2 + 2abd'}{d'} $$
By our induction hypothesis the first term is an integer $(=d)$ and the other term is divisible by $d'$ trivially.
Hence both of them are integers and thus $\frac{n-b'^2}{d'}$ is also an integer.
The base case of induction is trivial as $d=1$ in the base case.