Exercise 7.1.2 (Short continued fractions)

Proof.

(a)

If $u_1=1$ then the Euclidean algorithm gives the unique equation $$u_0=u_1\cdot 1+0.$$

Since the remainder $u_2=0$, there is no other equation.

If $u_1>1$, the fist equation is

$$u_0=u_1\cdot a_0+u_2.$$

Since $u_0\wedge u_1=1$ and $u_1>1$, $u_1\nmid u_0$, therefore $u_2\ne 0$, so there is at least one more equation to finish the Euclidean algorithm.

The set of equations of the Euclidean algorithm consists of exactly one equation if and only if $u_1=1$.

(b)

If $0<{\xi }_0=u_0∕u_1<1$, then $u_0=0\cdot u_1+u_0$, where $0<u_0<u_1$, thus the remainder is $u_2=u_0$ and the quotient is $a_0=0$.

Note that if $u_0∕u_1=0$, then $u_0=0,u_1=1$, where $u_0\wedge u_1=1$ and $u_1>0$. This gives $u_0=u_1\cdot 0$, which ends the algorithm, so $a_0=0$.

Conversely, if $a_0=0$ and $u_0\ne 0$, then the first equation of the Euclidean algorithm gives

$$u_0=u_1\cdot 0+u_2=u_2,\text{ and }0<u_2=u_0<u_1.$$

Therefore $0<u_0∕u_1<1$.

So $a_0=0$ if and only if $0\le {\xi }_0<1$.

(This is obvious if we know that $a_0=\lfloor {\xi }_0\rfloor$.)