# Deduce that the number of divisions in the Euclidean algorithm is at most $2n + 1$

Theorem. If $a > 0$ and $b$ is arbitrary, there is exactly one pair of integers $q, r$ such that the conditions $b = qa + r, 0 \leqslant r < a$, hold.

Repeated application of this theorem yields: \begin{align} a &= bq_1 + r_1,\hspace{1.6cm} 0 \leqslant r_1 < b\\b&=r_1q_2 + r_2,\hspace{1.4cm} 0 \leqslant r_2 < r_1 \\ r_1 &=r_2q_3 + r_3,\hspace{1.4cm} 0 \leqslant r_3 < r_2 \\& \vdots \\r_{k-3} &= r_{k-2}q_{k-1} + r_{k-1},\hspace{0.2cm} 0 \leqslant r_{k-1} < r_{k-2} \\r_{k-2} &= r_{k-1} q_k + r_k,\hspace{1cm} 0 \leqslant r_k < r_{k-1} \\r_{k-1} &= r_kq_{k+1}. \end{align}

(i) Show that each nonzero remainder $r_k$, with $k \geqslant 2$, is less than $\frac{r_{k-2}}{2}.$

Proof. If we multiply $r_k < r_{k-1}$ by $q_k$ and add $r_k$ to both sides, we obtain $r_k(q_k + 1) < r_{k-2}$. Since $r_k = \frac{2}{2}r_k = \frac{1 + 1}{2} r_k \leqslant \frac{r_k(q_k + 1)}{2}$, it follows that $r_k < \frac{r_{k-2}}{2}$. $\text{ } \Box$

(ii) Deduce that the number of divisions in the Euclidean algorithm is at most $2n + 1$, where $n \in \mathbb{Z}$ such that $2^n \leqslant b < 2^{n+1}$, and where $b$ is the smaller of the two numbers whose gcd is being found.

How do we approach part (ii)? I'm thinking if we let $m =$ #divisions when computing gcd$(a,b)$ and define a function $(a,b) \mapsto m$, we may prove it inductively on $b$, but I am unsure of the specifics and I suspect an easier method.

## 1 Answer

Hint: use already proved part (i).