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 \sqrt{D}, we first set a_{0}=[\sqrt{D}]. This is a very crude approximation to \sqrt{D}. At this point we have \sqrt{D}=a_{0}+(\sqrt{D}-a_{0})=a_{0}+\frac{1}{\frac{1}{\sqrt{D}-a_{0}}}

We apply the same procedure to \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 \sqrt{D}=a_{0}+\frac{1}{a_{1}+(\frac{\sqrt{D}+a_{0 }}{D-a_{0}^{2}}-a_{1})}

Now 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 \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 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

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

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

So \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}}}

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

So
\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 \sqrt{14}=[3,1,2,1,3+\sqrt{14}], so we've started to repeat.

Now find [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.