1
$\begingroup$

In my lecture notes there is the following: $$\newcommand{\gcd}{\operatorname{gcd}} a, b \in \mathbb{N}, \gcd(a, b)=d \implies \exists s, t \in \mathbb{Z} : sa+tb=d \implies tb \equiv d \pmod a$$

If $\gcd(a, b)=1$ then $tb \equiv 1 \pmod a \ $ $ \ \ \ [b]_a \in \mathbb{Z}_a^{\star}$ and $[b]_a^{-1}=[t]_a$

$$r_0=a, r_1=b \\ r_0=q_1 r_1+r_2 , 0 < r_2 <r_1 \\ r_1=q_2 r_2 + r_3, 0<r_3 < r_2 \\ \dots \\ r_{l-1}=q_{l-1}r_{l-1}+r_l, 0<r_l < r_{l-1} \\ r_{l-1}=q_l r_l+0$$

$\gcd(a, b)=r_l$

$$b, b-1, b-2, \dots , 0 \\ l \leq b$$

Because there isn't any explanation what $b, b-1, b-2, \dots , 0$ means, do you have any idea about what it could mean? What does this represent?

$\endgroup$
1
  • $\begingroup$ Context is important. Usually $a \geq b$, in which case the remainder of $a$ upon division by $b$ will be in the set: $\{0,1,\dots,b-2,b-1\}$. One can also divide $b$ by $a$, but the remainder is then immediately seen to be $0$ (if $a = b$), or $a$, if $a > b$. $\endgroup$
    – David Wheeler
    Commented Mar 3, 2015 at 19:55

2 Answers 2

Reset to default
1
$\begingroup$

The point here seems to be to give a simple argument why the Euclidean algorithm terminates.

The sequences of remainders $r_i$ is strictly decreasing and $r_1 = b$. So it will stop at at most $r_b$, as the worst case would be $r_2 = b-1$, $r_3 = b-2$ and so on $r_b = b - (b-1)=1$, so then the following remainder must be $0$.

Note that there are somewhat more sophisticated arguments that give a much better bound for the number of necessary steps.

$\endgroup$
1
$\begingroup$

My guess is the following: your teacher wanted to show that $l < b$. Since $r_1 = b$ and $r_{i+1} \leq r_i - 1$, it follows that $r_{i} \leq b - i + 1$ (which is what that sequence seems to represent). Now since $r_l > 0$, we get that $l \leq b$.

$\endgroup$

You must log in to answer this question.