2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

Hint: use already proved part (i).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.