1
$\begingroup$

Suppose that $a,b\in \mathbb{N}$ and our goal to find $\text{gcd}(a,b)$ and the most effective way to do that is the Euclidean algorithm. I know how the algorithm works but I'd like to understand thoroughly and that is why I created this topic because some moments are not crystal clear to me.

Suppose we are given two natural numbers $a,b\in \mathbb{N}$ and assume that $a>b$ with $a\nmid b$.

Step #0. Then there is the unique pair of integers $q_0, r_2$ such that $a=bq_0+r_2,$ where $0<r_2<b$. Let's introduce the new notation $r_0:=a$ and $r_1:=b$. Then

$$r_0=r_1q_0+r_2, \text{where} \ 0<r_2<r_1.$$

Step #1. Then we apply the same procedure to the pair $\{r_1,r_2\}$ and obtain that

$$r_1=r_2q_1+r_3, \text{where} \ 0\leq r_3<r_2.$$

If $r_3=0$ then $(a,b)=r_2$ and I know how to prove it.

If $r_3>0$ then we move on to the Step #2 where $r_2=r_3q_2+r_4$ with $0\leq r_4<r_3$.

Claim: On some step #m with $m\geq 1$ the remainder $r_{m+2}$ will vanish.

Proof: Suppose this is false. Then on any step #m the remained is nonzero, i.e. $r_{m+2}>0$. Then it is easy to show that $r_{n+2}\leq b-n-1$. Hence $0<r_{b+2}\leq -1<0$. But this is a contradiction.

Hence $\exists m\geq 1$ such that $r_{m+2}=0$. Then it implies that $r_{m+1}\neq 0$ (otherwise if $r_{m+1}=0$ then $r_m=\dots=r_1=0$, right? Can anyone show the rigorous proof of that? Probably the proof relies on induction).

Hence $r_{m+1}\mid r_m$ and $(a,b)=(b,r_2)=(r_1,r_2)=\dots=(r_m,r_{m+1})=r_{m+1}.$

Is my reasoning correct? If yes, can anyone explain the question which I've asked?

Thanks in advance!

$\endgroup$
0

1 Answer 1

Reset to default
1
$\begingroup$

You showed that there exist $m$ such that $r_{m+2} = 0$. Now we can not directly conclude that $r_{m+1} \ne 0$. In fact we can show that there exist $k$ such that $r_k = 0$ but $r_{k-1} \ne 0$. To see this let $ S = \{ t \in \mathbb{N} \, \vert \, r_t = 0 \} $. Clearly $S$ is non emty since $m+2 \in S$. By well ordering principle $S$ has a least element $k$ such that $r_k = 0$. This would imply that $r_{k-1}$ is non zero since $k-1 $ is not in $S$ .

But the above argument using well ordering principle isn't really necessary, since for each $i$, we have $r_i > r_{i+1}$. S0 $0=r_{m+2} < r_{m+1} < r_m < \cdots r_1 $. So this gives us that $r_{i} \ne 0$ for all $i =1,2 \dots ,m+1$

Another approach: Alternatively, You have the chain of inequalities $r_1 > r_2 > \cdots $ where each $r_i \ge 0$. Argue that this chain cannot contain infinite number of elements (indeed it can contain at-most $r_1$ elements). Then strict inequality yields one of $r_m=0$

$\endgroup$
15
  • $\begingroup$ Sorry but your answer has nothing in common with my question. $\endgroup$ Commented Jul 4, 2021 at 15:06
  • $\begingroup$ @PlayGame I edited my answer. $\endgroup$ Commented Jul 4, 2021 at 15:41
  • $\begingroup$ Actually I was also thinking in this manner (through well ordering principle). But there is one subtle moment: If $r_{i}=0$ then the process terminates, i.e. there and $r_j$ with $j>I$. I mean that if $r_{m+2}=0$ then previous terms should be non-zero. If one of the previous terms is zero then the sequence $r_{m+2}$ does not make sense. So we have to be very careful. That is why I am so confused with Euclid algorithm. $\endgroup$ Commented Jul 4, 2021 at 15:55
  • $\begingroup$ We should use the fact $r_i > r_{i+1}$ for each $i$. $\endgroup$ Commented Jul 4, 2021 at 16:27
  • $\begingroup$ Please read my comment carefully. If at some $r_i=0$ then there is no $r_{I+1}$ so it is not valid to talk about $r_i>r_{I+1}$ for each $I$. $\endgroup$ Commented Jul 4, 2021 at 16:30

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.