Number theory/Signed Articles/Elementary diophantine approximations

The theory of diophantine approximations is a chapter of number theory, which in turn is a part of mathematics. It studies the approximations of real numbers by rational numbers. This article presents an elementary introduction to diophantine approximations, as well as an introduction to number theory via diophantine approximations.

Introduction

In the everyday life our civilization applies mostly (finite) decimal fractions $\ {\frac {k}{10^{n}}}.$  Decimal fractions are used both as certain values, e.g. $5.85, and as approximations of the real numbers, e.g. $\ \pi \approx 3.14159.$  However, the field of all rational numbers is much richer than the ring of the decimal fractions (or of the binary fractions $\ {\frac {k}{2^{n}}},$  which are used in the computer science). For instance, the famous approximation $\ \pi \approx {\frac {355}{113}}$  has denominator 113 much smaller than 10⁵ but it provides a better approximation than the decimal one, which has five digits after the decimal point.

How well can real numbers (all of them or the special ones) be approximated by rational numbers? A typical Diophantine approximation result states:

Theorem  Let $\ a$  be an arbitrary real number. Then

• $\ a$  is rational if and only if there exists a real number C > 0 such that

$|a-{\frac {x}{y}}|>{\frac {C}{y}}$

for arbitrary integers $\ (x,y)$  such that $\ y>0$  and $\ a\neq {\frac {x}{y}};$

• (Adolph Hurwitz)   $\ a$  is irrational if and only if there exist infinitely many pairs of integers $\ (x,y)$  such that $\ y>0$  and

$|a-{\frac {x}{y}}|<{\frac {1}{{\sqrt {5}}\cdot y^{2}}}.$

Notation

• $\Leftarrow :\Rightarrow \$   —   "equivalent by definition" (i.e. "if and only if");
• $:=\$   —   "equals by definition";
• $\exists$   —   "there exists";
• $\forall$   —   "for all";
• $a\in A\$   —   "$a\$  is an element of set $\ A$";

 

• $\mathbb {N} \ :=\ \{1,2\dots \}$  —  the semiring of the natural numbers;
• $\mathbb {Z} _{+}\ :=\ \{0,1,\dots \}$  —  the semiring of the non-negative integers;
• $\mathbb {Z} \ :=\ \{-2,-1,1,2\dots \}$  —  the ring of integers;
• $\mathbb {Q}$  —  the field of rational numbers;
• $\mathbb {R}$  —  the field of real numbers;

 

• $(x;y)\ :=\{t\in \mathbb {R} :\,x<t<y\}$
• $|(x;y)|\ :=y-x$
• ${\mathit {Span}}(x,y)\ :=\ \left(\min \left(x,y\right);\,\max \left(x,y\right)\right)$

 

• $x|y\$   —   "$x\$  divides $\ y$"   (i.e. ${\frac {y}{x}}\in \mathbb {Z}$);
• $\gcd(a,b)\$  —  the greatest common divisor of integers $\ a$  and $\ b.$

 

The method of neighbors and median

In this section we will quickly obtain some results about approximating irrational numbers by rational (for the sake of simplicity only positive numbers will be considered). To this end we will not worry about the details of the difference between a rational number and a fraction (with integer numerator and denominator)—this will not cause any problems; fully crisp notions will be developed in the next sections, they will involve 2-dimensional vectors and 2x2 matrices. This section is still introductory. It is supposed to provide quick insight into the topic.

Fractions ${\frac {a}{c}}$  and ${\frac {b}{d}},$  with integer numerators and natural denominators, are called neighbors (in the given order)   $\Leftarrow :\Rightarrow$

${\frac {a}{c}}-{\frac {b}{d}}\ =\ {\frac {1}{c\cdot d}}$

Fraction ${\frac {a}{c}}$  is called the top neighbor of the other, ${\frac {b}{d}}$  is called the bottom neighbor, and the interval $\ {\mathit {Span}}({\frac {a}{c}},{\frac {b}{d}})$  is called neighborhood; thus a neighborhood is an open interval such that its endpoints are neighbors.

• If  ${\frac {a}{c}}$  and ${\frac {b}{d}}$  are neighbors then  $\ a\cdot b\geq 0$   ( i.e.  ${\frac {a}{c}}\cdot {\frac {b}{d}}\ \geq 0$ ).

• Let $\ a,b,c,d\in \mathbb {N} .$   Fractions ${\frac {a}{c}}$  and ${\frac {b}{d}}$  are neighbors   $\Leftrightarrow$   fractions ${\frac {d}{b}}$  and ${\frac {c}{a}}$  are neighbors.

Examples:

• Fractions ${\frac {n+1}{1}}$  and ${\frac {n}{1}}$  are neighbors for every positive integer $\ n.$

• Fractions ${\frac {1}{n}}$  and ${\frac {1}{n+1}}$  are neighbors for every positive integer $\ n.$

Thus it easily follows that for every positive irrational number $\ x$  there exists a pair of neighbors  ${\frac {a}{c}}$  and  ${\frac {b}{d}},$  with positive numerators and denominators, such that:

${\frac {a}{c}}\ >\ x\ >\ {\frac {b}{d}}$ 

First results

Theorem  Let fractions ${\frac {a}{c}}$  and ${\frac {b}{d}},$  with integer numerators and natural denominators, be neighbors. Then

• if integers $\ t>0$  and $\ s$  are such that   $\ {\frac {a}{c}}>{\frac {s}{t}}>{\frac {b}{d}},$   then   $t\geq b+d;$

• the median  ${\frac {a+b}{c+d}}$  is a bottom neighbor of  ${\frac {a}{c}},$  and a top neighbor of  ${\frac {b}{d}};$ 

• let  $\ x$  be an irrational number such that   ${\frac {a}{c}}\ >\ x\ >\ {\frac {b}{d}};$   then

$0\ <\ \max({\frac {a}{c}}-x,\,x-{\frac {b}{d}})\ <\ {\frac {1}{c\cdot d}}$

and

$0\ <\ {\frac {a}{c}}-x\ <\ {\frac {1}{c\cdot (c+1)}}$       or       $0\ <\ x-{\frac {b}{d}}\ <\ {\frac {1}{d\cdot (d+1)}}$

Proof   Let   $\ {\frac {a}{c}}>{\frac {s}{t}}>{\frac {b}{d}};$   then

${\frac {a}{c}}-{\frac {s}{t}}\ \geq \ {\frac {1}{c\cdot t}}$     and     ${\frac {s}{t}}-{\frac {b}{d}}\ \geq \ {\frac {1}{d\cdot t}}$

and

${\frac {1}{c\cdot t}}+{\frac {1}{d\cdot t}}\ \leq {\frac {1}{c\cdot d}}$

Multiplying this inequality by  $c\cdot d\cdot t\$ gives

$t\geq c+d$

which is the first part of our theorem.

The second part of the theorem is obtained by a simple calculation, straight from the definition of the neighbors.

the first inequality of the third part of the theorem is instant:

$\max({\frac {a}{c}}-x,\,x-{\frac {b}{d}})\ <\ ({\frac {a}{c}}-x)+(x-{\frac {b}{d}})\ =\ {\frac {1}{c\cdot d}}$

Next, either

${\frac {a}{c}}\ >\ x\ >\ {\frac {a+b}{c+d}}$

or

${\frac {a+b}{c+d}}\ >\ x\ >\ {\frac {b}{d}}$

and we get the respective required inequality in each case:

${\frac {a}{c}}-x\ <\ {\frac {1}{c\cdot (c+d)}}\ \leq \ {\frac {1}{c\cdot (c+1)}}$

or, respectively,

$x-{\frac {b}{d}}\ <\ {\frac {1}{d\cdot (c+d)}}\ \leq \ {\frac {1}{d\cdot (d+1)}}$

End of proof

 

Squeezing irrational numbers between neighbors

Let $\ x>0$  be an irrational number, We may always squeeze it between the extremal neighbours:

${\frac {1}{0}}\ >\ x\ >\ {\frac {0}{1}}$

But if you don't like infinity (on the left above) then you may do one of the two things:

$x>1\quad \quad \Rightarrow \quad \quad {\frac {n+1}{1}}>x>{\frac {n}{1}}$

or

$x<1\quad \quad \Rightarrow \quad \quad {\frac {1}{n}}>x>{\frac {1}{n+1}}$

where in each of these two cases  $\ n\in \mathbb {N}$   is a respective unique positive integer.

It was mentioned in the previous section (First results) that if fractions ${\frac {a}{c}}$  and ${\frac {b}{d}},$  with positive (or non-negative) integer numerators and denominators are neighbors then also the top and the bottom (bot  for short) pair:

• ${\mathit {top}}\!\left({\frac {a}{c}},{\frac {b}{d}}\right)\ :=\ \left({\frac {a}{c}},{\frac {a+b}{b+d}}\right)$

and

• ${\mathit {bot}}\!\left({\frac {a}{c}},{\frac {b}{d}}\right)\ :=\ \left({\frac {a+b}{c+d}},{\frac {b}{d}}\right)$

are both pairs of neighbors.

Let $\ A_{0}$  be a pair of neighbors, and $\ x\in {\mathit {Span}}(A_{0})$ — an irrational number. Assume that pairs of neighbors $\ A_{0},\dots ,A_{n-1}$  are already defined, and that they squeeze $\ x,$ i.e. that $\ x\in {\mathit {Span}}(A_{k})$  for each $\ k=0,\dots ,n-1.$  Then we define $\ A_{n}$  as the one of the two pairs: $\ {\mathit {top}}(A_{n-1})$  or  $\ {\mathit {bot}}(A_{n-1}),$  which squeezes $\ x.$  Thus for every positive irrational number we have obtained an infinite sequence of pairs of neighbors, each squeezing the given irrational number more and more. Thus for arbitrary irrational $\ x$  there exist fractions of integers $\ {\frac {s}{t}},$  with arbitrarily large denominators, such that

$\left|x-{\frac {s}{t}}\right|\ <\ {\frac {1}{t\cdot (t+1)}}$

(apply theorem from section First results). Let's get a sharper result:

First of all, since $\ x$ is irrational, the direction top-bottom of the sequence of pairs of neighbors changes infinitely many times, i.e.

$A_{n+1}={\mathit {top}}(A_{n}),\quad \quad A_{n+2}={\mathit {rgt}}(A_{n+1})$

for infinitely many values of  $n\in \mathbb {Z} _{+},$   and

$A_{n+1}={\mathit {bot}}(A_{n}),\quad \quad A_{n+2}={\mathit {lft}}(A_{n+1})$

for infinitely many values of  $n\in \mathbb {Z} _{+}$  as well. Thus there are infinitely many different $\ n$  of each of the two kinds. The other two kinds (which may or may not actually occur) are described by conditions:

$A_{n+1}={\mathit {top}}(A_{n}),\quad \quad A_{n+2}={\mathit {top}}(A_{n+1})$

and

$A_{n+1}={\mathit {bot}}(A_{n}),\quad \quad A_{n+2}={\mathit {bot}}(A_{n+1})$

Let $\ A_{n}:=({\frac {a}{c}},\,{\frac {b}{d}})$  be a pair of neighbors for which the top-top property above holds, i.e. for which $\ x$  is squeezed between a pair of neighbors as follows:

${\frac {a}{c}}\ >\ x\ >\ {\frac {2\cdot a+b}{2\cdot c+d}}$

Then

$0\ <\ {\frac {a}{c}}-x\ <\ {\frac {1}{c\cdot (2\cdot c+d)}}\ <\ {\frac {1}{2\cdot c^{2}}}$

Similarly, in the bot-bot case we get

$0\ <\ x-{\frac {b}{d}}\ <\ {\frac {1}{d\cdot (c+2\cdot d)}}\ <\ {\frac {1}{2\cdot d^{2}}}$

Thus if the top-top or the bot-bot case holds infinitely many times then there exist infinitely many fractions of natural numbers  ${\frac {s}{t}}$  such that:

$\left|x-{\frac {s}{t}}\right|\ <\ {\frac {1}{2\cdot t^{2}}}$

On the other hand, if cases top-top and bot-bot happen only finitely many times then starting with an $\ n$  we get an infinite alternating top-bot-top-bot-... sequence:

$A_{n+1}={\mathit {top}}(A_{n}),\quad A_{n+2}={\mathit {bot}}(A_{n+1}),\quad A_{n+3}={\mathit {top}}(A_{n+1})\quad \dots$

Then the new neighbor of the $\ A_{n+k}$  pair (i.e. the median of the previous pair $\ A_{n+k-1}$)  is equal to

$e_{k}\ :=\ {\frac {F_{k+1}\cdot a+F_{k}\cdot b}{F_{k+1}\cdot c+F_{k}\cdot d}}$

for every $\ k=1,2,\dots ,$  where $\ F_{t}$  are the Fibonacci numbers. It is known that

$\lim _{k\rightarrow \infty }{\frac {F_{k+1}}{F_{k}}}\ =\ \Phi \ :=\ {\frac {{\sqrt {5}}+1}{2}}$

hence

$x\ =\ \lim _{k\rightarrow \infty }e_{k}\ =\ {\frac {\Phi \cdot a+b}{\Phi \cdot c+d}}$

Thus

${\frac {a}{c}}-x\ =\ {\frac {1}{c\cdot (\Phi \cdot c+d)}}$

and

$x-{\frac {b}{d}}\ =\ {\frac {\Phi }{(\Phi \cdot c+d)\cdot d}}$

If  $\ d>{\frac {c}{\Phi }}$  then

$0\ <\ {\frac {a}{c}}-x\ <\ {\frac {1}{c^{2}}}\cdot {\frac {1}{\Phi +{\frac {1}{\Phi }}}}\ =\ {\frac {1}{{\sqrt {5}}\cdot c^{2}}}$

and if  $\ d<{\frac {c}{\Phi }},$  i.e.  $\ c>\Phi \cdot d,$  then

$0\ <\ x-{\frac {b}{d}}\ <\ {\frac {\Phi }{(\Phi ^{2}+1)\cdot d^{2}}}\ =\ {\frac {1}{{\sqrt {5}}\cdot d^{2}}}$

Since  ${\sqrt {(}}5)>2,$ and due to the earlier inequalities which have covered the top-top and the bot-bot cases, we have obtained the following theorem:

• for arbitrary irrational number there exist infinitely many different fractions $\ {\frac {s}{t}},$  with integer numerator and non-zero denominator, such that:

$\left|x-{\frac {s}{t}}\right|\ <\ {\frac {1}{2\cdot t^{2}}}$

However, we are close to replacing constant  $\ 2$  by  ${\sqrt {5}}$  in the above denominator. Let's do it:

 

Hurwitz theorem

• Let  $\ x\in \mathbb {R}$  be an arbitrary irrational number. Then

$\left|x-{\frac {s}{t}}\right|\ <\ {\frac {1}{{\sqrt {5}}\cdot t^{2}}}$

for infinitely many different $\ s,t\in \mathbb {Z} \backslash \{0\}.$

Proof of Hurwitz Theorem

Reduction to x > 0

Since

$\left|(-x)-{\frac {-s}{t}}\right|\ =\ \left|x-{\frac {s}{t}}\right|$

it is enough to prove Hurwitz theorem for positive irrational numbers only.

Two cases

Consider the sequence $\ \left(A_{n}\right)$  of pairs of neighbors, which squeeze $\ x>0,$  from the previous section. The case of the infinite alternation top-bot-top-bot-... has been proved already. In the remaining case the bot-bot-top or top-top-bot progressions appear infinitely many times, i.e. there are infinitely many non-negative integers $\ n$  for which

${\frac {a}{c}}\ >\ {\frac {a+b}{c+d}}\ >\ {\frac {a+2\cdot b}{c+2\cdot d}}\ >\ x\ >\ {\frac {a+3\cdot b}{c+3\cdot d}}\ >\ {\frac {b}{d}}$

or

${\frac {a}{c}}\ >\ {\frac {3\cdot a+b}{3\cdot c+d}}\ >\ x\ >\ {\frac {2\cdot a+b}{2\cdot c+d}}\ >\ {\frac {a+b}{c+d}}\ >\ {\frac {b}{d}}$

holds, where

$\left({\frac {a}{c}},{\frac {b}{d}}\right)\ :=\ A_{n}$

 

The top-top-bot case

Let's consider the latter top-top-bot case. Let $\ \xi :={\frac {d}{c}}.$  The squeeze by neighbors:

${\frac {a}{c}}\ >\ x\ >\ {\frac {2\cdot a+b}{2\cdot c+d}}$

shows that

$0\ <\ {\frac {a}{c}}-x\ <\ {\frac {1}{c\cdot (2\cdot c+d)}}\ =\ {\frac {1}{(2+\xi )}}\cdot {\frac {1}{c^{2}}}$

This inequality provides the first insight (otherwise, we are not going to use it), so it deserves to be written cleanly as an implication:

$0\ <\ {\frac {a}{c}}-x\ <\ {\frac {1}{(2+\xi )}}\cdot {\frac {1}{c^{2}}}\quad \quad \Leftarrow \quad \quad {\frac {a}{c}}\ >\ x\ >\ {\frac {2\cdot a+b}{2\cdot c+d}}$

The relevant neighborhoods

Consider the next two pairs of neighbors, pair $\ A_{n+4}$  and pair $\ A_{n+5},$  which squeeze $\ x.$  The relevant neighborhoods are:

• $A\ :=\ {\mathit {Span}}({\frac {a}{c}},\,{\frac {3\cdot a+b}{3\cdot c+d}})$

• $B\ :=\ {\mathit {Span}}({\frac {3\cdot a+b}{3\cdot c+d}},\,{\frac {5\cdot a+2\cdot b}{5\cdot c+2\cdot d}})$

• $C\ :=\ {\mathit {Span}}({\frac {5\cdot a+2\cdot b}{5\cdot c+2\cdot d}},\,{\frac {7\cdot a+3\cdot b}{7\cdot c+3\cdot d}})$

• $D\ :=\ {\mathit {Span}}({\frac {7\cdot a+3\cdot b}{7\cdot c+3\cdot d}},\,{\frac {2\cdot a+b}{2\cdot c+d}})$

 

Neighborhood B

Let  $\ x\in B.$  Then

${\frac {a}{c}}\ >\ {\frac {3\cdot a+b}{3\cdot c+d}}\ >\ x\ >\ {\frac {5\cdot a+2\cdot b}{5\cdot c+2\cdot d}}\ >\ {\frac {2\cdot a+b}{2\cdot c+d}}$

and

$0\ <\ {\frac {a}{c}}-x\ <\ {\frac {1}{c\cdot (3\cdot c+d)}}+{\frac {1}{(3\cdot c+d)\cdot (5\cdot c+2\cdot d)}}$

$=\ {\frac {2}{c\cdot (5\cdot c+2\cdot d)}}\ =\ {\frac {2}{(5+2\cdot \xi )}}\cdot {\frac {1}{c^{2}}}$

Conclusion:

$0\ <\ {\frac {a}{c}}-x\ <\ {\frac {2}{(5+2\cdot \xi )}}\cdot {\frac {1}{c^{2}}}\quad \quad \Leftarrow \quad \quad x\in B$

Neighborhood C (first C-inequality)

Let  $\ x\in C.$  Then

${\frac {a}{c}}\ >\ {\frac {3\cdot a+b}{3\cdot c+d}}\ >\ {\frac {5\cdot a+2\cdot b}{5\cdot c+2\cdot d}}\ >\ x\ >\ {\frac {7\cdot a+3\cdot b}{7\cdot c+3\cdot d}}$

Thus using the calculation for neighborhood B also for C, we get

$0\ <\ {\frac {a}{c}}-x\ <\ {\frac {2}{(5+2\cdot \xi )\cdot c^{2}}}+{\frac {1}{(5\cdot c+2\cdot d)\cdot (7\cdot c+3\cdot d)}}$

$=\ {\frac {3}{7+3\cdot \xi }}\cdot {\frac {1}{c^{2}}}$

Conclusion:

$0\ <\ {\frac {a}{c}}-x\ <\ {\frac {3}{7+3\cdot \xi }}\cdot {\frac {1}{c^{2}}}\quad \quad \Leftarrow \quad \quad x\in C$

 

Neighborhood D

Let  $\ x\in D,$  i.e.

${\frac {7\cdot a+3\cdot b}{7\cdot c+3\cdot d}}\ >\ x\ >\ {\frac {2\cdot a+b}{2\cdot c+d}}$

Let  $\alpha :=2\cdot a+b$  and  $\gamma :=2\cdot c+d=(2+\xi )\cdot c.$  Then

$0\ <\ x-{\frac {\alpha }{\gamma }}\ =\ x-{\frac {2\cdot a+b}{2\cdot c+d}}$

$<\ {\frac {1}{(7\cdot c+3\cdot d)\cdot (2\cdot c+d)}}\ =\ {\frac {1}{(7+3\cdot \xi )\cdot c\cdot \gamma }}$

$=\ {\frac {2+\xi }{7+3\cdot \xi }}\cdot {\frac {1}{\gamma ^{2}}}$

 

Divisibility

Definition  Integer $\ a$  is divisible by integer $\ b$   $\Leftarrow :\Rightarrow \$   $\exists _{c\in \mathbb {Z} }\ a=b\cdot c$

Symbolically:

$b|a\$   $\Leftarrow :\Rightarrow \$   $\exists _{c\in \mathbb {Z} }\ a=b\cdot c$

When $\ a$  is divisible by $\ b$  then we also say that $\ b$  is a divisor of $\ a,$  or that $\ b$  divides $\ a.$

• The only integer divisible by $\ 0$  is $\ 0$  (i.e. $\ 0$  is a divisor only of $\ 0$).
• $0\$  is divisible by every integer.
• $1\$  is the only positive divisor of $\ 1.$
• Every integer is divisible by $\ 1$  (and by  $\ -1$).

 

• $a|b\ \Rightarrow (-a|b\ \land \ a|\!-\!\!b)$
• $a|b>0\ \Rightarrow a\leq b$

 

• $a|a\$
• $(a|b\ \land \ b|c)\ \Rightarrow \ a|c$
• $(a|b\ \land \ b|a)\ \Rightarrow \ |a|=|b|$

Remark  The above three properties show that the relation of divisibility is a partial order in the set of natural number  $\mathbb {N} ,$  and also in $\mathbb {Z} _{+}$ — $\ 1$  is its minimal, and $\ 0$  is its maximal element.

• $(a|b\ \land \ a|c)\ \Rightarrow \ (a\,|\,b\!\cdot \!d\ \land \ a\,|\,b\!+\!c\ \land \ a\,|\,b\!-\!c)$

 

Relatively prime pairs of integers

Definition  Integers $\ a$  and $\ b$  are relatively prime   $\Leftarrow :\Rightarrow \$   $\ 1$  is their only common positive divisor.

• Integers $\ x$  and $\ 0$  are relatively prime   $\Leftrightarrow \ |x|=1.$
• $1\$  is relatively prime with every integer.
• If $\ a$  and $\ b$  are relatively prime then also $\ a$  and  $\ -b$  are relatively prime.

Theorem 1  If $\ a,b,c\in \mathbb {Z}$  are such that two of them are relatively prime and $\ a+b=c,$  then any two of them are relatively prime.

Corollary  If $\ a$  and $\ b$  are relatively prime then also $\ a$  and  $\ |a-b\,|$  are relatively prime.

Now, let's define inductively a table odd integers:

$(\nu _{k,n}:k\in \mathbb {Z} _{+},\ 0\leq n\leq 2^{k})$

as follows:

• $\nu _{0,0}:=0\$     and     $\nu _{0,1}:=1\$
• $\nu _{k+1,2\cdot n}\ :=\ \nu _{k,n}$   for  $0\leq n\leq 2^{k}\$
• $\nu _{k+1,2\cdot n+1}\ :=\ \nu _{k,n}+\nu _{k,n+1}$   for  $0\leq n<2^{k}\$

for every  $\ k=0,1,\dots .$

The top of this table looks as follows:

0 1

0 1 1

0 1 1 2 1

0 1 1 2 1 3 2 3 1

0 1 1 2 1 3 1 3 1 4 3 5 2 5 3 4 1

etc.

Theorem 2

• Every pair of neighboring elements of the table, $\ \nu _{k,n}$  and $\ \nu _{k,n+1}$   is relatively prime.
• For every pair of relatively prime, non-negative integers $\ a$  and $\ b$  there exist indices $k\in \mathbb {Z} _{+}$  and non-negative $\ n<2^{k}$  such that:

$\{a,b\}\ =\ \{\nu _{k,n},\nu _{k,n+1}\}$

Proof  Of course the pair

$\{\nu _{0,0},\nu _{0,1}\}\ =\ \{0,1\}$

is relatively prime; and the inductive proof of the first statement of Theorem 2 is now instant thanks to Theorem 1 above.

Now let $\ a$  and $\ b$  be a pair of relatively prime, non-negative integers. If $\ a+b=1$  then $\ \{a,b\}=\{0,1\}=\{\nu _{0,0},\nu _{0,1}\},$  and the second part of the theorem holds. Continuing this unductive proof, let's assume that $\ a+b>1.$  Then $\ \min(a,b)>0.$  Thus

$\ \max(a,b)<a+b$

But integers $\ c:=\min(a,b)$  and $\ d:=|a-b|$  are relatively prime (see Corollary above), and

$c+d\ =\ max(a,b)\ <\ a+b$

hence, by induction,

$\{c,d\}\ =\ \{\nu _{k,n},\nu _{k,n+1}\}$

for certain indices $k\in \mathbb {Z} _{+}$  and non-negative $\ n<2^{k}.$  Furthermore:

$\{a,b\}\ =\ \{\min(a,b),\max(a,b)\}$

It follows that one of the two options holds:

$\{a,b\}\ =\ \{\nu _{k+1,2\cdot n},\nu _{k+1,2\cdot n+1}\}$

or

$\{a,b\}\ =\ \{\nu _{k+1,2\cdot n+1},\nu _{k+1,2\cdot n+2}\}$

End of proof

Let's note also, that

$\max _{\quad 0\leq n\leq 2^{k}}\nu _{k,n}\ =\ F_{k+1}$

where $\ F_{r}$  is the r-th Fibonacci number.

Matrix monoid ${\mathit {SO}}(\mathbb {Z} _{+},2)$

Definition 1  ${\mathit {SO}}(\mathbb {Z} _{+},2)$  is the set of all matrices

$M\ :=\ \left[{\begin{array}{cc}a&b\\c&d\end{array}}\right]$

such that $\ a,b,c,d\in \mathbb {Z} _{+},$  and  $\ \det(M)=1,$  where  $\ \det(M):=a\cdot d-b\cdot c.$  Such matrices (and their columns and rows) will be called special.

• If

$M\ :=\ \left[{\begin{array}{cc}a&b\\c&d\end{array}}\right]\in {\mathit {SO}}(\mathbb {Z} _{+},2)$

then  $\ a,d>0,$  and each of the columns and rows of M, i.e. each of the four pairs  $(x,y)\in \{a,d\}\times \{b,c\},\$  is relatively prime.

Obviously, the identity matrix

${\mathcal {I}}\ :=\ \left[{\begin{array}{cc}1&0\\0&1\end{array}}\right]$

belongs to   ${\mathit {SO}}(\mathbb {Z} _{+},2).$  Furthermore,  ${\mathit {SO}}(\mathbb {Z} _{+},2)$  is a monoid with respect to the matrix multiplication.

Example  The upper matrix and the lower matrix are defined respectively as follows:

${\mathcal {U}}\ :=\ \left[{\begin{array}{cc}1&1\\0&1\end{array}}\right]$   and   ${\mathcal {L}}\ :=\ \left[{\begin{array}{cc}1&0\\1&1\end{array}}\right]$

Obviously $\ {\mathcal {U}},{\mathcal {L}}\in {\mathit {SO}}(\mathbb {Z} _{+},2).$  When they act on the right on a matrix M (by multipliplying M by itself), then they leave respectively the left or right column of M intact:

$M\cdot {\mathcal {U}}\ =\ \left[{\begin{array}{cc}a&a+b\\c&c+d\end{array}}\right]$

and

$M\cdot {\mathcal {L}}\ =\ \left[{\begin{array}{cc}a+b&b\\c+d&d\end{array}}\right]$

Definition 2  Vectors

$\left[{\begin{array}{c}a\\c\end{array}}\right]$     and     $\left[{\begin{array}{c}b\\d\end{array}}\right]$

where $\ a,b,c,d\in \mathbb {Z} _{+},$  are called neighbors (in that order)   $\Leftarrow :\Rightarrow$   matrix formed by these vectors

$M\ :=\ \left[{\begin{array}{cc}a&b\\c&d\end{array}}\right]$

belongs to  ${\mathit {SO}}(\mathbb {Z} _{+},2).$  Then the left (resp. right) column is called the left (resp. right) neighbor.

Rational representation

With every vector

$v\ :=\ \left[{\begin{array}{c}a\\c\end{array}}\right]$

such that $\ c\neq 0,$  let's associate a rational number

${\mathit {rat}}(v)\ :=\ {\frac {a}{c}}$

Also, let

${\mathit {rat}}(v_{\infty })\ :=\ \infty$

for

$v_{\infty }\ :=\ \left[{\begin{array}{c}1\\0\end{array}}\right]$

Furthermore, with every matrix  $M\in {\mathit {SO}}(\mathbb {Z} _{+},2),$  let's associate the real open interval

${\mathit {span}}(M)\ :=\ ({\mathit {rat}}(w);{\mathit {rat}}(v))$

and its length

$|M|\ :=\ {\mathit {rat}}(v)-{\mathit {rat}}(w)$

where $\ v$  is the left, and $\ w$  is the right column of matrix M — observe that the rational representation of the left column of a special matrix is always greater than the rational representation of the right column of the same special matrix.

• If

$M\ :=\ \left[{\begin{array}{cc}a&b\\c&d\end{array}}\right]\in {\mathit {SO}}(\mathbb {Z} _{+},2)$

then  $\ |M|={\frac {1}{c\cdot d}}$