Why is the coefficient in front of $\sqrt n$ always 1 in the intermediate terms for finding the continued fraction expansion of $\sqrt n$?

Question

After playing around on paper for a bit, I came up with a short python generator to find the continued fraction expansion of $\sqrt n$. I understand why it gets the right answer when it gets an answer. But I don't understand why that last divmod always has no remainder. (In other words, why is the coefficient in front of the $\sqrt n$ always 1 in the intermediate terms of the expansion)

from math import sqrt

def contfracsqrt(n):
    k = int(sqrt(n))
    x = 0
    d = 1
    while True:
        a,x=divmod(x+k,d)
        yield a
        x=k-x
        d,t=divmod(n-x**2,d)
        assert t==0

Clarification: I'm not doing anything fancy. I'm finding the continued fraction the simplest way I know of. Suppose we want to find the continued fraction for $\sqrt{n}$. Now let k=$\lfloor\sqrt(n)\rfloor$. We have an expression of the form

$\frac{\sqrt{n}+x_i}{d_i}$

where x and d are integers. (Note that this is just $\sqrt{n}$ when $x_0=0$ and $d_0=1$)

The integer part is

$a_i=\lfloor{\frac{k+x_i}{d_i}}\rfloor$

Now let $r_i=((k+x_i)\bmod{d_i})$ (the other part of the divmod)

Then the fractional part is

$\frac{\sqrt{n} - (k-r_i)}{d_i}$

which can be re-written as 1 over its reciporical to get an expression whose integer part is the next term:

$=\frac{1}{\frac{d_i}{\sqrt{n}-(k-r_i)}}=\frac{1}{\frac{\sqrt{n}+(k-r_i)}{\frac{n-(k-r_i)^2}{d_i}}}$

So that the next term has

$x_{i+1}=k-r_i$

$d_{i+1}=\frac{n-(k-r_i)^2}{d_i}$

This works, because $d_{i+1}$ always seems to be an integer. My question is why?

Answer 1

Ok,

So I found a simple inductive proof which relies on strengthening the inductive hypothesis (and hence the result).

Proof that $\forall i, d_i\in\mathbb{Z}$ and $d_i|n-x_i^2$

Base case:

$d_0=1$ so it's $\in\mathbb{Z}$ and it divides any integer expression

Inductive case:

Given some $i$, assume $d_i\in\mathbb{Z}$ and $d_i|n-x_i^2$

Now because $a_i$ and $r_i$ are the div and mod of $k+x_i$ with $d_i$ (see the notation used in the question) we can say

$d_i|x_i+k-r_i$

We can multiply the right-hand expression by $x_i-(k-r_i)$ to get

$d_i|x_i^2-(k-r_i)^2$

Adding this to the expression in our inductive hypothesis gives

$d_i|n-(k-r_i)^2$

So $d_{i+1}\in\mathbb{Z}$

Additionally, if we look at the other expression we need to prove, substituting in the expressions for $d_{i+1}$ and $x_{i+1}$ we get:

$\frac{n-(k-r_i)^2}{d_i}|n-(k-r_i)^2=d_{i+1}|n-x_{i+1}^2$

which follows trivially from the fact that $d_i\in\mathbb{Z}$

QED

Answer 2

I don't understand. The continued fraction for $\sqrt {41}$ is $\langle 6; 2,2,12 \rangle.$

Here is output from my C++ program doing Lagrange's method of "reduced forms," which are the triples of integers in the middle of each line in the cycle. It is in precisely this situation, by the way, that Lagrange's method gives double the cyclic part in the continued fraction method.

jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$ ./Pell
Input n for Pell 
41

0  form   1 12 -5   delta  -2
1  form   -5 8 5   delta  2
2  form   5 12 -1   delta  -12
3  form   -1 12 5   delta  2
4  form   5 8 -5   delta  -2
5  form   -5 12 1   delta  12
6  form   1 12 -5

 disc   164
Automorph, written on right of Gram matrix:  
-129  -1600
-320  -3969


 Pell automorph 
-2049  -13120
-320  -2049

Pell unit 
-2049^2 - 41 * -320^2 = 1 

=========================================

Pell NEGATIVE 
-32^2 - 41 * -5^2 = -1 

=========================================

41       41

jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$ 

---