Exercise 1.2.42 ($|x_j| \leq c/(2g)$)

Proof. The last equation of the Euclidean algorithm is $r_{j-1}=r_j{q}_{j+1}$, where $0<r_j<r_{j-1}$ (see Theorem 11). Therefore

Since $q_{j+1}$ is an integer, $q_{j+1}\ge 2$ (this is not true for the others $q_i$ such that $i\le j$).

By Problem 39,

and by Problem 41, $|x_{j+1}|=c∕g$, thus

If $x_j=c∕(2g)$, then

thus $|x_{j-1}|+(q_{j+1}-2)|x_j|=0$. Since $|x_{j-1}|\ge 0$ and $(q_{j+1}-2)|x_j|\ge 0$, this shows that $|x_{j-1}|=0$ and $(q_{j+1}-2)|x_j|=0$ (otherwise $|x_{j-1}|+(q_{j+1}-2)|x_j|>0$). So $x_{j-1}=0$.

Moreover $x_j\ne 0$, otherwise $c∕g=|x_{j-1}|+q_{j+1}|x_j|=0$, in contradiction with the hypothesis $c>0$. Therefore $q_{j+1}=2$.

We have proved $|x_j|\le c∕(2g)$, with equality if and only if $q_{j+1}=2$ and $x_{j-1}=0$.

Similarly

so

□