Rational Number can be Expressed as Simple Finite Continued Fraction

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $q \in \Q$ be a rational number.

Then $q$ can be expressed as a simple finite continued fraction.


Proof

Let $q = \dfrac a b$ be a rational number expressed in canonical form.

That is $b > 0$ and $a \perp b = 1$.

By the Euclidean Algorithm, we have:

\(\ds a\) \(=\) \(\ds q_1 b + r_1,\) \(\ds 0 < r_1 < b\) or $\dfrac a b = q_1 + \dfrac {r_1} b$
\(\ds b\) \(=\) \(\ds q_2 r_1 + r_2,\) \(\ds 0 < r_2 < r_1\) or $\dfrac b {r_1} = q_2 + \dfrac {r_2} {r_1}$
\(\ds r_1\) \(=\) \(\ds q_3 r_2 + r_3,\) \(\ds 0 < r_3 < r_2\) or $\dfrac {r_2} {r_1} = q_3 + \dfrac {r_3} {r_2}$
\(\ds \) \(\vdots\) \(\ds \)
\(\ds r_{n-3}\) \(=\) \(\ds q_{n - 1} r_{n - 2} + r_{n - 1},\) \(\ds 0 < r_{n - 1} < r_{n - 2}\) or $\dfrac {r_{n - 3} } {r_{n - 2} } = q_{n - 1} + \dfrac {r_{n - 1} } {r_{n - 2} }$
\(\ds r_{n - 2}\) \(=\) \(\ds q_n r_{n - 1} + 0,\) or $\dfrac {r_{n - 2} } {r_{n - 1} } = q_n$

Thus from the system of equations on the right hand side, we get:

\(\ds \frac a b\) \(=\) \(\ds q_1 + \cfrac 1 {\frac b {r_1} }\)
\(\ds \) \(=\) \(\ds q_1 + \cfrac 1 {q_2 + \cfrac 1 {\frac {r_1} {r_2} } }\)
\(\ds \) \(=\) \(\ds q_1 + \cfrac 1 {q_2 + \cfrac 1 {q_3 + \cfrac 1 {\frac {r_2} {r_3} } } }\)
\(\ds \) \(\cdots\) \(\ds \)
\(\ds \) \(=\) \(\ds q_1 + \cfrac 1 {q_2 + \cfrac 1 {q_3 + \cfrac 1 {\ddots \cfrac {} {q_{n - 1} + \cfrac 1 {q_n} } } } }\)

This shows that $q$ has the SFCF $\sqbrk {q_1, q_2, q_3, \ldots, q_n}$.

$\blacksquare$


Note



It can be seen from this proof that there is a close connection between continued fractions and the Euclidean Algorithm.


Sources