# Partial Quotients of Continued Fraction Expansion of Irrational Square Root

## Theorem

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

Let the continued fraction expansion of $\sqrt n$ be expressed as:

$\left[{a_0, a_1, a_2, \ldots}\right]$

Then the partial quotients of this continued fraction expansion can be calculated as:

$a_r = \left\lfloor{\dfrac{\left\lfloor{\sqrt n}\right\rfloor + P_r} {Q_r} }\right\rfloor$

where:

$P_r = \begin{cases} 0 & : r = 0 \\ a_{r - 1} Q_{r - 1} - P_{r - 1} & : r > 0 \\ \end{cases}$

$Q_r = \begin{cases} 1 & : r = 0 \\ \dfrac {n - {P_r}^2} {Q_{r - 1} } & : r > 0 \\ \end{cases}$

## Proof

The proof proceeds by strong induction.

For all $r \in \Z_{\ge 0}$, let $P \left({r}\right)$ be the proposition:

$a_r = \left\lfloor{\dfrac{\left\lfloor{\sqrt n}\right\rfloor + P_r} {Q_r} }\right\rfloor$

where:

$P_r = \begin{cases} 0 & : r = 0 \\ a_{r - 1} Q_{r - 1} - P_{r - 1} & : r > 0 \\ \end{cases}$

$Q_r = \begin{cases} 1 & : r = 0 \\ \dfrac {n - {P_r}^2} {Q_{r - 1} } & : r > 0 \\ \end{cases}$

### Edge Cases

By definition of the structure of a continued fraction:

$\sqrt n = a_0 + \dfrac 1 {x_1}$

for some $a_0 \in \Z$ and $x_1 \in \R_{>0}$.

Thus:

 $\ds a_0$ $=$ $\ds \left\lfloor{\sqrt n}\right\rfloor$ Definition of Floor Function $\ds$ $=$ $\ds \left\lfloor{\dfrac {\sqrt n + 0} 1}\right\rfloor$ $\ds$ $=$ $\ds \left\lfloor{\dfrac {\sqrt n + P_0} {Q_0} }\right\rfloor$ Definition of $P_0$ and $Q_0$ $\ds$ $=$ $\ds \left\lfloor{\dfrac {\left\lfloor{\sqrt n}\right\rfloor + P_0} {Q_0} }\right\rfloor$ Floor of $\dfrac {x + m} n$

Thus $P \left({0}\right)$ is seen to hold.

We have that:

$\sqrt n = a_0 + \dfrac 1 {x_1}$

Then:

 $\ds \dfrac 1 {x_1}$ $=$ $\ds \sqrt n - a_0$ $\ds \leadsto \ \$ $\ds x_1$ $=$ $\ds \dfrac 1 {n - a_0}$ $\ds$ $=$ $\ds \dfrac {\sqrt n + a_0} {\left({\sqrt n - a_0}\right) \left({\sqrt n + a_0}\right)}$ multiplying top and bottom by $\sqrt n + a_0$ $\ds$ $=$ $\ds \dfrac {\sqrt n + P_1} {Q_1}$ Definition of $P_1$ and $Q_1$

By definition of the structure of a continued fraction:

$x_1 = a_1 + \dfrac 1 {x_2}$

for some $a_1 \in \Z$ and $x_2 \in \R_{>0}$.

Hence:

 $\ds a_1$ $=$ $\ds \left\lfloor{\dfrac {\sqrt n + P_1} {Q_1} }\right\rfloor$ Definition of Floor Function $\ds$ $=$ $\ds \left\lfloor{\dfrac {\left\lfloor{\sqrt n}\right\rfloor + P_1} {Q_1} }\right\rfloor$ Floor of $\dfrac {x + m} n$

Thus $P \left({1}\right)$ is seen to hold.

### Basis for the Induction

We have that:

$x_1 = a_1 + \dfrac 1 {x_2}$

Then:

 $\ds \dfrac 1 {x_2}$ $=$ $\ds x_1 - a_1$ $\ds$ $=$ $\ds \dfrac {\sqrt n + P_1} {Q_1} - a_1$ $\ds$ $=$ $\ds \dfrac {\sqrt n + P_1 - a_1 Q_1} {Q_1}$ $\ds \leadsto \ \$ $\ds x_2$ $=$ $\ds \dfrac {Q_1} {\sqrt n - \left({a_1 Q_1 - P_1}\right) }$ $\ds$ $=$ $\ds \dfrac {Q_1} {\sqrt n - P_2}$ Definition of $P_2$ $\ds$ $=$ $\ds \dfrac {Q_1 \left({\sqrt n + P_2}\right)} {\left({\sqrt n - P_2}\right) \left({\sqrt n + P_2}\right)}$ multiplying top and bottom by $\sqrt n + P_2$ $\ds$ $=$ $\ds \dfrac {Q_1 \left({\sqrt n + P_2}\right)} {n - {P_2}^2}$ Difference of Two Squares $\ds$ $=$ $\ds \dfrac {\sqrt n + P_2} {\left({n - {P_2}^2}\right) / Q_1}$ By Expansion of Associated Reduced Quadratic Irrational, $\left({n - {P_2}^2}\right) / Q_1$ is an integer $\ds$ $=$ $\ds \dfrac {\sqrt n + P_2} {Q_2}$ Definition of $Q_2$

By definition of the structure of a continued fraction:

$x_2 = a_2 + \dfrac 1 {x_3}$

for some $a_2 \in \Z$ and $x_3 \in \R_{>0}$.

Thus:

 $\ds a_2$ $=$ $\ds \left\lfloor{\dfrac {\sqrt n + P_2} {Q_2} }\right\rfloor$ Definition of Floor Function $\ds$ $=$ $\ds \left\lfloor{\dfrac {\left\lfloor{\sqrt n}\right\rfloor + P_2} {Q_2} }\right\rfloor$ Floor of $\dfrac {x + m} n$

This is the basis for the induction.

### Induction Hypothesis

Now it needs to be shown that, if $P \left({k - 1}\right)$ and $P \left({k}\right)$ ares true, for all $k \ge 2$, then it logically follows that $P \left({k + 1}\right)$ is true.

This is the induction hypothesis:

$a_k = \left\lfloor{\dfrac{a_0 + P_k} {Q_k} }\right\rfloor$

where:

$P_k = a_{k - 1} Q_{k - 1} - P_{k - 1}$
$Q_k = \dfrac {n - {P_k}^2} {Q_{k - 1} }$

and:

$x_k = \dfrac{\sqrt n + P_k} {Q_k}$

from which it is to be shown that:

$a_{k + 1} = \left\lfloor{\dfrac{a_0 + P_{k + 1} } {Q_{k + 1} } }\right\rfloor$

where:

$P_{k + 1} = a_k Q_k - P_k$
$Q_{k + 1} = \dfrac {n - {P_{k + 1} }^2} {Q_k}$

and:

$x_{k + 1} = \dfrac{\sqrt n + P_{k + 1} } {Q_{k + 1} }$

### Induction Step

This is the induction step:

By definition of the structure of a continued fraction:

$x_k = a_k + \dfrac 1 {x_{k+1} }$

where:

$x_{k+1} \in \R_{>0}$
$a_k = \left\lfloor{\dfrac{a_0 + P_k} {Q_k} }\right\rfloor$

by the induction hypothesis.

Then:

 $\ds \dfrac 1 {x_{k+1} }$ $=$ $\ds x_k - a_k$ $\ds$ $=$ $\ds \dfrac {\sqrt n + P_k} {Q_k} - a_k$ $\ds$ $=$ $\ds \dfrac {\sqrt n + P_k - a_k Q_k} {Q_k}$ $\ds \leadsto \ \$ $\ds x_2$ $=$ $\ds \dfrac {Q_k} {\sqrt n - \left({a_k Q_k - P_k}\right) }$ $\ds$ $=$ $\ds \dfrac {Q_k} {\sqrt n - P_{k + 1} }$ Definition of $P_{k + 1}$ $\ds$ $=$ $\ds \dfrac {Q_k \left({\sqrt n + P_{k + 1} }\right)} {\left({\sqrt n - P_{k + 1} }\right) \left({\sqrt n + P_{k + 1} }\right)}$ multiplying top and bottom by $\sqrt n + P_{k + 1}$ $\ds$ $=$ $\ds \dfrac {Q_k \left({\sqrt n + P_{k + 1} }\right)} {n - {P_{k + 1} }^2}$ Difference of Two Squares $\ds$ $=$ $\ds \dfrac {\sqrt n + P_{k + 1} } {\left({n - {P_{k + 1} }^2}\right) / Q_k}$ By Expansion of Associated Reduced Quadratic Irrational, $\left({n - {P_{k + 1} }^2}\right) / Q_k$ is an integer $\ds$ $=$ $\ds \dfrac {\sqrt n + P_{k + 1} } {Q_{k + 1} }$ Definition of $Q_{k + 1}$

By definition of the structure of a continued fraction:

$x_{k + 1} = a_{k + 1} + \dfrac 1 {x_{k + 2} }$

for some $a_{k + 1} \in \Z$ and $x_{k + 2} \in \R_{>0}$.

Thus:

 $\ds a_{k + 1}$ $=$ $\ds \left\lfloor{\dfrac {\sqrt n + P_{k + 1} } {Q_{k + 1} } }\right\rfloor$ Definition of Floor Function $\ds$ $=$ $\ds \left\lfloor{\dfrac {\left\lfloor{\sqrt n}\right\rfloor + P_{k + 1} } {Q_{k + 1} } }\right\rfloor$ Floor of $\dfrac {x + m} n$

So $P \left({k}\right) \implies P \left({k + 1}\right)$ and the result follows by the Second Principle of Mathematical Induction.

Hence the result.

$\blacksquare$