# 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:

- $\sqbrk {a_1 \sequence {b_1, b_2, \ldots, b_{m - 1}, b_m, b_{m - 1}, \ldots, b_2, b_1, 2 a_1} }$

or

- $\sqbrk {a_1 \sequence {b_1, b_2, \ldots, b_{m - 1}, b_m, b_m, b_{m - 1}, \ldots, b_2, b_1, 2 a_1} }$

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 section, either:
- $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 = \floor {\sqrt n}$
- $\sqrt n = a_0 + \dfrac 1 {\alpha_0}$

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

- $a_{i + 1} = \floor {\alpha_i}$
- $\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 irrationals 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}$
- $\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 that:

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

\(\ds 1\) | \(<\) | \(\ds \sqrt n + a_0\) | ||||||||||||

\(\ds \leadsto \ \ \) | \(\ds \sqrt n - a_0\) | \(<\) | \(\ds n - a_0^2\) | |||||||||||

\(\ds \leadsto \ \ \) | \(\ds a_0 - \sqrt n\) | \(>\) | \(\ds -\paren {n - a_0^2}\) | |||||||||||

\(\ds \leadsto \ \ \) | \(\ds \tilde {\alpha_0}\) | \(>\) | \(\ds -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$.

Thus $\alpha_0$ is associated to $n$ as well.

We have that each $\alpha_i$ is a reduced quadratic irrational.

So, following the recurrence defined, each $a_i \ge 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.

Work In ProgressIn particular: This gives us the fact that it repeats. We still need explain the pattern.You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by completing it.To discuss this page in more detail, feel free to use the talk page.When this work has been completed, you may remove this instance of `{{WIP}}` from the code. |

## Examples

\(\ds \sqrt 2\) | \(=\) | \(\ds \sqbrk {1, \sequence 2}\) | ||||||||||||

\(\ds \sqrt 3\) | \(=\) | \(\ds \sqbrk {1, \sequence {1, 2} }\) | ||||||||||||

\(\ds \sqrt 5\) | \(=\) | \(\ds \sqbrk {2, \sequence 4}\) | ||||||||||||

\(\ds \sqrt 6\) | \(=\) | \(\ds \sqbrk {2, \sequence {2, 4} }\) | ||||||||||||

\(\ds \sqrt 7\) | \(=\) | \(\ds \sqbrk {2, \sequence {1, 1, 1, 4} }\) | ||||||||||||

\(\ds \sqrt {13}\) | \(=\) | \(\ds \sqbrk {3, \sequence {1, 1, 1, 1, 6} }\) | ||||||||||||

\(\ds \sqrt {19}\) | \(=\) | \(\ds \sqbrk {4, \sequence {2, 1, 3, 1, 2, 8} }\) | ||||||||||||

\(\ds \sqrt {28}\) | \(=\) | \(\ds \sqbrk {5, \sequence {3, 2, 3, 10} }\) | ||||||||||||

\(\ds \sqrt {31}\) | \(=\) | \(\ds \sqbrk {5, \sequence {1, 1, 3, 5, 3, 1, 1, 10}\ }\) |