Number Theory Home

## Continued Fractions

A finite continued fraction is a fraction of the form $a_0+\cfrac{1}{a_1 + \cfrac{1}{a_2 + \cfrac{1}{ \llap{\ddots} a_{n-2}+\cfrac{}{ a_{n-1} + \cfrac{1}{a_n}}}}}$ for some real numbers $$a_0,a_1,a_2,\ldots,a_n$$ where $$a_i>0$$ for $$i=1,2,\ldots,n$$. It is denoted by $$[a_0,a_1,a_2,\ldots,a_n]$$. A continued fraction is called simple if $$a_0,a_1,a_2,\ldots,a_n$$ are integers.

Example.

1. $[5,2,3,2]=5+\cfrac{1}{2+\cfrac{1}{3+\cfrac{1}{2}}}.$ We can verify that $$[5,2,3,2]=\frac{87}{16}$$. Similarly we can show that any finite simple continued fraction is a rational number.

2. Let us write $$\frac{1479}{17}$$ as a finite simple continued fraction. We follow steps similar to the Euclidean Algorithm: \begin{align*} \frac{1479}{272} &=5+\frac{119}{272}=5+\cfrac{1}{\frac{272}{119}} &&\implies \frac{1479}{272}=5+\cfrac{1}{\frac{272}{119}}\\ \frac{272}{119} &=2+\frac{34}{119}=2+\cfrac{1}{\frac{119}{34}} &&\implies \frac{1479}{272}=5+\cfrac{1}{2+\cfrac{1}{\frac{119}{34}}}\\ \frac{119}{34} &=3+\frac{17}{34}=3+\frac{1}{2} &&\implies \frac{1479}{272}=5+\cfrac{1}{2+\cfrac{1}{3+\cfrac{1}{2}}} \end{align*} So $$\frac{1479}{272}=[5,2,3,2]$$. Similarly we can show that any rational number can be written as a finite simple continued fraction.

Observation. A real number is a rational number if and only if it can be written as a finite simple continued fraction.

An infinite continued fraction is a fraction of the form $a_0+\cfrac{1}{a_1 + \cfrac{1}{a_2 + \cfrac{1}{ \llap{\ddots} {\:\:}}}}$ for infinitely many real numbers $$a_0,a_1,a_2,\ldots$$ where $$a_i>0$$ for $$i=1,2,\ldots$$. It is denoted by $$[a_0,a_1,a_2,\ldots]$$. An irrational number expressed by an infinite continued fraction $$[a_0,a_1,a_2,\ldots]$$ can be approximated by its truncated form $$[a_0,a_1,a_2,\ldots,a_n]$$ for some $$n\geq 0$$ which is called the $$n$$th convergent of $$[a_0,a_1,a_2,\ldots]$$, denoted by $$C_n$$. It can be proved that $$\displaystyle\lim_{n\to \infty} C_n$$ exists and is equal to $$[a_0,a_1,a_2,\ldots]$$ using the following fact: $C_0< C_2< C_4<\cdots< C_{2n}<\cdots< C_{2n+1}<\cdots< C_5< C_3< C_1.$

Example.

1. $$\pi=[3,7,15,1,292,1,1,1,2,1,3,1,\ldots]$$.
$$\pi$$ can be approximated by $$C_0=[3]=3$$, $$C_1=[3,7]=\frac{22}{7}$$, $$C_2=[3,7,15]=\frac{333}{106}$$ etc.

2. $$e=[2,1,2,1,1,4,1,1,6,1,1,8,1,1,10,\ldots]$$.
Notice the interesting pattern.

3. $$\phi=[1,1,1,\ldots]=[\overline{1}]$$.
Note that $$x=[1,1,1,\ldots]=[1,x]=1+\frac{1}{x}$$. Then $$x^2-x-1=0\implies x=(1\pm \sqrt{5})/2$$. Since $$x>0$$, $$x=(1+\sqrt{5})/2=\phi$$, the golden ratio.

4. $$\sqrt{2}=[1,2,2,2,\ldots]=[1,\overline{2}]$$.
Note that $$(\sqrt{2}-1)(\sqrt{2}+1)=2-1=1\implies \sqrt{2}=1+\cfrac{1}{1+\sqrt{2}}$$. Repeating this process, we get $\sqrt{2}=1+\cfrac{1}{1+\sqrt{2}} =1+\cfrac{1}{2+\cfrac{1}{1+\sqrt{2}}} =1+\cfrac{1}{2+\cfrac{1}{2+\cfrac{1}{1+\sqrt{2}}}} =\cdots=[1,2,2,2,\ldots].$

We get the continued fraction of an irrational number $$n$$ by the continued fraction algorithm:
With $$x_0=n$$, recursively define $$x_{k+1}=\frac{1}{x_k-\left\lfloor x_k \right\rfloor}, \;k\geq 0$$. Now define $$a_k=\left\lfloor x_k \right\rfloor$$, $$k=0,1,2,\ldots$$. Then $$n=x_0=[a_0,a_1,a_2,\ldots]$$. For a rough justification, note that for $$k=0,1,2,\ldots$$, $$x_{k+1}=\frac{1}{x_k-a_k} \implies x_k=a_k+\cfrac{1}{x_{k+1}}$$. Thus $x_0 =a_0+\cfrac{1}{x_1} =a_0+\cfrac{1}{a_1+\cfrac{1}{x_2}} =a_0+\cfrac{1}{a_1+\cfrac{1}{a_2+\cfrac{1}{x_3}}}=\cdots$

Example. Let us find the continued fraction of $$\sqrt{2}$$. $\begin{array}{ll} x_0=\sqrt{2} &\implies a_0=\left\lfloor x_0\right\rfloor=1\\ x_1=\frac{1}{x_0-\left\lfloor x_0 \right\rfloor}=\frac{1}{\sqrt{2}-1}=\frac{\sqrt{2}+1}{(\sqrt{2}-1)(\sqrt{2}+1)}=\sqrt{2}+1 &\implies a_1=\left\lfloor x_1\right\rfloor=2\\ x_2=\frac{1}{x_1-\left\lfloor x_1\right\rfloor}=\frac{1}{(\sqrt{2}+1)-2}=\frac{\sqrt{2}+1}{(\sqrt{2}-1)(\sqrt{2}+1)}=\sqrt{2}+1 &\implies a_2=\left\lfloor x_2\right\rfloor=2\\ \hspace{4pt}\vdots & \hspace{32pt}\vdots \end{array}$ So $$\sqrt{2}=[1,2,2,2,\ldots]$$.

Last edited