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

continued-fractionsnumber theoryquadraticsroots

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$?

Best Answer

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$.