Continued fraction expansion of irrational numbers

In this section we use continued fractions for expansion of irrational numbers.

Theorem 1. Let $\displaystyle (x_n)_{n\geq 0}$ be a sequence of intergers with $\displaystyle x_i>0$ for every $\displaystyle i>0$ . Then the sequence $\displaystyle (p_n/q_n)_{n\geq 0}$ is a convergent sequence, and the its limit is an irrational number. We denote this limit by $\displaystyle [x_0;x_1,x_2,\ldots]$ .

Proof. From [1] we have $\displaystyle q_1\geq q_0=1>0$ and for all $\displaystyle n>1$ , $\displaystyle q_n=x_nq_{n-1}+q_{n-2},$ hence by induction on $\displaystyle n$ , $\displaystyle q_{n+1}>q_n$ for every $\displaystyle n\geq 1$ . Therefore $\displaystyle\lim_{n\to \infty}q_n=\infty$ .

By the Proposition 4 in [1], for all $\displaystyle n\geq 0$ ,

$\displaystyle \frac{p_n}{q_n}-\frac{p_{n+1}}{q_{n+1}}=\frac{(-1)^{n-1}}{q_nq_{n+1}},\quad\quad (1)$

hence $\displaystyle \frac{p_n}{q_n}-\frac{p_{n+2}}{q_{n+2}}=\frac{(-1)^{n-1}(q_{n+2}-q_n)}{q_nq_{n+1}q_{n+2}},\quad \forall n\geq 0.$ Therefore

$\displaystyle \frac{p_1}{q_1}>\frac{p_3}{q_3}>\frac{p_5}{q_5}>\ldots>\frac{p_0}{q_0}$

and

$\displaystyle \frac{p_0}{q_0}<\frac{p_2}{q_2}<\frac{p_4}{q_4}<\ldots<\frac{p_1}{q_1},$

hence $\displaystyle (p_{2n}/q_{2n})_{n\geq 0}$ and $\displaystyle (p_{2n+1}/q_{2n+1})_{n\geq 0}$ are convergent sequences. By (1) and $\displaystyle q_n\to\infty$ we have

$\displaystyle\lim_{n\to\infty}\frac{p_{2n}}{q_{2n}}=\lim_{n\to\infty}\frac{p_{2n+1}}{q_{2n+1}},$ so $\displaystyle (p_n/q_n)_{n\geq 0}$ is a convergent sequence.

Now we prove $\displaystyle \displaystyle \alpha:=\lim_{n\to\infty}\frac{p_n}{q_n}$ is an irrational number. We have

$\displaystyle \frac{p_{2m}}{q_{2m}}<\alpha<\frac{p_{2n+1}}{q_{2n+1}},\quad\forall m,n\geq 0.$

Thus, by (1),

$\displaystyle\left|\alpha-\frac{p_{2n}}{q_{2n}}\right|\leq \frac{1}{q_{2n}q_{2n+1}}<\frac{1}{q_{2n}^2},\quad\forall n\geq 1.$

By the Proposition 2 in [1], $\displaystyle p_{2n}$ and $\displaystyle q_{2n}$ are coprime integers for every $\displaystyle n\geq 1$ , hence there are infinite rational numbers $\displaystyle r/s$ , with $\displaystyle s>0$ and $\displaystyle (r,s)=1$ , such that

$\displaystyle \left|\alpha-\frac{r}{s}\right| <\frac{1}{s^2}.\quad\quad (2)$

Assume that $\displaystyle \alpha$ is rational and write $\displaystyle \alpha=p/q$ , where $\displaystyle p$ and $\displaystyle q>0$ are coprime integers. For all positive integers $\displaystyle s$ , at most two integers $\displaystyle r$ satisfy the equation (2), hence there are coprime integers $\displaystyle r_0$ and $\displaystyle s_0>q$ such that

$\displaystyle\left|\frac{p}{q}-\frac{r_0}{s_0}\right| <\frac{1}{s_0^2}.$

From the inequality we have $\displaystyle \mid ps_0-qr_0\mid <1$ , hence $\displaystyle ps_0=qr_0$ , a contradiction. Therefore $\displaystyle \alpha$ is an irrational number. $\Box$

Theorem 2. Let $\displaystyle \alpha$ be an irrational number. Then there is a unique sequence of integers $\displaystyle (a_n)_{n\geq 0}$ such that

(1) $\displaystyle a_i>0$ for every $\displaystyle i>0$ .

(2) $\displaystyle \alpha =[a_0;a_1,a_2,\ldots]$ .

Proof. In this proof, $\displaystyle [x]$ is the integer part of $\displaystyle x$ . Because $\displaystyle \alpha$ is an irrational number, we have $\displaystyle [\alpha]<\alpha<[\alpha]+1$ , hence there is a real number $\displaystyle u_1>1$ such that

$\displaystyle \alpha=[\alpha]+\frac{1}{u_1}.$

Because $\displaystyle \alpha$ is an irrational and $\displaystyle [\alpha]$ is an integer, $\displaystyle u_1$ is an irrational number. Hence there is an irrational number $\displaystyle u_2>1$ such that

$\displaystyle u_1=[u_1]+\frac{1}{u_2},$

and so on. Therefore we have real numbers $\displaystyle u_0:=\alpha$ , $u_1>1$ , $\displaystyle u_2>1$ , $\displaystyle \ldots$ such that $\displaystyle u_i$ is irrationals for every $\displaystyle i>0$ and

$\displaystyle u_k=[u_k]+\frac{1}{u_{k+1}},\quad\forall k\geq 0.$

We claim that $\displaystyle \alpha=[[u_0];[u_1],[u_2],\ldots]$ . Fix a $\displaystyle k>2$ . We have

$\displaystyle \alpha=[[u_0];[u_1],\ldots, [u_k],u_{k+1}].$

Hence, by Proposition 4 in [1],

$\displaystyle \left|\alpha-\frac{p_k}{q_k}\right|=\frac{1}{q_k(u_{k+1}q_{k}+q_{k-1})}<\frac{1}{q_k^2},$

so $\displaystyle \lim_{n\to\infty}\frac{p_n}{q_n}=\alpha$ . Now assume that

$\displaystyle \alpha =[a_0;a_1,a_2,\ldots]=[b_0;b_1,b_2,\ldots],$

where $\displaystyle (a_n)_{n\geq 0}$ and $\displaystyle (b_n)_{n\geq 0}$ are two sequences of integers such that $\displaystyle a_i>0$ and $\displaystyle b_i>0$ for every $\displaystyle i>0$ .

Because

$\displaystyle [a_0;a_1,a_2,\ldots,a_{n}]=a_0+\frac{1}{[a_1;a_2,\ldots,a_n]},\quad\forall n\geq 0,$

we have

$\displaystyle [a_0;a_1,a_2,\ldots]=a_0+\frac{1}{[a_1;a_2,\ldots]}.$

Hence $\displaystyle a_0=b_0=[\alpha]$ and $\displaystyle [a_1;a_2,a_3,\ldots] = [b_1;b_2,b_3,\ldots]$ . Similarly, $\displaystyle a_1=b_1$ and

$\displaystyle [a_2;a_3,a_4,\ldots] = [b_2;b_3,b_4,\ldots],$

and so on. Therefore $\displaystyle a_i=b_i$ for every $i$ . $\Box$

The equality in the theorem is called an expansion of $\displaystyle \alpha$ into a infinite continued fraction. In that expansion we will call $\displaystyle [a_0;a_1,a_2,\ldots,a_i]$ is the $\displaystyle i-$ th convergent of the continued fraction, or $\displaystyle i-$ th convergent of $\displaystyle \alpha$ . The theorem says that for every irrational number has an expansion into a infinite continued fraction, and this expansion is unique.

Example 1. $\displaystyle \sqrt{2}=[1;2,2,\ldots]$ .

Example 2. The golden ratio $\displaystyle\varphi:=\frac{1+\sqrt{5}}{2}=[1;1,1,\ldots]$ .

Example 3. $\displaystyle e=[2;1,2,1,1,4,1,1,6,1,1,8,\ldots]$ .

A sequence $\displaystyle (a_n)_{n\geq 0}$ is called eventually periodic if $\displaystyle a_{n+T}=a_n$ for some positive integer $\displaystyle T$ and sufficiently large $\displaystyle n$ . A real number is called quadratic irrational number, if there is a polynomial $\displaystyle P(x)$ is of degree two with rational coefficients such that $\displaystyle P(x)$ is an irreducible polynomial (see [3]) over the rational numbers and $\displaystyle \alpha$ is a root of $\displaystyle P(x)$ .

Theorem 3. Let $\displaystyle \alpha$ be an irrational number and $\displaystyle \alpha =[a_0;a_1,a_2,\ldots]$ is the expansion of $\displaystyle\alpha$ into a infinite continued fraction. Then $\displaystyle (a_n)_{n\geq 1}$ is eventually periodic if and only if $\displaystyle \alpha$ is a quadratic irrational.

References

[1] https://nttuan.org/2008/10/12/continued-fractions-the-basics/

[2] https://nttuan.org/2008/11/14/continued-fraction-expansion-of-rational-numbers/

[3] https://nttuan.org/2009/01/11/poly02/

Continued fraction expansion of rational numbers

In this section we use continued fractions ([2]) for expansion of rational numbers. If $\displaystyle x_0$ , $\displaystyle x_1$ , $\displaystyle \ldots$ , are integer nunbers with $\displaystyle x_i>0$ for every $\displaystyle i>0$ then $\displaystyle [x_0;x_1,x_2,\ldots,x_n]\in\mathbb{Q},\quad\forall n\geq 0.$

Conversly, we have the theorem

Theorem 1. Let $\displaystyle r$ and $\displaystyle s$ be coprime integers with $\displaystyle s>0$ . Then there are non negative integer $\displaystyle n$ and integers $\displaystyle a_0$ , $\displaystyle a_1$ , $\displaystyle \ldots$ , $\displaystyle a_n$ such that

(1) $\displaystyle a_i>0$ for every $\displaystyle i=1,2,\ldots,n$ .

(2) $\displaystyle r/s=[a_0;a_1,a_2,\ldots,a_n]$ .

Proof. Let us proceed by induction on $\displaystyle s$ . The case $\displaystyle s=1$ is trivial. Now suppose that the assertion is true for all positive integers up to $\displaystyle s-1$ ( $\displaystyle s>1$ ). Because $\displaystyle (r,s)=1$ and $\displaystyle s>1$ , we have $\displaystyle s\nmid r$ . Hence by the Division Algorithm ([1]), there are integers $\displaystyle a$ and $\displaystyle b$ such that

$\displaystyle r=sa+b,\quad 1\leq b<s.\quad\quad (1)$

By the hypothesis of the induction, there are integers $\displaystyle m>0$ , $\displaystyle a_1$ , $\displaystyle a_2>0$ , $\displaystyle \ldots$ , $\displaystyle a_m>0$ such that

$\displaystyle \frac{s}{b}=[a_1;a_2,a_3,\ldots,a_m].\quad\quad (2)$

Because $\displaystyle s>b$ , we have $\displaystyle a_1>0$ . From (1) and (2) we have

$\displaystyle \frac{r}{s}=a+\frac{1}{s/b}=a+\frac{1}{[a_1;a_2,a_3,\ldots,a_m]}=[a;a_1,a_2,\ldots,a_m],$ completing the induction step. $\Box$

The equality in the theorem is called an expansion of $\displaystyle r/s$ into a finite continued fraction. In that expansion we will call $\displaystyle [a_0;a_1,a_2,\ldots,a_i]$ is the $i-$ th convergent of the continued fraction, or $i-$ th convergent of $\displaystyle r/s$ .

Example 1. Find an expansion of $\displaystyle 43/5$ into a finite continued fraction.

Solution. By the Division Algorithm, we have

$\displaystyle 43=5\cdot 8+3\quad\quad\frac{43}{5}=8+\frac{3}{5}=8+\frac{1}{5/3},$ and

$\displaystyle 5= 3\cdot 1 +2\quad\quad\frac{5}{3}=1+\frac{2}{3}=1+\frac{1}{3/2},$ and $\displaystyle \frac{3}{2}=1+\frac{1}{2}$ . Therefore $\displaystyle 43/5=[8;1,1,2]$ . $\Box$

The theorem says that for every rational number has an expansion into a finite continued fraction. But this expansion is not unique.

Example 2. $\displaystyle 13/5=[2;1,1,2]=[2;1,1,1,1]$ . $\Box$

Theorem 2. Let $\displaystyle \alpha$ be an integer number. Then $\displaystyle \alpha$ has exactly two expansions into a finite continued fraction.

Proof. By the theorem 1, we can write

$\displaystyle \alpha=[a_0;a_1,a_2,\ldots,a_n],$

where $a_0$ , $a_1$ , $\ldots$ , $a_n$ are integers such that $a_i>0$ for every $i=1,2,\ldots,n$ . If $\displaystyle n=0$ then $\displaystyle \alpha=a_0$ and $\displaystyle \alpha=[\alpha]$ is an expansion of $\displaystyle \alpha$ . If $\displaystyle n=1$ then $\displaystyle \alpha=a_0+\frac{1}{a_1}$ , hence $\displaystyle \frac{1}{a_1}$ is an integer, so $\displaystyle a_1=1$ . Therefore $\displaystyle \alpha=[\alpha-1;1]$ is an expansion of $\displaystyle \alpha$ .

Now assume that $\displaystyle n\geq 2$ . We have

$\displaystyle \alpha-a_0=\frac{1}{[a_1;a_2,\ldots,a_n]}$

is an integer number and $\displaystyle [a_1;a_2,\ldots,a_n]>0$ , hence $\displaystyle [a_1;a_2,\ldots,a_n]\leq 1$ . This claim is false because $\displaystyle n\geq 2$ and $\displaystyle a_i\geq 1$ for every $\displaystyle i=1,2,\ldots,n$ . $\Box$

Theorem 3. Let $\displaystyle \alpha$ be a rational number but not an integer. Then $\displaystyle \alpha$ has exactly two expansions into a finite continued fraction.

Proof. Assume that $\displaystyle \alpha=\alpha=r/s$ , where $\displaystyle r$ and $\displaystyle s>1$ are coprime integers. We prove by induction on $\displaystyle s$ that $\displaystyle \alpha$ has exactly two expansions into a finite continued fraction

$\displaystyle \alpha=[a_0;a_1,\ldots,a_n]=[a_0;a_1,\ldots,a_n-1,1],$

where $\displaystyle a_n>1$ . If $\displaystyle s=2$ , because $\displaystyle (r,s)=1$ there is an integer $\displaystyle k$ such that $\displaystyle r=2k+1$ . By the theorem 1, we can write

$\displaystyle \alpha=k+\frac{1}{2}=[a_0;a_1,a_2,\ldots,a_n],$

where $a_0$ , $a_1$ , $\ldots$ , $a_n$ are integers such that $a_i>0$ for every $i=1,2,\ldots,n$ . We have $n>0$ and $a_0=k$ , hence $\displaystyle 2=[a_1;a_2,\ldots,a_n]$ . By the theorem 2, we have $2$ has exactly two expansions into a finite continued fraction, those are $2=[2]$ and $2=[1;1]$ , therefore $\alpha$ has exactly two expansions $\displaystyle \alpha=[k;2]=[k;1,1],$ hence the claim is true for $\displaystyle s=2$ . Now suppose that the claim is true for $\displaystyle 2$ , $\displaystyle 3$ , $\displaystyle \ldots$ , $\displaystyle s-1$ ( $\displaystyle s>2$ ). By the theorem 1, we can write

$\displaystyle \alpha=[a_0;a_1,a_2,\ldots,a_n],$

where $a_0$ , $a_1$ , $\ldots$ , $a_n$ are integers such that $a_i>0$ for every $i=1,2,\ldots,n$ . We have $n>0$ and $a_0=[\alpha]$ (integer part of $\alpha$ ), hence $\displaystyle \frac{1}{\alpha-[\alpha]}=[a_1;a_2,\ldots,a_n].$ By the Division Algorithm, there is an integer $\displaystyle a$ such that $\displaystyle r=s[\alpha]+a$ and $1\leq a<s$ , then

$\displaystyle \frac{s}{a}=[a_1;a_2,\ldots,a_n].$

If $a=1$ then $a_1>1$ and by the theorem 2, we have $s/a$ has exactly two expansions are $s/a=[a_1]$ and $\displaystyle s/a=[a_1-1;1]$ . If $\displaystyle a>1$ then by the hypothesis of the induction (note that $\displaystyle s$ and $\displaystyle a$ are coprime integers), $\displaystyle s/a$ has exactly two expansions are

$\displaystyle \frac{s}{a}=[a_1;b_2,\ldots,b_n]=[a_1;b_2,\ldots,b_n-1,1],$

where $\displaystyle b_n>1$ . Therefore $\displaystyle \alpha$ has exactly two expansions, and the claim is true for $\displaystyle s$ . $\Box$

References

[1] https://nttuan.org/2020/01/14/divisibility/

[2] https://nttuan.org/2008/11/14/continued-fraction-expansion-of-rational-numbers/

Continued fractions: The basics

Let $x_0$ , $\displaystyle x_1$ , $\displaystyle x_2$ , $\displaystyle \ldots$ be variables. We define two sequences of polynomials with complex coefficients $\displaystyle \{p_n\}_{n\geq 0}$ and $\displaystyle \{q_n\}_{n\geq 0}$ by conditions following:

(1) For all non negative integer $\displaystyle n$ , $\displaystyle p_n$ and $\displaystyle q_n$ are polynomials in $\displaystyle x_0,x_1,\ldots,x_n$ .

(2) $\displaystyle p_0=x_0$ and $\displaystyle q_0=1$ .

(3) For all positive integer $\displaystyle n$ , $\displaystyle p_n=x_0p_{n-1}(x_1,x_2,\ldots,x_n)+q_{n-1}(x_1,x_2,\ldots,x_n)$ and

$\displaystyle q_n=p_{n-1}(x_1,x_2,\ldots,x_n)$ .

Example. We have

$\displaystyle p_1=x_0x_1+1$ and $\displaystyle q_1=x_1$ , therefore $\displaystyle \frac{p_1}{q_1}=x_0+\frac{1}{x_1}$ .

$\displaystyle p_2=x_0x_1x_2+x_0+x_2$ and $\displaystyle q_2=x_1x_2+1$ , hence

$\displaystyle \frac{p_2}{q_2}=x_0+\frac{x_2}{x_1x_2+1}=x_0+\cfrac{1}{x_1+\cfrac{1}{x_2}}. \Box$

For all non negative integer $\displaystyle n$ we have

$\displaystyle [x_0;x_1,x_2,\ldots,x_n]:=\frac{p_n}{q_n}=x_0+\cfrac{1}{x_1+\cfrac{1}{x_2+\cfrac{1}{x_3+\cdots+\cfrac{1}{x_{n-1}+\cfrac{1}{x_n}}}}}.$

A rational function of this form is called a continued fraction.

Proposition 1. For all $\displaystyle n>1$ , we have $\displaystyle p_n=x_np_{n-1}+p_{n-2}$ and $\displaystyle q_n=x_nq_{n-1}+q_{n-2}.$

Proof. We use induction on $\displaystyle n$ . From the above example we have the assertion is true for $\displaystyle n=2$ . Now suppose that the assertion has been established for $\displaystyle n-1$ ( $\displaystyle n>2$ ). Then we have

$\displaystyle p_{n-1}(x_1,x_2,\ldots,x_n)=x_np_{n-2}(x_1,x_2,\ldots,x_{n-1})+p_{n-3}(x_1,x_2,\ldots,x_{n-2})$

and

$\displaystyle q_{n-1}(x_1,x_2,\ldots,x_n)=x_nq_{n-2}(x_1,x_2,\ldots,x_{n-1})+q_{n-3}(x_1,x_2,\ldots,x_{n-2}).$

Therefore by define of $\displaystyle \{p_n\}$ and $\displaystyle \{q_n\}$ ,

$\displaystyle p_n=x_0p_{n-1}(x_1,x_2,\ldots,x_n)+q_{n-1}(x_1,x_2,\ldots,x_n)=x_np_{n-1}+p_{n-2},$

and $\displaystyle q_n=x_nq_{n-1}+q_{n-2}$ . Thus the assertion is true for $\displaystyle n$ . $\Box$

For convenience, we define $\displaystyle p_{-2}=0$ , $\displaystyle p_{-1}=1$ , $\displaystyle q_{-2}=1$ , and $\displaystyle q_{-1}=0$ .

Proposition 2. For all $\displaystyle n>-2$ , we have $\displaystyle p_nq_{n-1}-q_np_{n-1}=(-1)^{n-1}$ .

Proof. We prove by induction on $\displaystyle n$ . The case $\displaystyle n=-1$ is trivial. Now suppose that the assertion is true for $\displaystyle n-1$ ( $\displaystyle n\geq 0$ ). Then by proposition 1, we have

$\displaystyle p_nq_{n-1}-q_np_{n-1}=(x_np_{n-1}+p_{n-2})q_{n-1}-(x_nq_{n-1}+q_{n-2})p_{n-1}$

$=-(p_{n-1}q_{n-2}-q_{n-1}p_{n-2})=(-1)^{n-1}.$

Therefore the assertion is true for $\displaystyle n-1$ . $\Box$

Proposition 3. For all $\displaystyle n>-1$ , we have $\displaystyle p_nq_{n-2}-q_np_{n-2}=(-1)^nx_n$ .

Proof. Assume $\displaystyle n>-1$ is an integer number. By propositions 1 and 2, we have

$\displaystyle p_nq_{n-2}-q_np_{n-2}=(x_np_{n-1}+p_{n-2})q_{n-2}-(x_nq_{n-1}+q_{n-2})p_{n-2}$ $=x_n(p_{n-1}q_{n-2}-q_{n-1}p_{n-2})=(-1)^nx_n. \Box$

Proposition 4. If $\displaystyle n\geq 0$ and $\displaystyle \theta:=[x_0;x_1,x_2,\ldots,x_{n+1}]$ then $\displaystyle p_n-\theta q_n=\frac{(-1)^{n-1}}{q_{n+1}}.$