# Euclidean algorithm and its formal proof

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. Let's introduce the new notation $$r_0:=a$$ and $$r_1:=b$$. Then

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

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

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.

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. 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?

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$$

• Sorry but your answer has nothing in common with my question.
– RFZ
Commented Jul 4, 2021 at 15:06
• @PlayGame I edited my answer. Commented Jul 4, 2021 at 15:41
• 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.
– RFZ
Commented Jul 4, 2021 at 15:55
• We should use the fact $r_i > r_{i+1}$ for each $i$. Commented Jul 4, 2021 at 16:27
• 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$.
– RFZ
Commented Jul 4, 2021 at 16:30