Continued Fraction Expansion of Irrational Square Root

Theorem

Let $n \in \Z$ such that $n$ is not a square.

Then the continued fraction expansion of $\sqrt n$ is of the form:

$\left[{a_1 \left \langle{b_1, b_2, \ldots, b_{m-1}, b_m, b_{m-1}, \ldots, b_2, b_1, 2 a_1}\right \rangle}\right]$

or

$\left[{a_1 \left \langle{b_1, b_2, \ldots, b_{m-1}, b_m, b_m, b_{m-1}, \ldots, b_2, b_1, 2 a_1}\right \rangle}\right]$

where $m \in \Z: m \ge 0$.

That is, it has the form as follows:

• It is periodic;
• It starts with an integer $a_1$;
• Its cycle starts with a palindromic bit $b_1, b_2, \ldots, b_{m-1}, b_m, b_{m-1}, \ldots, b_2, b_1$ or $b_1, b_2, \ldots, b_{m-1}, b_m, b_m, b_{m-1}, \ldots, b_2, b_1$ which may be of length zero;
• Its cycle ends with twice the first partial quotient.

Proof

We use:

• Expansion of Associated Reduced Quadratic Irrational to establish a series of reduced quadratic irrationals associated to $n$

and then use

• Finitely Many Reduced Associated Quadratic Irrationals to assert this series must repeat (hence be periodic) due to the finite number of such irrationals.

Let:

• $a_0 = \left \lfloor {\sqrt n} \right \rfloor$
• $\sqrt n = a_0 + \dfrac 1 {\alpha_0}$

For all $i \in \N: i > 0$, let:

• $a_{i+1} = \left \lfloor {\alpha_i} \right \rfloor$
• $\alpha_i = a_{i + 1} + \dfrac 1 {\alpha_{i + 1}}$

From here, we will prove:

• $\alpha_0$ is a reduced quadratic irrational associated to $n$

• If all $\alpha_i: 0 \le i \le k$ are all reduced quadratic irrational associated to $n$, then so is $\alpha_{k + 1}$.

Since $\dfrac{1}{\alpha_0}$ is the fractional part of the irrational $\sqrt{n}$, we have:

$0 < \dfrac{1}{\alpha_0} < 1 \implies \alpha_0 > 1$

By simple algebra, we have:

$\alpha_0 = \dfrac{a_0 + \sqrt n}{n - a_0^2}, \qquad \tilde{\alpha_0} = \dfrac{a_0 - \sqrt n}{n - a_0^2}$

where $\tilde{\alpha_0}$ is the conjugate of $\alpha_0$.

Since $a_0$ is the floor of $\sqrt n$, we know $a_0 - \sqrt n < 0 \implies \tilde{\alpha_0} < 0$.

Since $n \in \Z \implies \sqrt n > 1$ and $\sqrt n > a_0$, we have:

$1 < \sqrt n + a_0 \implies \sqrt n - a_0 < n - a_0^2 \implies a_0 - \sqrt n > -(n - a_0^2) \implies \tilde{\alpha_0} > -1$

Thus $\alpha_0$ is a reduced quadratic irrational.

Since $P = a_0$ and $Q = n - a_0^2 = n - P^2$, $Q$ clearly divides $n - P^2$ so $\alpha_0$ is associated to $n$ as well.

Following the recurrence defined, since each $\alpha_i$ is a reduced quadratic irrational, each $a_i \geq 1$.

Also, by Expansion of Associated Reduced Quadratic Irrational, each $\alpha_{i + 1}$ is reduced and associated to $n$ since $\alpha_0$ is.

By Finitely Many Reduced Associated Quadratic Irrationals, we only have finitely many choices for these.

Hence there must be some smallest $k$ for which $\alpha_k = \alpha_0$.

Since $\alpha_{i + 1}$ is determined completely by $\alpha_i$ we will then have $\alpha_{k + j} = \alpha_j$ for all $j > 0$.

Hence the $\alpha_i$ are periodic.

Similarly, as the $a_i$ for $i > 0$ are determined completely by $\alpha_{i - 1}$, the $a_i$ must be periodic as well.

This forces the continued fraction expansion:

$\sqrt n = a_0 + \cfrac{1}{a_1 + \cfrac{1}{a_2 + \ddots}}$

to be periodic.

Examples

	\(\displaystyle \)	\(\displaystyle \sqrt 2\)	\(=\)	\(\displaystyle \left[{1, \left \langle{2}\right \rangle}\right]\)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \sqrt 3\)	\(=\)	\(\displaystyle \left[{1, \left \langle{1, 2}\right \rangle}\right]\)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \sqrt 5\)	\(=\)	\(\displaystyle \left[{2, \left \langle{4}\right \rangle}\right]\)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \sqrt 6\)	\(=\)	\(\displaystyle \left[{2, \left \langle{2, 4}\right \rangle}\right]\)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \sqrt 7\)	\(=\)	\(\displaystyle \left[{2, \left \langle{1, 1, 1, 4}\right \rangle}\right]\)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \sqrt {13}\)	\(=\)	\(\displaystyle \left[{3, \left \langle{1, 1, 1, 1, 6}\right \rangle}\right]\)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \sqrt {19}\)	\(=\)	\(\displaystyle \left[{4, \left \langle{2, 1, 3, 1, 2, 8}\right \rangle}\right]\)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \sqrt {28}\)	\(=\)	\(\displaystyle \left[{5, \left \langle{3, 2, 3, 10}\right \rangle}\right]\)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \sqrt {31}\)	\(=\)	\(\displaystyle \left[{5, \left \langle{1, 1, 3, 5, 3, 1, 1, 10}\right \rangle}\right]\)	\(\displaystyle \)