# Test

• Jun 25th 2008, 08:43 AM
Peritus
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.
• Jun 25th 2008, 08:58 AM
Peritus
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 $\sqrt{D}=[a_{0}, a_{1}, \ldots, a_{k}, a_{0}+\sqrt{D}]$and k is even, you need to find x, y with $x/y=[a_{0}, a_{1}, \ldots, a_{k}, 2a_{0}, a_{1}, \ldots, a_{k}]$, then x, y are your minimal solutions.

The $2a_{0}$ term shouldn't be suprising. If you were at $\sqrt{D}=[a_{0}, a_{1}$, $\ldots, a_{k}, a_{0}+\sqrt{D}]$, and you wanted to find more terms, you'd see $a_{k+1}=2a_{0}$. Muck about with a few examples and you'll see why this is so.
• Jun 25th 2008, 09:01 AM
Peritus
If you truncate after the first period you get $(-1)^{k+1}$.
If you try D=10, you'll get $[3,3+\sqrt{10}].$ If you take x/y=3/1 then you get
$3^2-10\cdot 1^2=-1$
but if you go to $x/y=[3,6]=3+1/6=19/6$, you get:
$19^2-10\cdot 6^2=1$
Notice $(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.