1. Test

Hi, you'll have to learn how to calculate square roots with continued fractions.

Since formatting continued fractions is a nightmare of parentheses, I'll refer you to Continued Fraction -- from Wolfram MathWorld and ask you to read equation (3), which gives the basic form of the continued fractions we'll need and the shortcut form for this (4) so I don't scratch my eyeballs out trying to format things. Also see (11) for the finite version of this. Another bit of slightly confusing notation, [x] will mean the greatest integer less than x. This shouldn't be confused with our continued fraction notation, since that will always have more than one term.

Assume D is not a perfect square. To find the continued fraction expression of $\displaystyle \sqrt{D}$, we first set $\displaystyle a_{0}=[\sqrt{D}]$. This is a very crude approximation to \sqrt{D}. At this point we have $\displaystyle \sqrt{D}=a_{0}+(\sqrt{D}-a_{0})=a_{0}+\frac{1}{\frac{1}{\sqrt{D}-a_{0}}}$
We apply the same procedure to $\displaystyle \frac{1}{\sqrt{D}-a_{0}}=\frac{\sqrt{D}+a_{0}}{D-a_{0}^{2}} and get a_{1}=[\frac{\sqrt{D}+a_{0}}{D-a_{0}^{2}}]$

Now we have $\displaystyle \sqrt{D}=a_{0}+\frac{1}{a_{1}+(\frac{\sqrt{D}+a_{0 }}{D-a_{0}^{2}}-a_{1})}$

Now $\displaystyle a_{2}=[\frac{1}{\frac{\sqrt{D}+a_{0}}{D-a_{0}^{2}}-a_{1}}]$. Continue to get the rest of the a's. Eventually you'll get something that repeats like $\displaystyle \sqrt{D}=[a_{0}, a_{1}, \ldots, a_{k}, a_{0}+\sqrt{D}]$

Heres where you stop. If k is odd find integers x and y where $\displaystyle x/y=[a_{0}, a_{1}, \ldots, a_{k}]$. These are your minimal solutions to Pell's equation. If k is even, you do something similar, I'm not positive exactly what, sorry. I'll hopefully come back tomorrow with an answer.

An example: D=14

$\displaystyle a_{0}=[\sqrt{14}]=3$
so
$\displaystyle \sqrt{14}=3+\frac{1}{\frac{1}{\sqrt{14}-3}}$

$\displaystyle a_{1}=[\frac{1}{\sqrt{14}-3}]=[\frac{\sqrt{14}+3}{5}]=1$

So $\displaystyle \sqrt{14}=3+\frac{1}{1+(\frac{\sqrt{14}+3}{5}-1)}=3+\frac{1}{1+\frac{1}{\frac{1}{\frac{\sqrt{14} +3}{5}-1}}}$

$\displaystyle a_{2}=[\frac{1}{\frac{\sqrt{14}+3}{5}-1}]=[\frac{5}{\sqrt{14}-2}]=[\frac{\sqrt{14}+2}{2}]=2$

So
$\displaystyle \sqrt{14}=3+\frac{1}{1+\frac{1}{2+(\frac{\sqrt{14} +2}{2}-2)}}$

ok I'm stopping here. Go a couple more steps and you'll get $\displaystyle \sqrt{14}=[3,1,2,1,3+\sqrt{14}],$ so we've started to repeat.

Now find $\displaystyle [3,1,2,1]=3+\frac{1}{1+\frac{1}{2+\frac{1}{1}}}=15/4$, so x=15 and y=4 are the minimal solutions in this case.

2. I figured out what to do when k is even. I knew it involved doubling the period or something similar, but it wasn't working out. Sorry for the confusion.

Anyhoo, ionce you get to $\displaystyle \sqrt{D}=[a_{0}, a_{1}, \ldots, a_{k}, a_{0}+\sqrt{D}]$and k is even, you need to find x, y with $\displaystyle x/y=[a_{0}, a_{1}, \ldots, a_{k}, 2a_{0}, a_{1}, \ldots, a_{k}]$, then x, y are your minimal solutions.

The $\displaystyle 2a_{0}$ term shouldn't be suprising. If you were at $\displaystyle \sqrt{D}=[a_{0}, a_{1}$, $\displaystyle \ldots, a_{k}, a_{0}+\sqrt{D}]$, and you wanted to find more terms, you'd see $\displaystyle a_{k+1}=2a_{0}$. Muck about with a few examples and you'll see why this is so.

3. Glad it worked for you.

If you truncate after the first period you get $\displaystyle (-1)^{k+1}$.

If you try D=10, you'll get $\displaystyle [3,3+\sqrt{10}].$ If you take x/y=3/1 then you get

$\displaystyle 3^2-10\cdot 1^2=-1$

but if you go to $\displaystyle x/y=[3,6]=3+1/6=19/6$, you get:

$\displaystyle 19^2-10\cdot 6^2=1$

Notice $\displaystyle (3+\sqrt{10})(3+\sqrt{10})=19+6\sqrt{10}$, this is no accident! You can get the rest of the solutions to Pell's either by finding more periods of your continued fraction or by finding powers of your minimal solution.