# Size of partial quotients in continued fraction expansion of $\sqrt{n}$

It is a well-known result that the partial fraction expansion of $\sqrt{n}$ for some non-square natural number $n$ is periodic of the form

$$[a_0, \overline{a_1, a_2, \ldots, a_{l-1}, 2a_0}]$$ where $a_0 = \lfloor\sqrt{n}\rfloor$ and $a_1, \ldots, a_{l-1}$ is palindromic.

However, here is something that I could not find anywhere explicitly: Is anything more known about the size of the $a_1, \ldots, a_{l-1}$? Are they always ${}\leq a_0$? Looking at the first $10^5$ or so examples seems to suggest so.

If not that, are they at least ${}<2a_0$?

• – dan_fulea Jul 2 '18 at 11:01
• Once upon a time, I thought I had a proof of just this, but recently I tried to recreate it, and got stumped. Another “fact” I thought I had a proof of is that $a_0$ may appear only once in the period, and thus in the center. – Lubin Jul 3 '18 at 4:24
• Here is the same question for $n$ prime: math.stackexchange.com/questions/2593032 – punctured dusk Jul 3 '18 at 6:43
• @Lubin It is true, also that $a_0$ can occur at most once in a period. It is however the kind of fiddly proof that is easy to forget. I had to dig out my old write-up on continued fractions to see how to prove it. – Daniel Fischer Jul 6 '18 at 13:05

It is more convenient to look at this in terms of

$$\omega = \sqrt{n} + \lfloor \sqrt{n}\rfloor = \bigl[\overline{q_0,q_1,\dotsc,q_{l-1}}\bigr]\,.$$

It is clear that we have $q_0 = 2a_0$ and $q_k = a_k$ for $k \geqslant 1$, since $\omega$ differs from $\sqrt{n}$ exactly by the integer $a_0$.

Proposition: The partial quotients of the simple continued fraction expansion of $\omega$ satisfy $q_k \leqslant a_0$ for $k \not\equiv 0 \pmod{l}$, where $l$ is the minimal period of the continued fraction expansion. Additionally, $q_k = a_0$ can happen at most once per period, in the middle.

Proof: We can write the complete quotients of $\omega$ in the form $$\omega_k = \frac{\sqrt{n} + b_k}{c_k}$$ with integers $b_k, c_k$ satisfying

1. $0 < b_k < \sqrt{n}$,
2. $0 < c_k < \sqrt{n} + b_k$, and
3. $c_k \mid (n - b_k^2)$.

This is proved by induction. The base case $k = 0$ is immediate, for $$\omega_0 = \omega = \frac{\sqrt{n} + \lfloor \sqrt{n}\rfloor}{1}\,,$$

i.e. $b_0 = \lfloor \sqrt{n}\rfloor$ and $c_0 = 1$. For the induction step, we note that $b_{k+1} = q_{k}c_{k} - b_{k}$ and $c_{k+1} = \frac{n - b_{k+1}^2}{c_{k}}$. Since $b_{k+1} \equiv -b_k \pmod{c_k}$, we have $$(n - b_{k+1}^2) \equiv (n - b_{k}^2) \equiv 0 \pmod{c_{k}}$$ by the induction hypothesis, so $c_{k+1}$ is an integer (that $b_{k+1}$ is an integer is obvious). And by the continued fraction algorithm \begin{align} \omega_{k+1} &= \frac{1}{\omega_k - q_k} \\ &= \biggl(\frac{\sqrt{n} + b_k}{c_k} - q_k\biggr)^{-1} \\ &= \biggl(\frac{\sqrt{n} - (q_kc_k - b_k)}{c_k}\biggr)^{-1} \\ &= \frac{c_k}{\sqrt{n} - b_{k+1}} \\ &= \frac{c_k(\sqrt{n} + b_{k+1})}{n - b_{k+1}^2} \\ &= \frac{\sqrt{n} + b_{k+1}}{c_{k+1}}\,. \end{align}

Thus it is immediate that 3. holds for $k+1$ if it holds for $k$, and 2. follows from 1. since we always have $\omega_{k+1} > 1$. To see that 1. holds, note that $b_{k+1} < \sqrt{n}$ is equivalent to $\omega_k - q_k = \omega_k - \lfloor \omega_k\rfloor > 0$, which is true because $\omega_k$ is irrational. And \begin{align} && 0 &< b_{k+1} \\ &\iff& 0 &< q_k c_k - b_k \\ &\iff& \frac{b_k}{c_k} &< q_k\,. \end{align}

If $b_k < c_k$, then this is true because $q_k = \lfloor \omega_k\rfloor \geqslant 1$. And if $c_k \leqslant b_k$, then $c_k < \sqrt{n}$ and thus $$q_k = \biggl\lfloor \frac{\sqrt{n} + b_k}{c_k}\biggr\rfloor \geqslant \biggl\lfloor \frac{c_k + b_k}{c_k}\biggr\rfloor = 1 + \biggl\lfloor \frac{b_k}{c_k}\biggr\rfloor > \frac{b_k}{c_k}\,.$$

Having established $b_k \leqslant \lfloor\sqrt{n}\rfloor = a_0$ and $c_k > 0$ for all $k$, we see that

$$q_k = \biggl\lfloor \frac{\sqrt{n} + b_k}{c_k}\biggr\rfloor = \biggl\lfloor \frac{a_0 + b_k}{c_k}\biggr\rfloor \leqslant \biggl\lfloor \frac{2a_0}{c_k}\biggr\rfloor\,.$$

Thus $q_k \leqslant a_0$ unless $c_k = 1$. But if $c_k = 1$, then clearly $q_k = a_0 + b_k$, $b_{k+1} = a_0 = b_1$ and $c_{k+1} = n - a_0^2 = c_1$, i.e. $\omega_{k+1} = \omega_1$, which means $k$ is a multiple of the minimal period $l$.

Additionally, we see that $q_r = a_0$ if and only if $c_r = 2$ and $b_r = a_0$. Then we have $b_{r+1} = a_0 = b_r$ and $$c_rc_{r+1} = n - b_{r+1}^2 = n - b_r^2 = c_{r-1}c_r\,,$$ whence $c_{r+1} = c_{r-1}$. From this one finds $$b_{r+m} = b_{r+1-m} \qquad\text{and}\qquad c_{r+m} = c_{r-m}$$ as well as $q_{r+m} = q_{r-m}$ for $0 \leqslant m \leqslant r$ using the recursion $b_{k+1} = q_kc_k - b_k$ and $c_kc_{k+1} = n - b_{k+1}^2$. Thus if $q_r = a_0$, then $c_{2r} = c_0 = 1$ and $2r$ is a multiple of $l$. So $q_k = a_0$ can happen at most once in a period, and if it happens the period has even length and $q_{l/2} = a_0$.

• Thanks! I figured out a proof very much like this as well in the mean time, except for the ‘$a_0$ can happen at most once’ part, but I did not have the time to write it up in prose yet. – Manuel Eberl Jul 6 '18 at 17:03

I am more comfortable with the Lagrange cycle description of this. The "partial quotients" are the absolute values of my $\delta$ in the example below. A "reduced" form is an ordered triple $\langle A,B,C \rangle$ that stands for the quadratic form $A x^2 + B xy + C y^2.$ The original description of "reduced" had more square roots in it, it suffices to say $$AC < 0 \; \; \; \mbox{AND} \; \; \; B > |A+C|$$ as long as the discriminant is correct, $B^2 - 4 AC = \Delta.$ For Pell equation we have $\Delta = 4n$ from the (non-reduced) form $x^2 - n y^2.$ It follows that $B^2 < \Delta$ so $B < 2 \sqrt n \; .$

Given a reduced form $\langle A,B,C \rangle,$ the number I call $\delta$ has $$\delta C > 0 \; \; \; \mbox{AND} \; \; \; |\delta| = \left\lfloor \; \left| \; \frac{B + \sqrt \Delta}{2C} \; \right| \; \right\rfloor \; \; .$$ I should emphasize that we find the integer part of $\sqrt \Delta$ once and for all, and use that every time $\delta$ is calculated. So this is integer arithmetic.

Now the numerator is less than $4 \sqrt n \; .$ IF $|C| = 1,$ then we are allowed to have $|\delta|$ as large as $2 \sqrt n.$ There is a special case for forms that do represent $-1,$ which happens when $n \equiv 1 \pmod 4$ is prime for example. I have my software continue to $x^2 - n y^2 = 1.$

Other than that, the vast majority of the time (and for you, all the time if you are just doing the continued fraction) we have $|C| \geq 2,$ therefore $|\delta| < \sqrt n \; .$

jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$./Pell 103 0 form 1 20 -3 delta -6 1 form -3 16 13 delta 1 2 form 13 10 -6 delta -2 3 form -6 14 9 delta 1 4 form 9 4 -11 delta -1 5 form -11 18 2 delta 9 6 form 2 18 -11 delta -1 7 form -11 4 9 delta 1 8 form 9 14 -6 delta -2 9 form -6 10 13 delta 1 10 form 13 16 -3 delta -6 11 form -3 20 1 delta 20 12 form 1 20 -3 disc 412 Automorph, written on right of Gram matrix: 3338 67257 22419 451718 Pell automorph 227528 2309157 22419 227528 Pell unit 227528^2 - 103 * 22419^2 = 1 ========================================= 2 477^2 - 103 * 47^2 = 2 =========================================  Probably more familiar, although still done with integer operations only: Method described by Prof. Lubin at Continued fraction of$\sqrt{67} - 4\$

$$\sqrt { 103} = 10 + \frac{ \sqrt {103} - 10 }{ 1 }$$ $$\frac{ 1 }{ \sqrt {103} - 10 } = \frac{ \sqrt {103} + 10 }{3 } = 6 + \frac{ \sqrt {103} - 8 }{3 }$$ $$\frac{ 3 }{ \sqrt {103} - 8 } = \frac{ \sqrt {103} + 8 }{13 } = 1 + \frac{ \sqrt {103} - 5 }{13 }$$ $$\frac{ 13 }{ \sqrt {103} - 5 } = \frac{ \sqrt {103} + 5 }{6 } = 2 + \frac{ \sqrt {103} - 7 }{6 }$$ $$\frac{ 6 }{ \sqrt {103} - 7 } = \frac{ \sqrt {103} + 7 }{9 } = 1 + \frac{ \sqrt {103} - 2 }{9 }$$ $$\frac{ 9 }{ \sqrt {103} - 2 } = \frac{ \sqrt {103} + 2 }{11 } = 1 + \frac{ \sqrt {103} - 9 }{11 }$$ $$\frac{ 11 }{ \sqrt {103} - 9 } = \frac{ \sqrt {103} + 9 }{2 } = 9 + \frac{ \sqrt {103} - 9 }{2 }$$ $$\frac{ 2 }{ \sqrt {103} - 9 } = \frac{ \sqrt {103} + 9 }{11 } = 1 + \frac{ \sqrt {103} - 2 }{11 }$$ $$\frac{ 11 }{ \sqrt {103} - 2 } = \frac{ \sqrt {103} + 2 }{9 } = 1 + \frac{ \sqrt {103} - 7 }{9 }$$ $$\frac{ 9 }{ \sqrt {103} - 7 } = \frac{ \sqrt {103} + 7 }{6 } = 2 + \frac{ \sqrt {103} - 5 }{6 }$$ $$\frac{ 6 }{ \sqrt {103} - 5 } = \frac{ \sqrt {103} + 5 }{13 } = 1 + \frac{ \sqrt {103} - 8 }{13 }$$ $$\frac{ 13 }{ \sqrt {103} - 8 } = \frac{ \sqrt {103} + 8 }{3 } = 6 + \frac{ \sqrt {103} - 10 }{3 }$$ $$\frac{ 3 }{ \sqrt {103} - 10 } = \frac{ \sqrt {103} + 10 }{1 } = 20 + \frac{ \sqrt {103} - 10 }{1 }$$

Simple continued fraction tableau:
$$\begin{array}{cccccccccccccccccccccccccccccc} & & 10 & & 6 & & 1 & & 2 & & 1 & & 1 & & 9 & & 1 & & 1 & & 2 & & 1 & & 6 & & 20 & \\ \\ \frac{ 0 }{ 1 } & \frac{ 1 }{ 0 } & & \frac{ 10 }{ 1 } & & \frac{ 61 }{ 6 } & & \frac{ 71 }{ 7 } & & \frac{ 203 }{ 20 } & & \frac{ 274 }{ 27 } & & \frac{ 477 }{ 47 } & & \frac{ 4567 }{ 450 } & & \frac{ 5044 }{ 497 } & & \frac{ 9611 }{ 947 } & & \frac{ 24266 }{ 2391 } & & \frac{ 33877 }{ 3338 } & & \frac{ 227528 }{ 22419 } \\ \\ & 1 & & -3 & & 13 & & -6 & & 9 & & -11 & & 2 & & -11 & & 9 & & -6 & & 13 & & -3 & & 1 \end{array}$$

$$\begin{array}{cccc} \frac{ 1 }{ 0 } & 1^2 - 103 \cdot 0^2 = 1 & \mbox{digit} & 10 \\ \frac{ 10 }{ 1 } & 10^2 - 103 \cdot 1^2 = -3 & \mbox{digit} & 6 \\ \frac{ 61 }{ 6 } & 61^2 - 103 \cdot 6^2 = 13 & \mbox{digit} & 1 \\ \frac{ 71 }{ 7 } & 71^2 - 103 \cdot 7^2 = -6 & \mbox{digit} & 2 \\ \frac{ 203 }{ 20 } & 203^2 - 103 \cdot 20^2 = 9 & \mbox{digit} & 1 \\ \frac{ 274 }{ 27 } & 274^2 - 103 \cdot 27^2 = -11 & \mbox{digit} & 1 \\ \frac{ 477 }{ 47 } & 477^2 - 103 \cdot 47^2 = 2 & \mbox{digit} & 9 \\ \frac{ 4567 }{ 450 } & 4567^2 - 103 \cdot 450^2 = -11 & \mbox{digit} & 1 \\ \frac{ 5044 }{ 497 } & 5044^2 - 103 \cdot 497^2 = 9 & \mbox{digit} & 1 \\ \frac{ 9611 }{ 947 } & 9611^2 - 103 \cdot 947^2 = -6 & \mbox{digit} & 2 \\ \frac{ 24266 }{ 2391 } & 24266^2 - 103 \cdot 2391^2 = 13 & \mbox{digit} & 1 \\ \frac{ 33877 }{ 3338 } & 33877^2 - 103 \cdot 3338^2 = -3 & \mbox{digit} & 6 \\ \frac{ 227528 }{ 22419 } & 227528^2 - 103 \cdot 22419^2 = 1 & \mbox{digit} & 20 \\ \end{array}$$